Solution Pool and Multi-Scenario Logging

Populating a solution pool or solving for multiple scenarios involves looking for more than one solution, which leads to different logging output. In particular, logging for these methods comes in two phases. In the first, the log shows progress towards finding one provably optimal solution (for multi-scenario optimization, this is the best solution over all scenarios). The log for this first phase is identical to the standard MIP log. It shows progress in the lower and upper bounds, and the phase terminates when these are sufficiently close to each other.

The second phase starts once attention has shifted towards finding solutions beyond that one optimal solution. You will see a message indicating that a new phase has begun. When populating a solution pool, you will see:

Optimal solution found at node 7407 - now completing solution pool...

When solving for multiple scenarios, you will see:

Optimal solution found at node 15203 - now completing multiple scenarios...

You will also see an additional header, which is slightly different from the standard MIP header. For a solution pool:

   Nodes    |    Current Node    |      Pool Obj. Bounds     |     Work
            |                    |   Worst                   |
Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

For multiple scenarios:

   Nodes    |    Current Node    |    Scenario Obj. Bounds   |     Work
            |                    |   Worst                   |
Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

The most important difference versus the standard header is in the Incumbent column. In the standard MIP log, this column shows the objective value for the best solution found so far. For a solution pool or multiple scenarios, this column shows the objective value for the worst solution. This of course isn’t the worst solution ever found. Rather, it shows the objective value for the worst solution among all the solutions that the MIP solver has been asked to find. For example, if you have set the PoolSolutions parameter to 100 to ask for the 100 best solutions, this column will show the objective value for the 100th best solution found so far. If you are solving a multi-scenario model, this column shows the worst solution found over all scenarios. As the search progresses, the value in this column will improve monotonically as the MIP solver replaces this worst solution with better solutions.

One other important difference in this second phase log is in the meaning of the BestBd column. In the standard MIP log, this column gives a bound on the best possible objective value for any solution. In this log, this column shows the best possible objective value for any solution that has not yet been found. To give an example, if a minimization model has a unique optimal solution at objective 100, the second phase will begin once the lower bound reaches 100, and the BestBd column will show a value larger than 100 once the solver has determined that only one solution exists at objective 100.

The BestBd and Incumbent columns allow you to track progress towards completion of the solution pool or multi-scenario solve. Specifically, once the best bound for any solution that has not yet been found reaches the objective value for the worst solution, we know that we can’t improve that solution and we can stop.