The Linear Programming Solver

For a linear programming problem, an irreducible infeasible set (IIS) is an infeasible subset of constraints and variable bounds that will become feasible if any single constraint or variable bound is removed. It is possible to have more than one IIS in an infeasible LP. Identifying an IIS can help to isolate the structural infeasibility in an LP.

The IIS=ON option directs the LP solver to search for an IIS in a given LP. You should specify the OPTMODEL option PRESOLVER=NONE when you specify IIS=ON; otherwise the IIS results can be incomplete. The LP presolver is not applied to the problem during the IIS search. If the LP solver detects an IIS, it updates the .status suffix of the decision variables and constraints, and then it stops. The number of iterations that are reported in the macro variable and the ODS table is the total number of simplex iterations. This includes the initial LP solve and all subsequent iterations during the constraint deletion phase.

The IIS= option can add special values to the .status suffixes of variables and constraints. (See the section Variable and Constraint Status for more information.) For constraints, a status of “I_L”, “I_U”, or “I_F” indicates, respectively, the “GE” (), “LE” (), or “EQ” (=) condition is violated. For range constraints, a status of “I_L” or “I_U” indicates, respectively, that the lower or upper bound of the constraint is violated. For variables, a status of “I_L”, “I_U”, or “I_F” indicates, respectively, the lower, upper, or fixed bound of the variable is violated. From this information, you can identify names of the constraints (variables) in the IIS as well as the corresponding bound where infeasibility occurs.

Making any one of the constraints or variable bounds in the IIS nonbinding removes the infeasibility from the IIS. In some cases, changing a right-hand side or bound by a finite amount will removes the infeasibility; however, the only way to guarantee removal of the infeasibility is to set the appropriate right-hand side or bound to or . Because it is possible for an LP to have multiple irreducible infeasible sets, simply removing the infeasibility from one set might not make the entire problem feasible. To make the entire problem feasible, you can rerun the LP solver with IIS=ON after removing the infeasibility from an IIS. Repeat this process until the LP solver no longer detects an IIS. The resulting problem is feasible. This approach to infeasibility repair can produce different end problems depending on which right-hand sides and bounds you choose to relax.

The IIS= option in the LP solver uses two different methods to identify an IIS. Based on the result of the initial solve, the sensitivity filter removes several constraints and variable bounds at once while still maintaining infeasibility. This phase is quick and dramatically reduces the size of the IIS. After that, the deletion filter removes each remaining constraint and variable bound one by one to check which of them are needed to get an infeasible system. This second phase is more time consuming, but it ensures that the IIS set returned by the LP solver is indeed irreducible. The progress of the deletion filter is reported at regular intervals. Occasionally, the sensitivity filter might be called again during the deletion filter to improve performance.

See Example 6.4 for an example demonstrating the use of the IIS= option in locating and removing infeasibilities.