Using CPLEX to examine alternate optimal solutions

Answer

Most problems (especially linear programs) drawn from practical sources have more than one optimal solution. Conventionally, CPLEX terminates as soon as it finds an optimal solution to a linear, mixed integer, or quadratic program. It does not attempt to find alternate optimal solutions. Furthermore, the problem of enumerating all optimal solutions to a problem may be more difficult than optimizing the original problem. Nevertheless, CPLEX does provide some useful tools for obtaining information about alternate optimal solutions.

The recommended methods to handle or calculate alternate optimal solutions depend on the CPLEX version and the problem type involved. For users of CPLEX 11 or later with MIPs, the Solution Pool feature provides an easy way to enumerate some or all alternate optimal solutions. For example, to enumerate all optimal solutions, set the solution pool absolute gap to 0 (zero), the solution pool intensity level to its maximum value of 4, the populate limit to 2 100 000 000, and run the populate procedure. Keep in mind that this operation may consume significantly more time than running CPLEX on the same model until it finds a single optimal solution.

The Solution Pool feature introduced in CPLEX 11 is a good reason to upgrade for users who still have earlier versions of CPLEX and need to examine multiple solutions (either optimal or not) in their MIP models. However, for users who have yet to upgrade or have models with only continuous variables, other tactics (described below) are available in some cases. Even so, keep in mind that the methods described below for MIP models will probably take more time to find alternate optimal solutions than the Solution Pool feature.

For linear programs reduced costs of zero for nonbasic variables indicate an alternate optimal basis exists. Furthermore, you can use the routines CPXgetgrad and CPXgetx to determine whether the associated pivot is degenerate (in which case the solution values remain unchanged but the basis changes) or not (in which case both the solution values and the basis change). Note that reduced costs on slack variables are the negative of the associated dual variables.

In addition, the routine CPXaddrows provides a simple way to enumerate alternate optimal solutions. Suppose the optimal objective value of the original problem is z*, and that c'x is the associated objective function. Use CPXaddrows to add the following constraint:

c'x = z*

Since only nonbasic variables with reduced costs of 0 (zero) can change when the application moves from one alternate optimal solution to another, you can also enumerate alternate optimal solutions by using the routines CPXgetdj and CPXgetpi to identify the nonbasic structural variables and slacks with nonzero reduced costs. Then, fix these structural variables to their current values using CPXchgbds, and fix the slack variables with CPXchgsense. Set the simplex iteration limit to 1 (one); change the objective as before; and you can enumerate some, but not all, alternate optimal solutions.

If your problem has binary variables, you can solve a sequence of MIPs where each successive MIP has an additional constraint that excludes the previous optimal solution. Here's the constraint you need to add.

Let x{S} be the binary variables. Suppose you have a binary solution x* in available from the most recent optimization. Let N be the subset of S such that x*[n] = 1 for all n in N

Then, add the following constraint:

sum{n in N} x[n] - sum{s in S\N} x[s] <= |N|-1

To derive this formula, start with the more obvious condition for excluding a binary solution:

sum {i in S} |x[i] - x*[i]| >= 1

Then use the definitions of S and N to derive the above constraint without any absolute values.

By adding this constraint, you exclude the previous optimal solution. Optimizing again will find an alternate optimal solution, if one exists; otherwise, this procedure will find the second best solution to the problem. You can repeat this process as many times as is necessary.

In the general integer case, you need a more complicated collection of constraints to express the condition:

sum {i in S} |x[i] - x*[i]| >= 1

This more complicated collection of constraints can also be implemented. In this case, S is the set of general integer variables rather than binaries.