Multiple solutions when doing ILP

Question

Currently I'm using PuLP to solve a maximization problem. It works fine, but I'd like to be able to get the N-best solutions instead of just one. Is there a way to do this in PuLP or any other free/Python solution? I toyed with the idea of just randomly picking some of the variables from the optimal solution and throwing them out and re-running, but this seems like a total hack.

Answer 1

If your problem is fast to solve, you can try to limit the objective from above step by step. For examle, if the objective value of the optimal solution is X, try to re-run the problem with an additional constraint:

problem += objective <= X - eps, ""

where the reduction step eps depends on your knowledge of the problem.

Of course, if you just pick some eps blindly and get a solution, you don't know if the solution is the 2nd best, 10th best or 1000-th best ... But you can do some systematic search (binary, grid) on the eps parameter (if the problem is really fast to solve).

Answer 2

So I figured out how (by RTFM) to get multiple soutions. In my code I essentially have:

number_unique = 1  # The number of variables that should be unique between runs

model += objective
model += constraint1
model += constraint2
model += constraint3

for i in range(1,5):
    model.solve()
    selected_vars = []
    for p in vars:
         if p_vars[p].value() != 0:
             selected_vars.append(p)
    print_results()

    # Add a new constraint that the sum of all of the variables should
    # not total up to what I'm looking for (effectively making unique solutions)
    model += sum([p_vars[p] for p in selected_vars]) <= 10 - number_unique

This works great, but I've realized that I really do need to go the random route. I've got 10 different variables and by only throwing out a couple of them, my solutions tend to have the same heavy weighted vars in all the permutations (which is to be expected).