多次元非線形0－1ナップザック問題のためのエントロピーを用いた問題困難度推定法

摘要

代理双対ギャップをもつ大規模な多次元非線形ナップザック問題（多制約分離形離散最適化問題）を，効率良く解く改良代理制約法（ISC）が提案された．この解法により極めて大規模な問題が厳密に解けるようになった．その際問題を解くときの困難さは，変数の数や制約条件式の数に直接関係なく，また代理ギャップの大きさも直接関係しないことが示された．本論文では多次元非線形0－1ナップザック問題のエントロピーを用いた新しい問題困難度推定法を提案する．また計算機実験でその有効性を示す．