Interpreting solution quality

Documents facilities for evaluating solution quality in LP models.

Infeasibility and unboundedness in linear programs are closely related. (For more about that idea, see the topics in Infeasibility and unboundedness.) When the linear program CPLEX solves is infeasible, the associated dual linear program has an unbounded ray. Similarly, when the dual linear program is infeasible, the primal linear program has an unbounded ray. This relationship is important for proper interpretation of infeasible solution output.

The treatment of models that are unbounded involves a few subtleties. Specifically, a declaration of unboundedness means that CPLEX has detected that the model has an unbounded ray. Given any feasible solution x with objective z, a multiple of the unbounded ray can be added to x to give a feasible solution with objective z-1 (or z+1 for maximization models). Thus, if a feasible solution exists, then the optimal objective is unbounded. Note that CPLEX has not necessarily concluded that a feasible solution exists. To see whether CPLEX has also concluded that the model has a feasible solution, use one of these routines or methods:

  • in Concert Technology:

    • isPrimalFeasible or isDualFeasible in the C++ API;

    • IloCplex.isPrimalFeasible or isDualFeasible in the Java API;

    • Cplex.IsPrimalFeasible or IsDualFeasible in the .NET API.

  • CPXsolninfo in the Callable Library.

By default, individual infeasibilities are written to a log file but not displayed on the screen. To display the infeasibilities on your screen, in Concert Technology, use methods of the environment to direct the output stream to your screen.

For C++ applications, see Accessing solution information, and for Java applications, see Accessing solution information. Those sections highlight the application programming details of how to retrieve statistics about the quality of a solution.

Regardless of whether a solution is infeasible or optimal, the command display solution quality in the Interactive Optimizer displays the bound and reduced-cost infeasibilities for both the scaled and unscaled problem. In fact, it displays the following summary statistics for both the scaled and unscaled problem:

  • maximum bound infeasibility, that is, the largest bound violation;

  • maximum reduced-cost infeasibility;

  • maximum row residual;

  • maximum dual residual;

  • maximum absolute value of a variable, a slack variable, a dual variable, and a reduced cost.

When the simplex optimizer detects infeasibility in the primal or dual linear program (LP), parts of the solution it provides are relative to the Phase I linear program it solved to conclude infeasibility. In other words, the result you see in such a case is not the solution values computed relative to the original objective or original righthand side vector. Keep this distinction in mind when you interpret solution quality; otherwise, you may be surprised by the results. In particular, when CPLEX detects that a linear program is infeasible using the primal simplex method, the reduced costs and dual variables provided in the solution are relative to the objective of the Phase I linear program it solved. Similarly, when CPLEX detects that a linear program is unbounded because the dual simplex method detected dual infeasibility, the primal and slack variables provided in the solution are relative to the Phase I linear program created for the dual simplex optimizer.

The following sections discuss these summary statistics in greater detail.

Maximum bound infeasibility: identifying largest bound violation

The maximum bound infeasibility identifies the largest bound violation. This information may help you discover the cause of infeasibility in your problem. If the largest bound violation exceeds the feasibility tolerance of your problem by only a small amount, then you may be able to get a feasible solution to the problem by increasing the feasibility tolerance parameter (EpRHS in Concert Technology, CPX_PARAM_EPRHS in the Callable Library). Its range is between 1e-9 and 0.1. Its default value is 1e-6.

Maximum reduced-cost infeasibility

The maximum reduced-cost infeasibility identifies a value for the optimality tolerance that would cause CPLEX to perform additional iterations. It refers to the infeasibility in the dual slack associated with reduced costs. Whether CPLEX terminated with an optimal or infeasible solution, if the maximum reduced-cost infeasibility is only slightly smaller in absolute value than the optimality tolerance, then solving the problem with a smaller optimality tolerance may result in an improvement in the objective function.

To change the optimality tolerance, set the optimality tolerance parameter (EpOpt in Concert Technology, CPX_PARAM_EPOPT in the Callable Library). Its range is between 1e-9 and 0.1. Its default value is 1e-6.

Maximum row residual

The maximum row residual identifies the maximum constraint violation. CPLEX simplex optimizers control these residuals only indirectly by applying numerically sound methods to solve the given linear system. When CPLEX terminates with an infeasible solution, all infeasibilities will appear as bound violations on structural or slack variables, not constraint violations. That is, the row residuals compare the righthand side of the constraint with the lefthand side (including slacks) for the computed solution. The maximum row residual may help you decide whether a model of your problem is poorly scaled, or whether the final basis (whether it is optimal or infeasible) is ill-conditioned.

Maximum dual residual

The maximum dual residual indicates the numeric accuracy of the reduced costs in the current solution. By construction, in exact arithmetic, the dual residual of a basic solution is always 0 (zero). A nonzero value is thus the effect of roundoff error due to finite-precision arithmetic in the computation of the dual solution vector. Thus, a significant nonzero value indicates ill conditioning.

Maximum absolute values: detecting ill-conditioned problems

When you are trying to decide whether your problem is ill-conditioned, you also need to consider the following maximum absolute values, all available in the infeasibility analysis that CPLEX provides you:

  • variables;

  • slack variables;

  • dual variables;

  • reduced costs (that is, dual slack variables).

When using the Component Libraries, use the method getQuality or the routine CPXgetdblquality to access the information provided by the command display solution quality in the Interactive Optimizer.

If you discover from this analysis that your model is indeed ill-conditioned, then you need to reformulate it. Coping with an ill-conditioned problem or handling unscaled infeasibilities outlines steps to follow in this situation.