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

摘要

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