ILOG CPLEX 11.0 User's Manual > Continuous Optimization > Solving LPs: Simplex Optimizers > Diagnosing LP Infeasibility > Coping with an Ill-Conditioned Problem or Handling Unscaled Infeasibilities

Coping with an Ill-Conditioned Problem or Handling Unscaled Infeasibilities

 INDEX Gray bullet PREVIOUS NEXT

By default, ILOG CPLEX scales a problem before attempting to solve it. After it finds an optimal solution, it then checks for any violations of optimality or feasibility in the original, unscaled problem. If there is a violation of reduced cost (indicating nonoptimality) or of a bound (indicating infeasibility), ILOG CPLEX reports both the maximum scaled and unscaled feasibility violations.

Unscaled infeasibilities are rare, but they may occur when a problem is ill-conditioned. For example, a problem containing a row in which the coefficients have vastly different magnitude is ill-conditioned in this sense and may result in unscaled infeasibilities.

It may be possible to produce a better solution anyway in spite of unscaled infeasibilities, or it may be necessary for you to revise the coefficients. To decide which way to go, consider these steps in such a case:

  1. Use the command display solution quality in the Interactive Optimizer to locate the infeasibilities.
  2. Examine the coefficient matrix for poorly scaled rows and columns.
  3. Evaluate whether you can change unnecessarily large or small coefficients.
  4. Consider alternate scalings.

You may also be able to re-optimize the problem successfully after you reduce optimality tolerance, as explained in Maximum Reduced-Cost Infeasibility, or after you reduce feasibility tolerance, as explained in Maximum Bound Infeasibility: Identifying Largest Bound Violation. When you change these tolerances, ILOG CPLEX may produce a better solution to your problem, but lowering these tolerances sometimes produces erratic behavior or an unstable optimal basis.

Check the basis condition number, as explained in Measuring Problem Sensitivity with Basis Condition Number. If the condition number is fairly low (for example, as little as 1e5 or less), then you can be confident about the solution. If the condition number is high, or if reducing tolerance does not help, then you must revise the model because the current model may be too ill-conditioned to produce a numerically reliable result.

Copyright © 1987-2007 ILOG S.A. All rights reserved. Legal terms. PREVIOUS NEXT