There are a few subtleties associated with finding multiple solutions that we'll cover now.
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.
The interplay between the optimality gap
MIPGapAbs) and multiple solutions
can be a bit subtle. When using the default
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 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 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 best would improve on the objective for the worst among the 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
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.
One limitation that we should point out related to multiple solutions
is that the distributed MIP solver has not been extended to support
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 best solutions.