Solution Pool#
While the default goal of the Gurobi Optimizer is to find one proven optimal solution to your model, with a possible side-effect of finding other solutions along the way, the solver provides a number of parameters that allow you to change this behavior.
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 \(n\) 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.
Retrieving Solutions#
After optimization has completed, you can retrieve solutions from the solution pool using a few parameters and attributes. The SolCount attribute indicates how many solutions were retained by the MIP solver. The best solution can always be obtained through the X attribute. Sub-optimal solutions can be obtained by first setting the SolutionNumber parameter and then querying the Xn attribute to obtain the solution or the PoolObjVal attribute to obtain the objective value for the corresponding solution.
Solutions in the solution pool are ordered from best to worst. For example, to
retrieve the worst solution kept by the MIP solver, you’d first query
SolCount to determine how many solutions are available, then set
the SolutionNumber parameter to SolCount-1, then query the
Xn attribute.
The PoolObjBound attribute gives a bound on the objective value of undiscovered solutions (i.e., of solutions that aren’t already in the solution pool). Further tree exploration won’t find solutions having a better objective value than PoolObjBound.
The difference between this attribute and ObjBound is that the latter gives a bound on the objective for any solution, while PoolObjBound only refers to undiscovered solutions (which are not in the solution pool). PoolObjBound is always at least as tight as ObjBound and it is often strictly tighter than ObjBound if PoolSearchMode=2. If PoolSearchMode=0 or PoolSearchMode=1, then PoolObjBound and ObjBound will always take the same value.
If the solver terminated early (e.g. due to reaching the time limit), you can still use the attribute PoolObjBound to get a count of how many of the \(n\) best solutions you found: any solutions having objective values that are at least as good as PoolObjBound are among the \(n\) best. This is illustrated in the examples on the next section.
Examples#
Parameter usage#
Let’s continue with a few examples on how the parameters related to solution pools would be used. Imagine that you are solving a MIP model with an optimal (minimization) objective of 100. Further imagine that, using default settings, the MIP solver finds four solutions to this model with objectives 100, 110, 120, and 130.
If you set the PoolSolutions parameter to 3 and solve
the model again, the MIP solver would return with 3 solutions in the
solution pool (i.e., the SolCount attribute would have value
3). If you instead set the PoolGap parameter to value
0.2, the MIP solver would discard any solutions whose objective
value is worse than 120 (which would also leave 3 solutions in the
solution pool).
If you set the PoolSearchMode parameter to 1 and the PoolSolutions parameter to 10, the MIP solver would continue running after having found an optimal solution trying to find and store 10 solutions, but with no guarantee on the quality of the additional solutions.
If you set the PoolSearchMode parameter to 2 and the PoolSolutions parameter to 10, the MIP solver would attempt to find the 10 best solutions to the model. An OPTIMAL return status would indicate that either (i) it found the 10 best solutions, or (ii) it found all feasible solutions to the model, and there were fewer than 10. If you also set the PoolGap parameter to a value of 0.1, the MIP solver would try to find 10 solutions with objective no worse than 110. While this may appear equivalent to asking for 10 solutions and simply ignoring those with objective worse than 110, the solve will typically complete significantly faster with this parameter set, since the solver does not have to expend effort looking for solutions beyond the requested gap.
Interpreting attribute information#
Let’s try to better understand the attributes related to solution pools. Consider again a minimization problem where the parameter settings PoolSearchMode=2 and PoolSolutions=10 have been used.
First, imagine that the solver terminated with an OPTIMAL return status. We look at several possible hypothetical values of some attributes:
Case 1:
ObjVal=100,ObjBound=100,PoolObjBound=500, and the objective value of the 10th solution in the pool is 500.The first solution in the pool is optimal (because ObjVal and ObjBound are equal), and the solver was able to find 10 solutions of value at most 500. Because
PoolObjBound=500, we know that all solutions that the solver did not find have an objective value of at least 500. Since the last solution in the pool has value 500, the 10 solutions in the pool are definitely the 10 best solutions.Case 2:
ObjVal=100,ObjBound=100,PoolObjBound=+infinity,SolCount=7, and the values of the 7th and 8th solutions in the pool are 350 and+infinity, respectively.The solver has found 7 solutions and has proven that no other feasible solution for the model exists. The best of these 7 solutions has objective 100, the worst of them has objective 350.
Now, imagine that the solver terminated early due to a time limit (return status TIME_LIMIT). Again, we look at several possible hypothetical values of some attributes:
Case 3:
ObjVal=100,ObjBound=50,PoolObjBound=50Since ObjBound < ObjVal, the solver did not prove optimality of the incumbent solution (the first solution in the pool). There can be better solutions than the incumbent.
Case 4:
ObjVal=100,ObjBound=100,PoolObjBound=100, and the objective value of the 10th solution in the pool is 500.The first solution in the pool is optimal (because ObjVal and ObjBound are equal), and the solver was able to find 10 solutions with objective value at most 500. Because
PoolObjBound=100, we know that all solutions that the solver did not find have an objective value of at least 100. Since the value of the last solution in the pool is 500, it could be the case that there exist 10 or more solutions with objective smaller than 500 (but greater than or equal to 100). In particular, solutions that are currently in the pool and have objective value greater than 100 might not be among the 10 best solutions.Case 5:
ObjVal=100,ObjBound=100,PoolObjBound=200, and the objective values of the 4th, 5th and 10th solutions in the pool are 180, 220 and 500, respectively.The first solution in the pool is optimal (because ObjVal and ObjBound are equal), and the solver was able to find 10 solutions of value at most 500. Because
PoolObjBound=200, we know that all solutions that the solver did not find have an objective value of at least 200. This means that the first 4 solutions in the pool (up to the solution with value 180) are definitely the best four solutions that exist. The 5th solution with value 220 (and subsequent solutions in the pool) may be inferior to other undiscovered solutions.
Subtleties and Limitations#
There are a few subtleties associated with finding multiple solutions that we’ll cover now.
Continuous Variables#
One subtlety arises when considering multiple solutions for models with continuous variables. Specifically, you may have two solutions that take identical values on the integer variables but where some continuous variables differ. By choosing different points on the line between these two solutions, you actually have an infinite number of choices for feasible solutions to the problem. This might be an issue, because the solution pool could be filled with solutions that only differ in the values of continuous variables but are otherwise equivalent, providing little interesting information. To avoid this issue, we define two solutions as being equivalent if
in the presolved space, the integer variables and continuous variables participating in SOS and bilinear constraints assume the same values, or
in the original model space, all variables assume the same values.
A solution will be discarded if it is equivalent to another solution that is already in the pool.
Optimality Gap#
The interplay between the optimality gap (MIPGap or MIPGapAbs) and multiple solutions can be a bit subtle. When using the default PoolSearchMode, a non-zero optimality gap indicates that you are willing to allow the MIP solver to declare a solution optimal, even though the model may have other, better solutions. The claim the solver makes upon termination is that no other solution would improve the incumbent objective by more than the optimality gap. Terminating at this point is ultimately a pragmatic choice - we’d probably rather have the true best solution, but the cost of reducing the optimality gap to zero can often be prohibitive.
This pragmatic choice can produce a bit of confusion when finding multiple optimal solutions. Specifically, if you ask for the \(n\) best solutions, the optimality gap plays a similar role as it does in the default case, but the implications may be a bit harder to understand. Specifically, a non-zero optimality gap means that you are willing to allow the solver to declare that it has found the \(n\) best solutions, even though there may be solutions that are better than those that were returned. The claim in this case is that any solution not among the reported \(n\) best would improve on the objective for the worst among the \(n\) best by less than the optimality gap.
If you want to avoid this source of potential confusion, you should set the optimality gap to 0 when using PoolSearchMode=2.
Presolve#
Setting the parameter PoolSearchMode to 1 does not guarantee a search among all possible feasible solutions. This is because presolve procedures, such as Symmetry and DualReductions, may eliminate some feasible solutions from the search space, provided that at least one optimal solution remains. Consequently, with PoolSearchMode=1, the number of solutions retrieved might be less than the value specified by the PoolSolutions parameter. This differs from PoolSearchMode=2, where the Gurobi Optimizer is guaranteed to search over the entire feasible space, potentially yielding more solutions.
Logging#
The log for a MIP solve with PoolSearchMode set to a non-default value is different from the standard MIP log. You should consult the section Solution Pool and Multi-Scenario Logging for details.
Distributed MIP#
One limitation that we should point out related to multiple solutions is that the distributed MIP solver has not been extended to support non-default PoolSearchMode settings. Distributed MIP will typically produce many more feasible solutions than non-distributed MIP, but there’s no way to ask it to find the \(n\) best solutions.