ILOG CPLEX 11.0 User's Manual > Discrete Optimization > Solution Pool: Generating and Keeping Multiple Solutions > Populating the Solution Pool > Example: Calling Populate |
Example: Calling Populate |
INDEX PREVIOUS NEXT |
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:
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 (20 solutions in this example).
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:
(best integer - best node ) * objsen / (abs (best integer) + 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 begin its second phase, like this:
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.
Copyright © 1987-2007 ILOG S.A. All rights reserved. Legal terms. | PREVIOUS NEXT |