Diagnosing LP Infeasibility

> Continuous Optimization > Solving LPs: Simplex Optimizers > 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 function; 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.

ILOG CPLEX provides tools to help you analyze the source of the infeasibility in your model. Those tools include the IIS Finder and FeasOpt:

The IIS Finder finds a set of irreducibly inconsistent constraints in a model. For more about this this feature, see Finding a Set of Irreducibly Inconsistent Constraints.
FeasOpt is implemented in the Callable Library by the routine CPXfeasopt and in Concert Technology by the method feasOpt. For more about this feature, see More about Infeasibility: FeasOpt.

With the help of those tools, you may be able to modify your problem to avoid infeasibility.

PREVIOUS NEXT