The Nonlinear Programming Solver

Example 10.7 Finding an Irreducible Infeasible Set

This example demonstrates the use of the IIS= option to locate an irreducible infeasible set. Suppose you have the following nonlinear programming problem:

$\begin{array}{rllllllcrc} \mbox{minimize} & & x_1^4 & + & x_2^4 & + & x_3^4 & & & \\ \mbox{ subject to }& & x_1 & + & x_2 & & & \geq & 10 & (\Variable{c1})\\ & & x_1 & & & + & x_3 & \leq & 4 & (\Variable{c2})\\ & 4\leq & & & x_2 & + & x_3 & \leq & 5 & (\Variable{c3})\\ & & x_1^2 & & & + & x_3 & \leq & 5 & (\Variable{c4})\\ & & & & & x_1, & x_2 & \geq & 0 & \\ & & & & 0 & \leq & x_3 & \leq & 3 & \\ \end{array}$

It is easy to verify that the following three linear constraints and one variable bound form an IIS for this problem:

$\begin{array}{lllllcrc} x_1 & + & x_2 & & & \geq & 10 & (\Variable{c1})\\ x_1 & & & + & x_3 & \leq & 4 & (\Variable{c2})\\ & & x_2 & + & x_3 & \leq & 5 & (\Variable{c3})\\ & & & & x_3 & \geq & 0 & \\ \end{array}$

You can formulate the problem and call the NLP solver by using the following statements:

proc optmodel;
   /* declare variables */
   var x{1..3} >= 0;

   /* upper bound on variable x[3] */
   x[3].ub = 3;

   /* objective function */
   min f = x[1]^4 + x[2]^4 + x[3]^4;

   /* constraints */
   con c1: x[1] + x[2] >= 10;
   con c2: x[1] + x[3] <= 4;
   con c3: 4 <= x[2] + x[3] <= 5;
   con c4: x[1]^2 + x[3] <= 5;

   solve with nlp / iis = on;

   print x.status;
   print c1.status c2.status c3.status;
quit;

The SAS log output is shown in Output 10.7.1. Note that the PROC OPTMODEL presolver is disabled because the IIS= option is enabled. Also, a warning message is displayed to alert the user that the nonlinear constraints are ignored for the purpose of detecting an IIS.

Output 10.7.1: Finding an IIS: Original Problem

NOTE: The OPTMODEL presolver is disabled when the IIS= option is enabled.

NOTE: Problem generation will use 4 threads.

NOTE: The problem has 3 variables (0 free, 0 fixed).

NOTE: The problem has 3 linear constraints (1 LE, 0 EQ, 1 GE, 1 range).

NOTE: The problem has 6 linear constraint coefficients.

NOTE: The problem has 1 nonlinear constraints (1 LE, 0 EQ, 0 GE, 0 range).

WARNING: The nonlinear constraints are ignored because the IIS= option is

enabled.

NOTE: The NLP solver is called.

NOTE: The IIS= option is enabled.

Objective

Phase Iteration Value Time

P 1 1 1.400000E+01 0

P 1 3 9.999420E-01 0

NOTE: Applying the IIS sensitivity filter.

NOTE: The sensitivity filter removed 1 constraints and 3 variable bounds.

NOTE: Applying the IIS deletion filter.

NOTE: Processing constraints.

Processed Removed Time

0 0 0

1 0 0

2 0 0

3 0 0

NOTE: Processing variable bounds.

Processed Removed Time

0 0 0

1 0 0

2 0 0

3 0 0

NOTE: The deletion filter removed 0 constraints and 0 variable bounds.

NOTE: The IIS= option found this problem to be infeasible.

NOTE: The IIS= option found an irreducible infeasible set with 1 variables and

3 constraints.

NOTE: The IIS solve time is 0.02 seconds.

The "Solution Summary" table and the output of the PRINT statements appear in Output 10.7.2.

Output 10.7.2: Solution Summary and PRINT Statement Output

The OPTMODEL Procedure

Solution Summary
Solver	NLP
Algorithm	IIS
Objective Function	f
Solution Status	Infeasible

Iterations	14
Iterations2	0
Presolve Time	0.00
Solution Time	0.02

[1]	x.STATUS
1
2
3	I_L

c1.STATUS	c2.STATUS	c3.STATUS
I_L	I_U	I_U

The "Solution Summary" table shows that the problem is infeasible. As you can see, the lower bound of variable $x_3$ , the lower bound of constraint c1, and the upper bounds of constraints c2 and c3 form an IIS.

Making any of the components in the preceding IIS nonbinding removes the infeasibility from the IIS. Because there could be multiple IISs, you would want to remove the infeasibility from the preceding IIS and call the NLP solver with the IIS= option enabled again to see whether there is any other IIS. The following statements show how to modify the original PROC OPTMODEL statements to set the upper bound of constraint c3 to infinity, represented by CONSTANT(’BIG’), and invoke the NLP IIS detection:

   /* relax upper bound on constraint c3 */
   c3.ub = constant('BIG');
   
   solve with nlp / iis = on;
   
   print x.status;
   print c1.status c2.status c3.status;

The SAS log output for the modified problem is shown in Output 10.7.3.

Output 10.7.3: Finding an IIS: Modified Problem