How to ask for second best solution to a MIP using JuMP

Question

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.

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.

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?

Answer 1

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

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

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