Gurobiのログ上で、gap値の増大が見られることがあります。下記の例ではgap値が113% から 4171%に増加し再び減少し始めます。
Nodes | Current Node | Objective Bounds | Work Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time 1503 1467 -283.00000 284 285 2160.99979 -285.00000 113% 609 127s H 1968 1870 1858.0000000 -285.00000 115% 662 145s [...] 4854 3038 -257.55772 357 368 13.00000 -285.00000 2292% 1044 919s H 4924 2950 8.0000000 -285.00000 3662% 1050 919s 5130 3120 -246.16119 393 407 8.00000 -285.00000 3662% 1044 942s H 5317 3172 7.0000000 -285.00000 4171% 1059 942s 5630 3377 infeasible 468 7.00000 -285.00000 4171% 1042 969s 5716 3420 -285.00000 21 472 7.00000 -285.00000 4171% 1058 993s 5937 3615 -284.00000 77 403 7.00000 -285.00000 4171% 1057 1024s H 5938 3615 2.0000000 -285.00000 - 1057 1024s [...] 8623 6061 -213.60040 141 748 2.00000 -285.00000 - 1219 1487s H 8848 6207 -103.0000000 -285.00000 177% 1210 1487s 9149 6446 infeasible 191 -103.00000 -285.00000 177% 1199 1561s 9675 6904 -280.00000 114 725 -103.00000 -285.00000 177% 1182 1626s [...] H18133 14145 -118.0000000 -285.00000 142% 1015 3309s 18258 14238 -264.98878 195 590 -118.00000 -285.00000 142% 1020 3408s 18590 14461 -198.90509 211 630 -118.00000 -285.00000 142% 1027 3622s H18749 815 -284.0000000 -285.00000 0.35% 1025 3622s
これは特定の状況下で起こりえるふるまいです。相対的なMIP gapは次のように定義されています：
\[\frac{\left| \text{ObjBound} - \text{ObjVal} \right|}{\left| \text{ObjVal} \right|}\]
ObjBound と ObjVal は MIPにおける目的関数の限界値 (BestBd列) と現在の暫定解の目的関数値に対応します。もしこの二つの値の符号が異なる場合、例のようにMIP gap値の解釈が意味をなさない場合があります。
また、ギャップが9999%より大きい場合、フォーマットの問題を避けるため、Gurobiはこの値をログに表示しません。このようなときには、 - が表示されます。ただし、暫定解の場合でも- が表示されることに注意してください。
目的関数に、値が常に正になるような十分な大きさの定数を追加することは可能です。しかし、その場合にも gap の意味合いが変わってしまうことに注意が必要です。
コメント
0件のコメント
記事コメントは受け付けていません。