MIPs
For MIPs, Solution Pools can be used to find the N best solutions as well as N solutions that are less than a specified gap from the optimal solution.
LPs
Note that the Solution Pool feature is designed for MIPs and will not provide multiple optimal solutions for LPs.
The cases where an LP has infinitely many optimal solutions are complex to handle and require manual algorithms and/or heuristics to get multiple solution points. As an example, one approach may focus on the computation of all vertices of the optimal facet (which is in general very expensive).
We sketch one possibility to compute multiple vertices of the optimal facet.
- Turn all inequality constraints with a non-zero dual value into equality constraints.
- Fix all variables with a non-zero reduced costs value to its optimal solution value. This leads to a new simpler LP.
- Change the objective coefficients of the non-fixed variables and re-optimize. Then, you might get a different vertex of the optimal facet.
Please note that this idea does not work well for numerically challenging models because Gurobi works with finite precision meaning that you have to decide when you define a value as non-zero, e.g., should a value of 10^-8 be handled as 0 or not?
Further information
- Solution pool section in the Reference Manual