Gurobi がMIPを解くのにかかる時間を推定する方法はあるか？

オリジナルURL：Is there a way to predict how long it will take Gurobi to solve a MIP?

一般に、MIPを解くのにかかる時間を見積もるのは非常に難しいといえます。NP困難問題の性質上、解くのに非常に長い時間がかかったり、実用的な時間では解けないことさえあります。Gurobiは、非常に高度な解法テクニックやトリックを数多く備えているため、大規模なモデルであっても、しばしば迅速に解を見つけることが可能です。また、一見簡単そうに見える問題でも、解くのが非常に難しいものもあります。

Gurobiのログ出力は、現在のソルバーの状態を把握することに役立ちます。ログ出力の詳細については、ドキュメントの MIP Logging セクションを参照してください。このうち、残り時間を推定するために最も関連性の高いものは以下の通りです：

• MIPGAP列の推移
• Unexplored(またはopen) ノード列の情報

MIPGap

MIPGap が順調に減少している場合、新しい暫定解（Hまたは*印）を見つけるか、限界値を改善することによって、gapはそのまま減少していく可能性が高いです。

Unexplored nodes(未探索ノード)

Unexplored node の数は、分枝操作によって作成されたがまだ処理されていないノードの数を表しています。この数が増え続けている場合、ソルバーはまだ最適性の証明には程遠い可能性が高いといえます。一方で、新しい暫定解を発見することで探索木の大部分が限定操作を受け、この数が突然減少することもあります。

さらに詳しく

MIPツリー(分枝限定木)のサイズ、ひいてはモデルを解くための残り時間を推定することは、現在も続いている研究テーマです。さらなる研究の出発点としては次のような記事があります：