Example: calling populate

Shows an example of the populate procedure in the Interactive Optimizer.

You can generate multiple solutions with populate. To see this effect in the Interactive Optimizer, first read the example cited in Example: simple facility location problem, like this:

read location.lp
populate

At default settings in the Interactive Optimizer, you will see results such as these:

Populate: phase I
Tried aggregator 1 time.
MIP Presolve eliminated 3 rows and 3 columns.
MIP Presolve modified 47 coefficients.
Reduced MIP has 49 rows, 40 columns, and 148 nonzeros.
Presolve time =    0.01 sec.
Clique table members: 45.
MIP emphasis: balance optimality and feasibility.
Root relaxation solution time =    0.04 sec.

        Nodes                                         Cuts/
   Node  Left     Objective  IInf  Best Integer     Best Node    ItCnt     Gap

      0     0      452.1107    27                    452.1107       51
*     0+    0                          549.0000      452.1107       51   17.65%
      0     0      468.2224    23      549.0000      Cuts: 17       64   14.71%
*     0+    0                          512.0000      468.2224       64    8.55%
      0     0      470.5942    23      512.0000       Cuts: 2       68    8.09%
      0     0      470.6800    20      512.0000       Cuts: 3       70    8.07%
      0     2      470.6800    20      512.0000      470.6800       70    8.07%
*    10     6      integral     0      499.0000      479.9271      129    3.82%

Cover cuts applied:  2
Zero-half cuts applied:  2
Gomory fractional cuts applied:  1

Populate: phase II
MIP emphasis: balance optimality and feasibility.
    100    26    infeasible            499.0000      500.0000      234   -0.20%

Cover cuts applied:  2
Zero-half cuts applied:  2
Gomory fractional cuts applied:  1

Solution pool: 20 solutions saved.

Populate - Populate solution limit exceeded, integer optimal:  Objective =  4.9900000000e+02
Solution time =    0.54 sec.  Iterations = 261  Nodes = 193 (34)

In that log, you see that the procedure executed its first and second phases. It reports parameter settings, such as MIP emphasis, like other optimization logs. It also reports how many solutions it found. It stops when it reaches the populate limit. (In this example, the populate limit rests at its default, 20 solutions.)

Interestingly, the gap printed in that log becomes negative in the second phase of populate. At the end of the first phase of populate, the model was solved to optimality; the best node value and the best integer value coincided and were equal to the optimal objective value; the gap was zero. Early in the second phase, the best integer value remained equal to the optimal objective value, but as populate progressed, nodes were explored and fathomed. At some point, all nodes with a relaxation value equal to the optimal objective value were fathomed. This fathoming explains why the best node value increased above the optimal objective value (for a minimization problem, such as this example) as the search space was explored in the second phase. Recall that the gap value is computed as:

(bestInteger-bestBound)*objSense/(abs(bestInteger)+1e-10)

Consequently, the gap can become negative. A negative gap value ( -g% ) indicates that the search space explored by populate does not contain any more solutions that are less than g% worse than the optimal objective value.

You can invoke the populate procedure multiple times. In successive invocations, it will re-use information it has accumulated in previous invocations. For example, if you then immediately invoke populate a second time on this model, it re-uses the information it gathered in the previous invocation to resume its second phase, like this:

CPLEX> populate

Populate: phase II
MIP emphasis: balance optimality and feasibility.
    200    32    infeasible            499.0000      512.0000      268   -2.61%
    300    38    infeasible            499.0000      514.0000      282   -3.01%
    400    44      516.0000     1      499.0000      516.0000      295   -3.41%
    500    48      518.0000     1      499.0000      518.0000      312   -3.81%

Cover cuts applied:  2
Zero-half cuts applied:  2
Gomory fractional cuts applied:  1

Solution pool: 40 solutions saved.

Populate - Populate solution limit exceeded, integer optimal:  Objective =  4.9900000000e+02
Solution time =    0.23 sec.  Iterations = 320  Nodes = 532 (53)

In this second invocation, populate does not disturb the twenty solutions already accumulated in the solution pool, and it continues to search for another twenty solutions before stopping at its default limit again.

The status line of both invocations of populate indicates that the optimal solution of the model has been found. Nevertheless, populate continues to produce solutions: optimality is not the stopping criterion for populating the solution pool. For more detail about stopping criteria, see Stopping criteria for the populate procedure.