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 you multiple optimal solutions for LPs.
The rare 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 of how to compute multiple vertices of the optimal facet.
- First, turn all inequality constraints with a non-zero dual value into equality constraints.
- Next, fix all variables with a non-zero reduced costs value to its optimal solution value. This provides you a new simpler LP.
- Now by changing the objective coefficients of the non-fixed variables and re-optimizing, you will get a different vertex of the optimal facet.
Please note that this idea does not work well for numerically challenging models because the Gurobi algorithm works with finite precision meaning that you have to decide when you define a value as non-zero, e.g., you decide whether a value of 10^-8 shall be handled as 0 or not.
Further information
- Solution pool section in the Reference Manual