双線形ナップサック問題の解法

概要

論文の詳細を見る
この論文は、x^εR^m。y^εR^nがそれぞれ独立な0-1ナップザック制約式を満足する、という条件の下で、x、yに関する双線形関数を最大化する、"双線形ナップザック問題"の解法を論じたものであ私この問題は2次0-1整数計画問題の一種で、これまでのところ分枝限定法を含め、実用的解法が得られていない問題の1つである。ここで提案した切除平面法は、従来双線形計画問題や凸2次関数最大化問題に対して、著者らが開発してきた切除平面法をべースとし、双線形ナップザック問題の特殊構造を取入れて効率化を図ったもので、この算法を用いて数値実験を行なった結果、mが20、nが100程度の問題に対しては、たかだか数本のカットを導入するだけで最適解が生成されることが確かめられた。また、カットを用いない、より単純な交互山登りルーチンが、10個程度の出発点をランダムに選ぶことにより、90%以上のサンプル問題に対して実際に最適解を生成していたことが結果的に確かめられた。このことは、より大規模な双線形ナップザック問題や、双線形計画問題一般に対する実用的な解法としての交互山登り法の可能性を示唆するものである。