进行ILP时多个解决方案

Question

当前我正在使用PuLP来解决最大化问题。它运行良好，但是我希望能够获得N最佳解决方案，而不仅仅是一种解决方案。有没有办法在PuLP或任何其他免费/Python解决方案中执行此操作？我想到的想法只是随机从最佳解决方案中挑选一些变量并将其扔掉并重新运行，但这似乎是一个完全的黑客攻击。

Answer 1

如果您的问题快速解决，则可以尝试逐步限制目标。对于审查，如果最佳解决方案的客观值是X，请尝试使用附加约束来重新解决问题：

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

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

当然，如果您只盲目选择一些eps并获得解决方案，那么您不知道该解决方案是第二最好的，第10个最佳还是第1000-最好...但是您可以进行一些系统的搜索（二进制搜索，网格）在eps参数上（如果问题确实很快解决）。

Answer 2

，所以我弄清楚（通过RTFM）如何获得多个Soutions。在我的代码中，我本质上有：

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个不同的变量，只需扔掉几个变量，我的解决方案在所有排列中往往具有相同的重型VAR（可以预料）。