かなりハードな MIP

以下の MIP であるが、Gurobi 4.5.1 で解いてみると前処理後は 62行, 312列, 1252 非零要素それに 310 個の 0-1 変数となり、規模的にはそんなに大きな問題とも言えない。ところが 0 秒後に上界 308, 下界 231 を求めて以降、少なくとも 93531秒後(約 26時間後)では上界と下界の差が縮まっていない。メモリ的にはこの計算サーバの限界近くにまで達しているのだが、しばらくはこのまま実行を継続してみることにする。

vmpackin: 62 rows, 312 columns, 1252 nonzeros
Optimize a model with 62 rows, 312 columns and 1252 nonzeros
Presolve removed 2 rows and 2 columns
Presolve time: 0.01s
Presolved: 60 rows, 310 columns, 1230 nonzeros
Variable types: 0 continuous, 310 integer (310 binary)
Found heuristic solution: objective 770.0000000
Found heuristic solution: objective 315.0000000

Root relaxation: objective 2.143830e+02, 138 iterations, 0.00 seconds

Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time

0 0 214.38302 0 24 315.00000 214.38302 31.9% - 0s
0 0 228.85588 0 47 315.00000 228.85588 27.3% - 0s
0 0 231.00000 0 41 315.00000 231.00000 26.7% - 0s
0 0 231.00000 0 51 315.00000 231.00000 26.7% - 0s
0 0 231.00000 0 16 315.00000 231.00000 26.7% - 0s
H 0 0 308.0000000 231.00000 25.0% - 0s
0 6 231.00000 0 16 308.00000 231.00000 25.0% - 0s

中略

307095051 144319829 231.00000 53 8 308.00000 231.00000 25.0% 6.4 93511s
307099899 144322271 233.81181 60 11 308.00000 231.00000 25.0% 6.4 93517s
307101111 144322821 234.23310 64 8 308.00000 231.00000 25.0% 6.4 93527s
307104747 144324622 cutoff 63 308.00000 231.00000 25.0% 6.4 93531s