How to request the second best MIP solution using JuMP

Question

I have a problem with mixed whole programming. I can use JuMP to find the best solution. But how can I find the second best solution? Or the third best, etc.

This could potentially be another equally optimal solution, or it could be the worst solution, or maybe :Infeasiblethere could be most solutions.

I know that for a TSP-like problem, I can find additional solutions by gradually removing links that are on the optimal path (I. setting the distance between some cities to be infinite). For a task like Schedualling, I can also progressively set the availability of time slots used in the optimal way to be prohibited.

But is there a general way to do this without coding for yourself specific methods of rejecting this decision?

Answer 1

You can add a cut to prohibit what was found and to solve the optimal solution again. Let's say your model has binary variables x(i) . Let be the a(i):=x*(i)optimal solution found earlier. Then add a linear constraint :

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

and decide again. (This item is received here ). If xis a general integer variable, things get complicated.

, Cplex Gurobi, -, , .