This general question popped into my mind if finding all optimal solutions takes not much more time than finding just one optimal solution in a MILP why not gettting all of them in Gurobi?

  • 3
    $\begingroup$ It can be expensive and there may be a ton of solutions. Gurobi (and Cplex) don't solve from scratch for this. $\endgroup$ Commented Apr 30 at 18:58
  • 2
    $\begingroup$ Generally, finding all optimal solutions is obviously at least as difficult as solving the problem (finding one optimal solution). But you can easily think of polynomially solvable problems, where finding all optimal solutions is intractable (exponentially many feasible solutions and constant objective) $\endgroup$
    – Sune
    Commented Apr 30 at 19:00
  • $\begingroup$ @ErwinKalvelagen Thank you for reply. But theorically I would like to know if the second optimal solution requires solving a MILP again? or just by some different type of mathematical operation one could come up with the second optimal solution? $\endgroup$
    – Red shoes
    Commented Apr 30 at 19:38
  • $\begingroup$ As said before, the solution pool does not run a second MIP from scratch. See: Danna E., Fenelon M., Gu Z., Wunderling R. (2007) Generating Multiple Solutions for Mixed Integer Programming Problems. In: Fischetti M., Williamson D.P. (eds) Integer Programming and Combinatorial Optimization. IPCO 2007. Lecture Notes in Computer Science, vol 4513. Springer, Berlin, Heidelberg $\endgroup$ Commented Apr 30 at 19:45
  • 1
    $\begingroup$ It goes much deeper than using the solution, it reuses the tree. $\endgroup$ Commented May 1 at 9:26


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.