GurobiでLazy constraintsを扱うには？

MIPモデルに対して、Lazy constraints(遅延制約) を実装するためには以下の2つの方法があります。

1. 制約を前もって列挙する場合：Lazy constraints として扱いたい制約式の Lazy 属性を設定します。 
2. MIPの探索中に追加する場合： LazyConstraint パラメータを1に設定したうえで、コールバック関数を利用する必要があります。詳細はそれぞれのAPIのレファレンス (Model.cbLazy()等) に記載されていますが、例えばコールバックを使って遅延制約を追加する例として、巡回セールスマン問題(TSP)の例があります(Gurobiをインストールした際のexamplesディレクトリはサンプルコードもあります)。

上記２つの方法にはいくつか注意すべきトレードオフの関係があります。

• メモリー： 通常、扱いたい問題の制約サイズのオーダーによって、制約を前もって列挙できるかどうかが決まります。TSPを例に考えてみます。よく知られているモデルのうちの一つでは、都市のペアごとに変数を作成し、各都市が他の2つの都市に接続されていることを保証する制約を定義します。また、サブツアーが発生しないことを保証するために指数オーダーの制約を必要とします。例えば50都市の比較的小さなインスタンスでさえ、必要なサブツアー除去制約の数は非現実的な数であるため、事前に列挙するのではなくコールバック関数を通して逐次追加する必要が出てきます。そうでない場合、マシンのメモリ不足が容易に起こりえます。
• 使いやすさ：得られた解が制約に違反するかどうかを調べて、その違反を修正するために適切な制約を追加するコールバック関数を書くことは手間のかかる作業であり、ユーザにとって開発時間のかかることです。もし制約を前もって列挙することができれば、Gurobiが必要な制約を自動で追加してくれるので自前でコールバック関数を開発する労力を費やす必要がありません。
• 制御しやすさ： コールバック関数を書くことで、どの制約がモデルに追加され、MIP探索中のどの時点で追加されるかをユーザーが完全にコントロールできます。Lazy constraintsを事前に列挙する場合では、ユーザーは積極的に関与することができません。例えば追加される制約は、MIPの実行可能解を切り捨てるためにのみ使用されます。つまり、線形緩和を強化するために使用することはできません。ただし、Lazy 属性を使用して、Gurobiがどの程度積極的に制約をモデルに追加するかをユーザーが指定することは可能です：

Lazy=1では、あるLazy constraint は実行可能解を取り除くするために使われますが、他にもその解を取り除くような Lazy constraintsがある場合、必ずしもそのすべてが追加されるわけではありません。Lazy=2では、ある実行可能解において違反しているすべてのLazy constraintsが、モデルに追加されます。Lazy=3では、ルートノードにおける緩和解を取り除くLazy constraintsも追加されます。

• 通信のオーバーヘッド： Gurobi Instant Cloud と Gurobiの Compute Server はどちらもクライアント-サーバーの枠組みで動きます。モデルはあるマシン（クライアント）でGurobi APIを通して構築されますが、実際には別のマシン（サーバー）で求解されます。 このような場合に、コールバック関数はクライアントマシン上で実行されることに注意が必要です。コールバック関数が頻繁に呼び出される場合、クライアント-サーバー間で追加の通信が必要となるため、通信時間の問題が発生する可能性があります。

連続モデル（LP、QP、SOCP）では、Lazy constraints をサポートしていません。連続モデルにLazy constraints相当のもの を追加するには、そのモデルが解けるまで待つか手動で止め、新しい制約を追加し、再び解き始める必要があります。

その他の資料

• What is the difference between user cuts and lazy constraints?
• TSP example