Multiple ILP Decisions

Question

I am currently using PuLP to solve the maximization problem. It works great, but I would like to get N-better solutions instead of one. Is there a way to do this in PuLP or any other free / Python solution? I played with the idea of ​​just randomly selecting some variables from the optimal solution and throwing them away and restarting, but this seems like a general hack.

Answer 1

So, I figured out how (via RTFM) to get multiple soutions. In my code, I 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 fine, but I realized that I really need to go a random route. I have 10 different variables, and just throwing a couple of them out, my solutions tend to have the same weighted weights in all permutations (as you would expect).

Answer 2

If your problem is quickly resolved, you can try to limit the target from above. For example, if the objective value of the optimal solution is X , try restarting the problem with an additional restriction:

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

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

Of course, if you just pick eps blindly and get a solution, you don’t know if the solution is second best, 10th best or 1000th best ... But you can do a systematic search (binary, grid) by eps parameter (if the problem is really quickly resolved).