JuMPを使用してMIPの次善策を求める方法

Question

混合整数プログラミングの問題があります。 JuMPを使用して最適なソリューションを見つけることができます。 しかし、次善策を見つけるにはどうすればよいですか？ またはサード最良など

これは潜在的に 、別の平等に最適なソリューションかもしれませんか、それは悪いことソリューション、 かもしれませんか、それは:Infeasibleかもしれない - 何のほとんどのソリューションは存在しないかもしれません。

私はTSPのような問題があることを知っていますが、最適な経路にあるリンクを徐々に削除することで追加の解決策を見つけることができます（いくつかの都市間の距離を無限に設定します）。 scheduallingタイプの問題については、最適パスで使用されるタイムスロットの使用可能性を禁止するように同様にプログレッシブ設定できます。

しかし、このソリューションを許可しないという問題の具体的な方法をコーディングすることなく、これを行う一般的な方法はありますか？

Answer 1

見つけたばかりの最適解を禁止するようにカットを追加して、もう一度解くことができます。モデルにバイナリ変数x(i)があるとします。先に見つけた最適解をa(i):=x*(i)とする。そして、リニア制約を追加：

sum(i, x(i) * a(i)) - sum(i, x(i) * (1-a(i))) <= sum(i, a(i)) - 1 

をして、再度解きます。 （これは、hereから派生したものです）。 xが一般的な整数変数である場合、事態はより複雑になります。

CplexやGurobiのようなソルバーには、解決策プールと呼ばれるものもあります。