如何使用JuMP请求一个MIP的次优解决方案

Question

8

我有一个混合整数规划问题。我可以使用JuMP找到最优解。但是如何找到第二好的解？或者第三好的等等。

这可能是另一个完全相同的最优解，也可能是一个更差的解，或者它可能是:Infeasible -- 没有最优解。

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

但是否有一种通用方法来做到这一点，而不需要编写针对特定问题的方法来禁止此解？

- Frames Catherine White

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Erwin Kalvelagen · Accepted Answer

你可以添加一个截断来禁止刚刚找到的最优解，并重新求解。假设你的模型有二进制变量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还有一个叫做解池(solution pool)的功能，也可以做到这一点。