Diagnosing ill conditioning

Answer

Fundamentally, a mathematical program is ill conditioned if a small change in the input can result in a big change in the computed solution of the model. Ill conditioning or numerical instability in a model can cause trouble for
CPLEX in its pivot selection process during a simplex iteration. Such ill
conditioning can cause various problems such as:

• Inconsistent results with presolve on and off. Read the document titled Turning CPLEX presolve on or off gives inconsistent results for additional background on presolve
• Inaccuracies in the computed solution that contradict the meaning of constraints in the model
• Inconsistent results with different parameter settings
• Inconsistent results when making problem modifications that should not affect the solution, such as adding a constraint that the current solution does not violate
• Inconsistent results with a minute change in data

When there is such an inconsistent behavior like this, you can check for numerical problems by using the 'display solution quality' and 'display solution kappa' commands. The former displays the magnitude of various residuals associated with the solution (that is, the accuracy with which the solution satisfies constraints and bounds), while the latter provides the condition number of the optimal basis. The kappa value is the one of the most interesting value to note. Most computers have a precision of 1E-16, and the maximum potential error for the
solution value is (computer precision)* kappa. Hence, the kappa value would be significant in determining the extent of damage caused by a round off error.

For example, if your kappa is like:
kappa = 1.3672e+011

In this case, there are only 5 accurate places left in case CPLEX finds solution. This means round off errors on the order of 1E-05 can multiply the matrix, right hand side, or objective coefficients. Therefore, problem data of even modest orders of magnitude can magnify the contribution of the round off error.

Versions 12.2 and later of CPLEX also offer functionality to assess ill conditioning in integer programming models, which solve a sequence of continuous relaxations. Specifically, you can set the MIP Kappa parameter to instruct CPLEX to sample and compute statistics on the condition numbers of the optimal bases associated with the various continuous subproblems CPLEX's MIP algorithm solves. CPLEX will then provide summary statistics and an assessment of the overall level of ill conditioning. This provides more information then relying on the condition number of the initial relaxation, or the fixed model associated with the final solution. See the description of the MIP Kappa computation in the CPLEX Parameters Reference Manual for more information.

CPLEX provides certain parameters that can help solve ill conditioned models more effectively:

1. Set scale factor to 1 to invoke aggressive scaling.
2. Set the Markowitz tolerance to a near maximal value such as 0.90
   

Setting the scaling parameter helps if you have a combination of large and small coefficients in the constraint matrix. The Markowitz tolerance instructs CPLEX to use a more conservative pivoting scheme during the basis factorization. Both these parameters can reduce the round off error on numerically difficult, ill conditioned problems.

Furthermore, make sure that you do not use bounds larger than 1E+09 on your variables. Such large bounds can cause trouble because of round off and ill conditioning. Finite bounds should always be as small as possible without compromising the meaning of the associated variable and constraints it intersects. Note that for very large bounds, you could either declare the
variable as free or make use of CPX_INFBOUND, which is a large predefined constant that CPLEX interprets as an infinite bound value.

In addition, try to compute all data values in double precision. Computing the data in single precision, then converting the values into the double precision that CPLEX expects can introduce unnecessary perturbations to the problem data that can make an otherwise well conditioned model ill conditioned.

Make use of the diagnostic functions available in the check.c file from the standard distribution to analyze the model. This can give you information on the matrix coefficient range, the size of the bounds placed on the variables and the right hand side values of your constraints.

Click here - checkfile.c to download a program that will read in an MPS, LP or SAV file, then provide an analysis of your model data using the routines in check.c. Note that you can obtain some of the same information using interactive CPLEX by reading in the file then using the 'display problem stat' command to display the problem statistics. If using version 11.1 or earlier, you also need to turn on the datacheck parameter with the 'set read datacheck y' command to obtain these statistics.

Finally, read the document titled Histogram of coefficients in problem data vectors if you need even more diagnostic information about the problem data arrays.