做ILP时的多种解决方案

Question

目前我正在使用 PuLP 来解决最大化问题。它工作正常，但我希望能够获得 N 种最佳解决方案，而不仅仅是一个。在 PuLP 或任何其他 free/Python 解决方案中有没有办法做到这一点？我玩弄了从最优解中随机选择一些变量并将它们扔掉并重新运行的想法，但这似乎完全是 hack。

Answer 1

所以我弄清楚了如何（通过 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 个不同的变量，并且只丢弃其中的几个，我的解决方案往往在所有排列中都具有相同的权重变量（这是可以预料的）。

Answer 2

如果你的问题解决的很快，可以尝试逐步限制上面的objective。例如，如果最优解的 objective 值为 X，请尝试使用附加约束重新运行问题：

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

减少步骤 eps 取决于您对问题的了解。

当然，如果你只是盲目地挑选一些eps并得到一个解决方案，你不知道这个解决方案是第2最好的，第10最好的还是第1000最好的......但是你可以对 eps 参数进行一些系统搜索（二进制、网格）（如果问题真的很快就能解决）。

做ILP时的多种解决方案

Multiple solutions when doing ILP

python

numpy

scipy

pulp