python - ILPを行う際の複数のソリューション

Question

現在PuLP、最大化問題を解決するために使用しています。正常に動作しますが、1 つだけではなく N ベスト ソリューションを取得できるようにしたいと考えています。PuLPまたは他の無料/Pythonソリューションでこれを行う方法はありますか? 最適な解からいくつかの変数をランダムに選択し、それらを破棄して再実行するというアイデアをいじりましたが、これは完全なハックのようです。

Answer 1

問題がすぐに解決できる場合は、上記の目的を段階的に制限してみてください。たとえば、最適解の目的値が の場合、X制約を追加して問題を再実行してみてください。

problem += objective <= X - eps, ""

ここで、縮小ステップepsは問題に関する知識に依存します。

もちろん、epsやみくもにいくつかを選んで解を得た場合、その解が 2 番目に優れているか、10 番目に優れているか、1000 番目に優れているかはわかりません。パラメータ (問題のeps解決が本当に速い場合)。

Answer 2

それで、（RTFMで）複数のソリューションを取得する方法を見つけました。私のコードには、基本的に次のものがあります。

number_unique = 1  # The number of variables that should be unique between runs

model += objective
model += constraint1
model += constraint2
model += constraint3

for i in range(1,5):
    model.solve()
    selected_vars = []
    for p in vars:
         if p_vars[p].value() != 0:
             selected_vars.append(p)
    print_results()

    # Add a new constraint that the sum of all of the variables should
    # not total up to what I'm looking for (effectively making unique solutions)
    model += sum([p_vars[p] for p in selected_vars]) <= 10 - number_unique

これはうまく機能しますが、本当にランダムなルートをたどる必要があることに気付きました。私は10個の異なる変数を持っていますが、そのうちのいくつかを捨てるだけで、私のソリューションはすべての順列で同じ重い重みの変数を持つ傾向があります(これは予想されることです)。