N-bestな解を取得するには？

MIPの場合

MIPについてはSolution Pools に探索中で見つかった解の中でN-bestとなる解が保持されます。NはPoolSolutions パラメータで指定されます。また、PoolGapを利用することで、最適解から一定のGAPを持つ解に制限することも可能です。

LPの場合

Solution Pool はMIPに対して設計されたものであり、LPに対しては複数の解を保持しません。

LPが無限に多くの最適解を持つ場合、その扱いは複雑であり、複数の解を得るためには、手作業によるアルゴリズムやヒューリスティックが必要となります。一例として、最適なファセットの全頂点の計算（これは一般的に非常に重たい処理です）に注目する方法があります。

最適なファセットの頂点の計算（例）

1. 非ゼロのDual Valueを持つすべての不等式制約を等式制約に変える。
2. 非ゼロのReduced Costを持つ全ての変数をその最適解の値に固定する。これにより、より単純なLPが得られる。
3. 固定されていない変数の目的関数における係数を変更し、再度最適化を行う。これにより、最適ファセットの異なる頂点が得られる可能性がある。

このアプローチは数値的に不安定なモデルではうまくいかない可能性があることにご注意ください。Gurobiは有限精度で動作するため、例えばある値を0でないと判定するときなどに、数値的不安定性の影響を強く受けます。

その他の資料

•  レファレンスマニュアル: Solution pool