Algorithm of the populate procedure

Describes the algorithm of the populate procedure.

Briefly, the algorithm that populates the solution pool works in two phases.

In the first phase, it solves the model to optimality (or some stopping criterion set by the user), but it retains nodes that might contain useful, even if not necessarily optimal integer feasible solutions—nodes that would be pruned by the optimality based branch-and-cut algorithm of CPLEX. In other words, it retains nodes that have a feasible relaxation but an objective value worse than the cutoff value, as well as nodes that have an integer feasible relaxation solution without all the integer restricted variables having fixed bounds.

In the second phase, it generates multiple solutions by using the information computed and stored in the first phase and by continuing to explore the tree. Specifically, it branches on the additional nodes retained in the first phase and continues to explore the subtrees associated with these nodes.

The amount of preparation in the first phase and the intensity of exploration in the second phase are controlled by the solution pool intensity parameter:

  • SolnPoolIntensity in Concert Technology;

  • CPX_PARAM_SOLNPOOLINTENSITY in the Callable Library;

  • mip pool intensity in the Interactive Optimizer.

After a model has been read (or created), the first call to populate will carry out both the first and second phase. In the general case, subsequent calls to populate will re-use stored information and proceed with the continuation of the second phase. The first phase will be re-computed if:

  • the value of the pool intensity parameter has increased between successive calls of populate;

  • any filters have been deleted.

The details of the algorithm that populates the solution pool are published in the paper titled "Generating Multiple Solutions for Mixed Integer Programming Problems," by Emilie Danna, Mary Fenelon, Zonghao Gu, and Roland Wunderling, in the Proceedings of the Twelfth Conference on Integer Programming and Combinatorial Optimization (IPCO 2007), LNCS 4513, pages 280 - 294.