Diagnosing LP Infeasibility

Diagnosing LP Infeasibility

ILOG CPLEX reports statistics about any problem that it optimizes. For infeasible solutions, it reports values that you can analyze to determine where your problem formulation proved infeasible. In certain situations, you can then alter your problem formulation or change ILOG CPLEX parameters to achieve a satisfactory solution.

When the ILOG CPLEX primal simplex optimizer terminates with an infeasible basic solution, it calculates dual variables and reduced costs relative to the Phase I objective; that is, relative to the infeasibility function. The Phase I objective function depends on the current basis. Consequently, if you use the primal simplex optimizer with various parameter settings, an infeasible problem will produce different objective values and different solutions.
In the case of the dual simplex optimizer, termination with a status of infeasibility occurs only during Phase II. Therefore all solution values are relative to the problem's natural (primal) formulation, including the values related to the objective function such as the dual variables and reduced costs. As with the primal simplex optimizer, the basis at which the determination of infeasibility is made may not be unique.

Copyright © 2002 ILOG
http://www.ilog.com

Previous Page: Numerical Difficulties

Return to Top

Next Page: The Effect of Preprocessing on Feasibility