Example 10.6 Reoptimizing after Adding a New Constraint

Assume that after solving the diet problem in Example 10.3 you need to add a new constraint on sodium intake of no more than 550 mg/day for adults. The updated nutrition data are given in Table 10.7.

Table 10.7 Updated Cost and Nutrition Values
 

Bread

Milk

Cheese

Potato

Fish

Yogurt

Cost

2.0

3.5

8.0

1.5

11.0

1.0

Protein, g

4.0

8.0

7.0

1.3

8.0

9.2

Fat, g

1.0

5.0

9.0

0.1

7.0

1.0

Carbohydrates, g

15.0

11.7

0.4

22.6

0.0

17.0

Calories, Cal

90

120

106

97

130

180

sodium, mg

148

122

337

186

56

132

The input data set ex3 is updated (and the data set is saved as ex6) as follows:

/* added a new constraint to the diet problem */
data ex6;
input field1 $ field2 $ field3$ field4 field5 $ field6 ;
datalines;
NAME        .          EX6      .     .         .
ROWS        .          .        .     .         .
 N          diet       .        .     .         .
 G          calories   .        .     .         .
 L          protein    .        .     .         .
 G          fat        .        .     .         .
 G          carbs      .        .     .         .
 L          sodium     .        .     .         .
COLUMNS     .          .        .     .         .
.           br         diet     2     calories  90
.           br         protein  4     fat       1
.           br         carbs    15    sodium    148
.           mi         diet     3.5   calories  120
.           mi         protein  8     fat       5
.           mi         carbs    11.7  sodium    122
.           ch         diet     8     calories  106
.           ch         protein  7     fat       9
.           ch         carbs    .4    sodium    337
.           po         diet     1.5   calories  97
.           po         protein  1.3   fat       .1
.           po         carbs    22.6  sodium    186
.           fi         diet     11    calories  130
.           fi         protein  8     fat       7
.           fi         carbs    0     sodium    56
.           yo         diet     1     calories  180
.           yo         protein  9.2   fat       1
.           yo         carbs    17    sodium    132
RHS         .          .        .     .         .
.           .          calories 300   protein   10
.           .          fat      8     carbs     10
.           .          sodium   550   .         .
BOUNDS      .          .        .     .         .
UP          .          mi       1     .         .
LO          .          fi       .5    .         .
ENDATA      .          .        .     .         .
;

For the modified problem you can warm start the primal and dual simplex solvers to get a solution faster. The dual simplex solver is preferred because a dual feasible solution can be readily constructed from the optimal solution to the diet optimization problem.

Since there is a new constraint in the modified problem, you can use the following SAS code to create a new DUALIN= data set ex6din with this information:

data ex6newcon;
   _ROW_='sodium  '; _STATUS_='A';
   output;
run;
/* create a new DUALIN= data set to include the new constraint */
data ex6din;
   set ex3dout ex6newcon;
run;

Note that this step is optional. In this example, you can still use the data set ex3dout as the DUALIN= data set to solve the modified LP problem by using the BASIS=WARMSTART option. PROC OPTLP validates the PRIMALIN= and DUALIN= data sets against the input model. Any new variable (or constraint) in the model is added to the PRIMALIN= (or DUALIN=) data set, and its status is assigned to be 'A'. The primal and dual simplex solvers decide its corresponding status internally. Any variable in the PRIMALIN= and DUALIN= data sets but not in the input model is removed.

The _ROW_ and _STATUS_ columns of the DUALIN= data set ex6din are shown in Output 10.6.1.

Output 10.6.1 DUALIN= Data Set with a Newly Added Constraint
Obs _ROW_ _STATUS_
1 calories U
2 protein L
3 fat U
4 carbs B
5 sodium A

The dual simplex solver is called to solve the modified diet optimization problem more quickly with the following SAS code:

proc optlp data=ex6 
   objsense=min 
   presolver=none 
   solver=ds 
   primalout=ex6pout 
   dualout=ex6dout
   scale=none 
   printfreq=1
   basis=warmstart 
   primalin=ex3pout
   dualin=ex6din;
run;

The optimal primal and dual solutions of the modified problem are displayed in Output 10.6.2.

Output 10.6.2 Primal and Dual Solution Output
Primal Solution

Obs Objective
Function ID
RHS ID Variable
Name
Variable
Type
Objective
Coefficient
Lower Bound Upper Bound Variable Value Variable
Status
Reduced Cost
1 diet   br N 2.0 0.0 1.7977E308 0.00000 L 1.19066
2 diet   mi D 3.5 0.0 1 0.05360 B 0.00000
3 diet   ch N 8.0 0.0 1.7977E308 0.44950 B 0.00000
4 diet   po N 1.5 0.0 1.7977E308 1.86517 B 0.00000
5 diet   fi O 11.0 0.5 1.7977E308 0.50000 L 5.15641
6 diet   yo N 1.0 0.0 1.7977E308 0.00000 L 1.10849



Dual Solution

Obs Objective
Function ID
RHS ID Constraint Name Constraint
Type
Constraint
RHS
Constraint
Lower
Bound
Constraint
Upper
Bound
Dual Variable
Value
Constraint
Status
Constraint Activity
1 diet   calories G 300 . . 0.02179 U 300.000
2 diet   protein L 10 . . -0.55360 L 10.000
3 diet   fat G 8 . . 1.06286 U 8.000
4 diet   carbs G 10 . . 0.00000 B 42.960
5 diet   sodium L 550 . . 0.00000 B 532.941

The iteration log shown in Output 10.6.3 indicates that it takes the dual simplex solver no more iterations to solve the modified problem by using the BASIS=WARMSTART option, since the optimal solution to the original problem remains optimal after one more constraint is added.

Output 10.6.3 Iteration Log
NOTE: The problem EX6 has 6 variables (0 free, 0 fixed).                        
NOTE: The problem has 5 constraints (2 LE, 0 EQ, 3 GE, 0 range).                
NOTE: The problem has 29 constraint coefficients.                               
NOTE: The OPTLP presolver value NONE is applied.                                
NOTE: The DUAL SIMPLEX solver is called.                                        
NOTE: Optimal.                                                                  
NOTE: Objective = 12.0813379.                                                   
NOTE: The data set WORK.EX6POUT has 6 observations and 10 variables.            
NOTE: The data set WORK.EX6DOUT has 5 observations and 10 variables.            

Both this example and Example 10.4 illustrate the situation in which the optimal solution does not change after some perturbation of the parameters of the LP problem. The simplex solver starts from an optimal solution and quickly verifies the optimality. Usually the optimal solution of the slightly perturbed problem can be obtained after performing relatively small number of iterations if starting with the optimal solution of the original problem. In such cases you can expect a dramatic reduction of computation time, for instance, if you want to solve a large LP problem and a slightly perturbed version of this problem by using the BASIS=WARMSTART option rather than solving both problems from scratch.