Diagnosing LP Infeasibility

ILOG CPLEX 11.0 User's Manual > 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 discover 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 in which the detection of infeasibility occurred may not be unique.

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

The conflict refiner is invoked by the routine CPXrefineconflict in the Callable Library or by the method refineConflict in Concert Technology. It finds a set of conflicting constraints and bounds in a model and refines the set to be minimal in a sense that you declare. It then reports its findings for you to take action to repair that conflict in your infeasible model. For more about this feature, see Diagnosing Infeasibility by Refining Conflicts.
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 Repairing Infeasibility: FeasOpt.

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

PREVIOUS NEXT