パラメータの MIPGap は、返される解について最悪の品質を制御します。これは最終的に得られる解の実際のMIP Gapの上限です。GurobiはMIPGapよりも大幅に良い解を見つけるまで実行されることがありますが、これは与えられたMIPGapちょうどで終了できるとは限らないためです。その理由の1つは、Gapの改善が連続的な進行ではなく、次のように離散的に行われるためです：
MIPGapパラメータは単なる終了条件ではなく、他の部分でもアルゴリズムに影響を与えることに注意が必要です。異なるMIPGapを設定した場合、ソルバーが異なる最適化パスを通り、異なる動作をすることがあります。
GurobiのGapは以下の式で計算されます。
\[\frac{\left| \text{ObjBound} - \text{ObjVal} \right|}{\left| \text{ObjVal} \right|}\]
最適化を利用される方の中には、MIPGapの値を正の ε に設定することで、チャンスを取りこぼしてしまうのではないかと心配する人もいるかもしれません。次のように最適化プロセスにはいくつかの状況があり得ることを知ることで、その悩みが少し軽減されるかもしれません。
- Gurobiは、現在のMIP Gapが許容誤差よりも大きい（例えば、εが0.01%に対して、現在のMIP Gapが40%であるような場合）にもかかわらず、最適化の早い段階で大域的最適解を発見することがあります。
- しかし、Gurobiが ε で定義されたMIP Gapを達成し最適化の実行を終了したとき、最適解ではない可能性のある解を返すこともあります。このようなとき、得られた解は ε-準最適解と呼ばれます。そのような解が達成する目的関数値は、分枝限定木を探索し続けた場合に見つかる可能性のある他の解が達成する値より、最悪でも ε（例えば0.01%）悪いからです。ただし、ひとつ前の箇条書きですでに説明したように、そのような解が存在する保証はありません（すなわち最適解が得られている可能性もあります）。
いずれの場合でも、与えられたMIPGap=ε に対して、Gurobiが終了すると、最適解がソルバーによって発見された解の ε-近傍にあることが保証されます。さらに、実世界のアプリケーションでは、次の理由から、常に正の MIP Gap許容値を設定するのが賢明です。
- 数値精度: ソルバーは有限精度の演算を使用します。GAP=0 は数値精度の限界により問題を引き起こす可能性があります。
- 計算時間: Gapを正確に0にするには、多くの場合、時間がかかり、計算リソースを大量に消費します。そのため、Gurobi はデフォルトで小さな非負の値を使用して、解の品質と求解時間のバランスを取り、過度の計算を行わずに最適な結果に近い結果を提供します。
- 収穫逓減: ギャップが小さくなると解のわずかな改善に対して、指数関数的に多くの労力が必要になります。
- ソルバー上の制限: GAP=0を強制すると、ソルバーのヒューリスティックスが妨げられ、パフォーマンスが低下する可能性があります。
コメント
0件のコメント
記事コメントは受け付けていません。