オリジナルURL: What is the MIPGap?
パラメータの 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が終了すると、最適解がソルバーによって発見された解の ε-近傍にあることが保証されます。さらに、実世界のアプリケーションでは、ユースケースごとに十分な最適性を持つことと、分枝限定木を探索するのに必要な計算時間（多くの場合、完全に探索し尽くすことは非現実的です）とのトレードオフを調整するために、正のMIPGapを設定することが推奨されます。
Comments
0 comments
Article is closed for comments.