Ill conditioning

Introduces CPLEX behavior with respect to ill conditioning in LP models.

A mathematical model is said to be ill-conditioned when a small change in the input results in a surprisingly large change in the computed solution.

Even if you do not explicitly change the data in your model, finite precision computers can introduce changes in the data for a variety of reasons.

• Most numbers (for example, 1/3, 5/12) cannot be represented exactly in finite precision.
• Different chips employ different floating point representations.
• Different compilers can use the same floating point representation differently.

Consequently, an ill-conditioned linear system can yield much different results on different machines.

Not all kinds of ill-conditioning are easily measured. However, there are conventions to measure ill-conditioning in square linear systems of equations. These conventions calculate a value, known as the condition number or kappa, based on measurable qualities of the solution of the square linear system. (For more information about ill-conditioning and how it is conventionally calculated, consult the references recommended in the topic Further reading in the preface of this manual.)

Experts in the field say that a square linear system is ill-conditioned if the condition number kappa is large. A square linear system is well conditioned if the condition number kappa is small. Whether the condition number kappa is large or small depends on the computer, the data, and the algorithmic tolerances. In particular, ill conditioning can occur when the round off error associated with finite precision is large enough to influence algorithmic decisions. In other words, the basic question about both ill-conditioning and numerical difficulties is whether the tolerances of the optimizer can misdirect it to make decisions about the model based on round-off error of the computer. Algorithmic decisions based on computer round-off error are likely to cause inconsistent results in optimization.