多次元非線形ナップザック問題のための分枝困難度法

摘要

代理双対ギャップをもつ大規模な多次元非線形ナップザック問題を厳密に効率良く解く改良代理制約法（ISC法）が提案された．しかし，ギャップが大きい問題の中には，ISC法にとっていまだに解くことが難しい問題が存在する．本分枝困難度法は，問題の難しさを測る尺度として上界値や困難度エントロピーを用いることで，ギャップが大きく解くことが極めて難しい問題を，よりギャップが小さく解きやすい複数個の部分問題へ分割することを可能にする．計算機実験で本手法の有効性を示す．