Previous Page

|

Next Page

Irreducible Infeasible Set

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 presolver in the OPTLP procedure can detect infeasibility, but it only identifies the variable bound or constraint that triggers the infeasibility.

The experimental IIS=ON option directs the OPTLP procedure to search for an IIS in a given LP. The presolver is not applied to the problem during the IIS search. If the OPTLP procedure detects an IIS, it first outputs the IIS to the data sets specified by the PRIMALOUT= and DUALOUT= options, then stops. Otherwise, the problem is sent on to the presolver, followed by the specified solver.

The IIS= option can add special values to the _STATUS_ variables in the output data sets. (See the section "Data Input and Output" 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 will remove the infeasibility from the IIS. In some cases, changing a right-hand side or bound by a finite amount will remove the infeasibility; however, the only way to guarantee removal of the infeasibility is to set the appropriate right-hand side or bound to or . Since 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.

Changing different constraints and bounds can require considerably different changes to the MPS-format SAS data set. For example, if you used the default lower bound of 0 for a variable but you want to relax the lower bound to , you might need to add a LB row to the BOUNDS section of the data set. For more information about changing variable and constraint bounds, see Chapter 14, "The MPS-Format SAS Data Set."

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