Knapsack Problem

複数制約ナップサック問題は比較的MIPソルバーで解きやすい問題である.比較的古い論文でChu-Beasleyが遺伝的アルゴリズムを, Glover-Kochenbergerが禁断探索法のテストをするために作成したベンチマーク問題例は,Gurobiである程度までは解くことができる.

計算時間のグラフを以下に示す.
問題のサイズと計算時間

これを見ると,変数の数が2500を超えるようになると厳密解を出すのに多大な時間を要することが分かる.しかし,どの問題例も短時間で上界と下界のギャップは比較的小さくなっており,途中で計算を打ち切って得られる近似解は,十分に実用に耐えうると考えられる.

最大の問題例であるmk_gk11_100x2500(この問題例は250000個の変数を含む!)と呼ばれる問題の計算ログの一部を以下に示す.

Found heuristic solution: objective 93813.000000
Root relaxation: objective 9.527749e+04, 1007 iterations, 0.37 seconds
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time

0 0 95277.4913 0 100 93813.0000 95277.4913 1.56% – 0s
H 0 0 95155.000000 95277.4913 0.13% – 1s
H 0 0 95218.000000 95277.4913 0.06% – 5s
0 2 95277.4912 0 100 95218.0000 95277.4912 0.06% – 12s

これによると分枝の前のヒューリスティクスで93813という解を見つけ,分枝開始から12秒後に誤差0.06%の解を得ている.

他のメタヒューリスティクス(詳細については,「メタヒューリスティクスの数理」(共立出版)を参照)との比較はまだ行っていないが,近似解法としてのGurobiに対抗するのは難しいと考えられる.