CPXXpopulate and CPXpopulate

Description

The routine CPXXpopulate/CPXpopulate generates multiple solutions to a mixed integer programming (MIP) problem.

The algorithm that populates the solution pool works in two phases.

In the first phase, it solves the problem to optimality (or some stopping criterion set by the user) while it sets up a branch and cut tree for the second phase.

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.

The amount of preparation in the first phase and the intensity of exploration in the second phase are controlled by the solution pool intensity (CPXPARAM_MIP_Pool_Intensity).

Optimality is not a stopping criterion for the populate procedure. Even if the optimality gap is zero, this routine will still try to find alternative solutions. The stopping criteria for CPXXpopulate/CPXpopulate are these:

• Populate limit (maximum number of solutions generated for solution pool by populate) (CPXPARAM_MIP_Limits_Populate) This parameter controls how many solutions are generated before stopping. Its default value is 20.
• Time limit parameter (optimizer time limit in seconds) (CPXPARAM_TimeLimit) operates as in standard MIP optimization.
• Deterministic time limit parameter (deterministic time limit) (CPXPARAM_DetTimeLimit) also operates as in standard MIP optimization.
• Node limit parameter (MIP node limit) (CPXPARAM_MIP_Limits_Nodes) also operates as in standard MIP optimization.
• In the absence of other stopping criteria, CPXXpopulate/CPXpopulate stops when it cannot enumerate any more solutions. In particular, if the user specifies an objective tolerance with the relative or absolute solution pool gap parameters, CPXXpopulate/CPXpopulate stops if it cannot enumerate any more solutions within the specified objective tolerance. However, there may exist additional solutions that are feasible, and if the user has specified an objective tolerance, those feasible solutions may also satisfy this additional criterion. (For example, there may be a great many solutions to a given problem with the same integer values but different values for continuous variables.) Depending on the setting of the solution pool intensity parameter (CPXPARAM_MIP_Pool_Intensity), CPXXpopulate/CPXpopulate may or may not enumerate all possible solutions. Consequently, CPXXpopulate/CPXpopulate may stop when it has enumerated only a subset of the solutions satisfying your criteria.

Successive calls to CPXXpopulate/CPXpopulate create solutions that are stored in the solution pool. However, each call to CPXXpopulate/CPXpopulate applies only to the subset of solutions created in the current call; the call does not affect the solutions already in the pool. In other words, solutions in the pool are persistent.

The user may call this routine independently of any MIP optimization of a problem (such as CPXXmipopt/CPXmipopt). In that case, CPXXpopulate/CPXpopulate carries out the first and second phase itself.

The user may also call CPXXpopulate/CPXpopulate after CPXXmipopt/CPXmipopt. The activity of CPXXmipopt/CPXmipopt constitutes the first phase of the populate algorithm; CPXXpopulate/CPXpopulate then re-uses the information computed and stored by CPXXmipopt/CPXmipopt and thus carries out only the second phase.

CPXXpopulate/CPXpopulate does not try to generate multiple solutions for unbounded MIP problems. As soon as the proof of unboundedness is obtained, CPXXpopulate/CPXpopulate stops.

Arguments

env

A pointer to the CPLEX environment as returned by CPXXopenCPLEX/CPXopenCPLEX.

lp

A pointer to the CPLEX problem object as returned by CPXXcreateprob/CPXcreateprob.

Return

Example

 status = CPXpopulate (env, lp);
 

For more detail about populate, see also the chapter titled Solution Pool: Generating and Keeping Multiple Solutions in the CPLEX User's Manual.