Analyzing Infeasible Problems

An important feature of ILOG CPLEX is that even if no feasible solution has been found, that is, if cplex.solve() returns IloFalse, some information about the problem can be queried when solving LPs or QPs. All the methods discussed so far may successfully return information about the current (infeasible) solution which ILOG CPLEX maintains.

Unfortunately, there is no simple comprehensive rule about whether or not current solution information can be queried. This is because, by default, ILOG CPLEX uses a presolve procedure to simplify the model. If, for example, the model is proven to be infeasible during the presolve, no current solution is generated by the optimizer. If, in contrast, infeasibility is only proven by the optimizer, current solution information is available to be queried. The status returned by calling cplex.getCplexStatus() may help to determine which case you are facing, but it is probably safer and easier to include the methods for querying solution within try/catch statements.

When an LP has been proven to be infeasible, ILOG CPLEX provides assistance for determining the cause of the infeasibility. This is done by computing what is known as an irreducibly inconsistent set (IIS), which is a description of the minimal subproblem that is still infeasible. Here minimality is defined as being: if you remove any of the constraints (including finite bounds), the infeasibility vanishes. An IIS is computed for an infeasible LP model by calling method cplex.getIIS(). To compute an IIS for a QP, you should change the model to an LP by removing (zeroing) any quadratic terms from the objective function and then compute an IIS on the LP version.


Previous Page: Performing Sensitivity Analysis  Return to Top Next Page: Solution Quality