Try our new documentation site (beta).
Finding Multiple Solutions
By default, the Gurobi MIP solver will try to find one proven optimal solution to your model. It will typically find multiple sub-optimal solutions along the way, which can be retrieved later (using the SolutionNumber parameter, and the Xn and PoolObjVal attributes). However, these solutions aren't produced in a systematic way. The set of solutions that are found depends on the exact path the solver takes through the MIP search. You could solve a MIP model once, obtaining a set of interesting sub-optimal solutions, and then solve the same problem again with different parameter settings, and find only one optimal solution or a different set of sub-optimal solutions.
If you'd like more control over how solutions are found and retained, the Gurobi Optimizer has a number of parameters available for this. The first and simplest one is PoolSolutions, which controls the size of the solution pool. Changing this parameter won't affect the number of solutions that are found - it simply determines how many of those are retained.
You can use the PoolSearchMode
parameter to control the approach used to find multiple solutions. In its
default setting (0), the MIP search simply aims to find one optimal
solution. Setting the parameter to 1 causes the MIP search to expend
additional effort to find more solutions, but in a non-systematic way, and
with no guarantee on the quality of these solutions:
you will get more solutions, but not necessarily the best solutions.
Setting the parameter to 2 causes the MIP to do a systematic search
for the n
best solutions. For both non-default settings, the
PoolSolutions parameter
sets the target for the number of solutions to find.
If you are only interested in solutions that are within a certain gap of the best solution found, you can set the PoolGap parameter. Solutions that are not within the specified gap are discarded.
Obtaining an OPTIMAL
optimization return status when using
PoolSearchMode=2
indicates that the MIP solver succeeded in
finding the desired number of best solutions, or it proved that the
model doesn't have that many distinct feasible solutions. If the
solver terminated early (e.g., due to a time limit), you can use the
PoolObjBound attribute to evaluate
the quality of the solutions that were found. You can find more details
on how to do this later in this section.
There are a few subtleties associated with finding multiple solutions that you should be aware of. For example, the notion of finding the best solutions can be a bit ambiguous when you have a non-zero optimality tolerance. Also, it isn't obvious whether two solutions should be considered different when the model has continuous variables. We'll discuss these issues later in this section.