MIP kappa: detecting and coping with ill-conditioned MIP models

Recommends techniques to detect ill conditioning in your MIP model.

To help you evaluate ill-conditioning and numerical difficulties in your model, CPLEX offers an optional report of the condition number, that is, MIP kappa statistics based on the simplex solutions of node relaxations during MIP optimization. To generate such a report, set the MIP kappa computation (CPXPARAM_MIP_Strategy_KappaStats, MIPKappaStats) documented in the Parameter Reference Manual.

When you set that parameter to report kappa statistics about your model, CPLEX tells you whether it encountered suspicious, unstable, or ill-posed bases while solving your model. For a definition of the range of condition numbers for suspicious, unstable, and ill-posed bases, see the documentation of these symbols in the reference manuals of the APIs:

  • CPX_KAPPA_SUSPICIOUS or KappaSuspicious reports the percentage of numerically suspicious simplex bases (condition number kappa between 1e+7 and 1e+10) among simplex bases encountered during a MIP solve.
  • CPX_KAPPA_UNSTABLE or KappaUnstable reports the percentage of numerically unstable simplex bases (condition number kappa between 1e+10 and 1e+14) among simplex bases encountered during a MIP solve.
  • CPX_KAPPA_ILLPOSED or KappaIllposed reports the percentage of numerically ill-posed simplex bases (condition number greater than 1e+14) among simplex bases encountered during a MIP solve.

Here is a sample from a log file showing results when the parameter CPXPARAM_MIP_Strategy_KappaStats=2 (formerly CPX_PARAM_MIPKAPPASTATS=2) tells CPLEX to compute MIP kappa for all LP subproblems:

MILP objective                                -2.1989035553e+06
MILP solution norm |x| (Total, Max)            1.95445e+10  1.68134e+08
MILP solution error (Ax=b) (Total, Max)        3.90105e+05  8.14760e+03
MILP x bound error (Total, Max)                0.00000e+00  0.00000e+00
MILP x integrality error (Total, Max)          1.96296e-06  9.81482e-07
MILP slack bound error (Total, Max)            8.27493e-08  2.95847e-09

Branch-and-cut subproblem optimization:
Max condition number:                    1.9347e+12
Percentage (number) of stable bases:      0.00%   (0)
Percentage (number) of suspicious bases: 99.97%   (16518157)
Percentage (number) of unstable bases:    0.03%   (5044)
Percentage (number) of ill-posed bases:   0.00%   (0)
Attention level:                         0.010089

This output was generated from the Interactive Optimizer of CPLEX using the display solution quality command. From a program using one of the CPLEX APIs, the routines CPXXgetdblquality and CPXgetdblquality from the C API and the getQuality methods of the IloCplex classes in the object-oriented APIs provide the corresponding information.

In such a report, the attention level estimates the probability of numerical difficulties for the given sample of condition numbers. When the attention level is 0 (zero), CPLEX encountered only stable bases while solving the model. When the attention level is strictly greater than 0 (zero), CPLEX encountered at least one basis that is not stable. The maximum value of attention level is 1 (one), reporting that all the bases are ill-posed.

You should reconsider your model if CPLEX reports any ill-posed bases or more than 5% unstable bases.

In a report like that sample, consider the solution norm values. If the report shows large solution norm values, check the lower order decimal places for round off error. If the round off error exceeds the tolerances set for this optimization, you can encounter inconsistent results and other numerical difficulties.

For example, that sample report of solution quality shows that the maximum individual x value is on the order of 1e+8. Conventional machine precision is 1e-16; that is, there are 16 digits of accuracy; that is, values beyond the eighth decimal place are likely to arise from round-off error. CPLEX uses default tolerances for feasibility and optimality of 1e-6 implying that the solution in the sample report is sound. However, for the particular model in that sample report, it would not be a good idea to reduce the CPLEX feasibility and optimality tolerances to 1e-8 or less.

Also consider the solution error in the report. The solution error is a vector of residuals on the constraints; that is:

b - Ax

The Max solution error is the maximum individual absolute residual element in that vector. The Total solution error is the sum of the absolute values of all elements in that vector. In that sample report, both the maximum and total solution error are quite significant.

Acceptable residual levels depend on the magnitude of the numerical values in the problem. In other words, whether residuals are too great or not depends on your model and data. For most models, one would expect residuals no larger than the feasibility tolerance used to solve the model. In this case (as reported in that sample), the residuals are much larger. In fact, the residuals are so much larger that they warrant investigation.

To detect the source of the large residuals and to assess their importance, start by looking for constraints with large right hand side values where a modest relative violation in the constraint results in a large absolute violation. Then, examine the nonzero matrix and associated variable values for such constraints. This procedure suggests the cause of the large residuals. Possible remedies include rescaling constraints with extremely large coefficients or reformulating parts of the model to reduce large solution values.

Even a small percentage of ill-posed bases in the MIP kappa statistics is cause for concern about the model. Likewise, a significant percentage of unstable bases raises concern about the model. For practical suggestions about how to address such concerns, see the popular CPLEX Tech Note Diagnosing ill conditioning at your IBM Support Portal: http://www-304.ibm.com/support/docview.wss?uid=swg21399993