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 the optimal solution.
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 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 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.
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. This attribute gives a
bound on the objective of any solution that isn't already in the
solution pool. The difference between this attribute and
ObjBound is that the latter gives a
bound on the objective for any solution, and which is often looser
than PoolObjBound.
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.
