julia - 如何使用 JuMP 寻求 MIP 的第二最佳解决方案

Question

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

这可能是另一个同样最佳的解决方案，或者这可能是一个更糟糕的解决方案，或者可能是:Infeasible——可能没有大多数解决方案。

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

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

Answer 1

可以添加一个cut来禁止刚刚找到的最优解再次求解。假设您的模型有二元变量x(i)。令a(i):=x*(i) 为之前找到的最优解。然后添加线性约束:

sum(i, x(i) * a(i)) - sum(i, x(i) * (1-a(i))) <= sum(i, a(i)) - 1

再次求解。 (这个东西源自 here )。如果x是一个一般的整型变量，事情就会变得更加复杂。

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