julia - 如何使用 JuMP 请求 MIP 的次优解决方案

Question

我有一个混合整数编程问题。我可以使用 JuMP 找到最佳解决方案。但是我怎样才能找到第二好的解决方案呢？或三等奖等。

这可能是另一个同样最优的解决方案，或者它可能是一个更差的解决方案，或者它可能是:Infeasible- 可能没有大多数解决方案。

我知道对于类似 TSP 的问题，我可以通过逐步删除最佳路径上的链接来找到其他解决方案（即将某些城市之间的距离设置为无限）。对于调度类型的问题，我可以类似地逐步设置在最佳路径中使用的时隙的可用性被禁止。

但是有没有一种通用的方法来做到这一点，而无需编写自己的问题特定方法来禁止此解决方案？

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

并再次解决。（这个东西是从这里衍生出来的）。如果x是一个一般的整数变量，事情就变得更复杂了。

一些像 Cplex 和 Gurobi 这样的求解器也有一个叫做解池的东西，它也可以做到这一点。