MIPスタート(初期解)を使うには？

オリジナルURL：How do I use MIP starts?

Gurobiに対して、初期実行可能解(MIPスタート)を与えることで、全体の求解時間が削減されることがあります(ただし、必ず改善するとは保証されません)。MIPスタートは変数オブジェクトの Start 属性を使うか、.mstファイル、.solファイルを読み込むことで利用可能です。

バイナリ変数と整数変数の（一部の）値のみを設定し、残りの変数の値の計算をGurobiにさせることも可能です。これは、全変数に対するMIPスタートが少量だけ制約に違反し、それによって初期解が受理されないような場合に有用です。

関連するオプションとして、Variable hints があります。この値は、求解プロセス全体を通してソルバーを誘導します。ある変数が許容解において特定の値を持つ可能性が高いことが分かっている場合、variable hint を設定することで、Gurobiが解を見つけるために役立つことがあります。

複数のMIPスタートを使う

Gurobiに対して複数の実行可能なMIPスタートを提供することが可能です。この操作はAPIまたはコマンドラインツールから行うことができます。ただし、今のところ多目的問題に対して複数のMIPスタートを追加することはサポートされていません。

APIからは、 NumStart 属性と StartNumber パラメータを使用して、複数のMIP Startを指定することができます。例えば、Python APIでは以下のようになります：

model.NumStart = 2
model.update()

# 複数のMIP startsを反復
for s in range(model.NumStart):
  
  # set StartNumber
  model.params.StartNumber = s

  # now set MIP start values using the Start attribute, e.g.:
  for v in model.getVars():
    v.Start = <value>

gurobi_cl を使う場合、引数としてInputFile を複数回与えます。

gurobi_cl InputFile=mipstart1.mst InputFile=mipstart2.mst model.mps

どちらの場合でも、与えられたMIPスタートをそれぞれ検証し、最も良いものが採用されます。

部分的な初期解の補完

StartNodeLimit パラメータは、部分的な初期解を与えた時にその補完を行うために探索される分枝ノードの数を制御できます。デフォルトでは、SubMIPNodesと同じ値が使用されます。

その他の資料

• MIP Start documentation