python - 进行 ILP 时的多种解决方案

Question

目前我正在PuLP用来解决最大化问题。它工作正常，但我希望能够获得 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 个不同的变量，并且只扔掉其中的几个，我的解决方案往往在所有排列中都具有相同的权重变量（这是意料之中的）。