非線形ナップザック問題における新上界値計算法

摘要

非線形ナップザック間題を効率的に解くためには,限界値操作における上界値または下界値が重要である.この限界値を求める一般的な方法は,線形緩和問題を解くことである. 1979年に　 Sinha-Zoltnersは線形緩和問題の最適解であるLP解をもとに,よりよい限界値を計算する方法を用いている.本論文は, Sinha-Zoltnersよりも更によい限界値を計算する新しい方法を提案し,計算機実験により比較を行う.