The OPTLP Procedure

(View the complete code for this example.)

This example demonstrates the use of the IIS= option to locate an irreducible infeasible set. Suppose you want to solve a linear program that has the following simple formulation:

The corresponding MPS-format SAS data set is as follows:

/* infeasible */
data exiis;
   input field1 $ field2 $ field3 $ field4 field5 $ field6;
datalines;
NAME     .        .        .        .        .
ROWS     .        .        .        .        .
 N       cost     .        .        .        .
 G       con1     .        .        .        .
 L       con2     .        .        .        .
 G       con3     .        .        .        .
COLUMNS  .        .        .        .        .
.        x1       cost     1        con1     1
.        x1       con2     1        .        .
.        x2       cost     1        con1     1
.        x2       con3     1        .        .
.        x3       cost     1        con2     1
.        x3       con3     1        .        .
RHS      .        .        .        .        .
.        rhs      con1     10       con2     4
.        rhs      con3     4        .        .
RANGES   .        .        .        .        .
.        r1       con3     1        .        .
BOUNDS   .        .        .        .        .
UP       b1       x3       3        .        .
ENDATA   .        .        .        .        .
;

It is easy to verify that the following three constraints (or rows) and one variable (or column) bound form an IIS for this problem.

You can use the IIS=TRUE option to detect this IIS by using the following statements:

proc optlp data=exiis
   iis=true
   primalout=iis_vars
   dualout=iis_cons
   logfreq=1;
run;

The OPTLP procedure outputs the detected IIS to the data sets specified by the PRIMALOUT= and DUALOUT= options, then stops. The notes shown in Output 12.7.1 are printed to the log.

The data sets iis_cons and iis_vars are shown in Output 12.7.2.

The constraint , which is an element of the IIS, is created by the RANGES section. The original constraint is con3, a "" constraint with an RHS value of 4. If you choose to remove the constraint , you can accomplish this by removing con3 from the RANGES section in the MPS-format SAS data set exiis. Since con3 is the only observation in the section, the identifier observation can also be removed. The modified LP problem is specified in the following SAS statements:

 /* dropping con3, feasible */
data exiisf;
   input field1 $ field2 $ field3 $ field4 field5 $ field6;
datalines;
NAME     .        .        .        .        .
ROWS     .        .        .        .        .
 N       cost     .        .        .        .
 G       con1     .        .        .        .
 L       con2     .        .        .        .
 G       con3     .        .        .        .
COLUMNS  .        .        .        .        .
.        x1       cost     1        con1     1
.        x1       con2     1        .        .
.        x2       cost     1        con1     1
.        x2       con3     1        .        .
.        x3       cost     1        con2     1
.        x3       con3     1        .        .
RHS      .        .        .        .        .
.        rhs      con1     10       con2     4
.        rhs      con3     4        .        .
BOUNDS   .        .        .        .        .
UP       b1       x3       3        .        .
ENDATA   .        .        .        .        .
;

Since one element of the IIS has been removed, the modified LP problem should no longer contain the infeasible set. Due to the size of this problem, there should be no additional irreducible infeasible sets. You can confirm this by submitting the following SAS statements:

proc optlp data=exiisf
   iis=true;
run;

The notes shown in Output 12.7.3 are printed to the log.

The solution summary is displayed in Output 12.7.4.