如何使用 JuMP 请求 MIP 的次优解决方案 [英] How to ask for second best solution to a MIP using JuMP

问题描述

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

I have a Mixed Integer Programming problem. I can use JuMP to find the optimal solution. But how can I find the second best solution? Or the third-best etc.

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

This potentially might be another equally optimal solution, or it might be a worse solution, or it might be :Infeasible -- there might be no most solutions.

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

I know for a TSP-like problem, I can find additional solutions by progressively removing links that are on the optimal path (I.e setting the distances between some of the cities to be infinite). For a schedualling type problem, I can similarly progressive set the availabilities of the timeslots used in the optimal path to be forbidden.

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

But is there a general way of doing this, without coding up myself problem specific methods for disallowing this solution?

推荐答案

你可以加一个cut来禁止刚刚找到的最优解，然后再求解.假设您的模型具有 二元变量 x(i).让 a(i):=x*(i) 成为之前找到的最优解.然后添加 linear 约束:

You can add a cut to forbid the optimal solution just found and solve again. Say your model has binary variables x(i). Let a(i):=x*(i) be the optimal solution found earlier. Then add the linear constraint:

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

然后再次解决.(这个东西来源于here).如果 x 是一个通用的整数变量，事情就变得更复杂了.

and solve again. (This thing is derived here). If x is a general integer variable, things become more complicated.

Cplex 和 Gurobi 等一些求解器也有一个称为解池的东西，它也可以做到这一点.

Some solvers like Cplex and Gurobi also have something called a solution pool which also can do this.

这篇关于如何使用 JuMP 请求 MIP 的次优解决方案的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！