The OPTLP Procedure

Example 10.5 Reoptimizing after Modifying the Right-Hand Side

You can also modify the right-hand side of your problem and use the BASIS=WARMSTART option to obtain an optimal solution more quickly. Since the dual solution to the original LP is still feasible for the modified problem in this case, the dual simplex solver is preferred. This case is illustrated by using the same diet problem as in Example 10.3. Assume that you now need a diet that supplies at least 150 calories. The RHS section in the input data set ex3 is updated (and the data set is saved as ex5) as follows:

      ...
   RHS         .          .        .     .         .
   .           .          calories 150   protein   10
   .           .          fat      8     carbs     10
   BOUNDS      .          .        .     .         .
      ...

You can use the following DATA step to create the data set ex5:

data ex5;
input field1 $ field2 $ field3$ field4 field5 $ field6 ;
datalines;
NAME        .          EX5      .     .         .
ROWS        .          .        .     .         .
 N          diet       .        .     .         .
 G          calories   .        .     .         .
 L          protein    .        .     .         . 
 G          fat        .        .     .         .
 G          carbs      .        .     .         .
COLUMNS     .          .        .     .         .
.           br         diet     2     calories  90
.           br         protein  4     fat       1
.           br         carbs    15    .         .
.           mi         diet     3.5   calories  120
.           mi         protein  8     fat       5
.           mi         carbs    11.7  .         .
.           ch         diet     8     calories  106
.           ch         protein  7     fat       9
.           ch         carbs    .4    .         .
.           po         diet     1.5   calories  97
.           po         protein  1.3   fat       .1
.           po         carbs    22.6  .         .
.           fi         diet     11    calories  130
.           fi         protein  8     fat       7
.           fi         carbs    0     .         .
.           yo         diet     1     calories  180
.           yo         protein  9.2   fat       1
.           yo         carbs    17    .         .
RHS         .          .        .     .         .
.           .          calories 150   protein   10
.           .          fat      8     carbs     10
BOUNDS      .          .        .     .         .
UP          .          mi       1     .         .
LO          .          fi       .5    .         .
ENDATA      .          .        .     .         .
;

You can use the BASIS=WARMSTART option in the following call to PROC OPTLP to solve the modified problem:

proc optlp data=ex5
  presolver = none
  basis     = warmstart
  primalin  = ex3pout
  dualin    = ex3dout
  solver    = dual
  primalout = ex5pout
  dualout   = ex5dout
  printfreq = 1;
run;

Note that the dual simplex solver is preferred because the dual solution to the last solved LP is still feasible for the modified problem in this case.

The following iteration log indicates that it takes the dual simplex solver just one more phase II iteration to solve the modified problem by using BASIS=WARMSTART.

Output 10.5.1 Iteration Log

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

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

NOTE: The problem has 23 constraint coefficients.

NOTE: The OPTLP presolver value NONE is applied.

NOTE: The DUAL SIMPLEX solver is called.

Objective Entering Leaving

Phase Iteration Value Variable Variable

2 1 9.174413 calories(S) carbs (S)

NOTE: Optimal.

NOTE: Objective = 9.1744132.

NOTE: The data set WORK.EX5POUT has 6 observations and 10 variables.

NOTE: The data set WORK.EX5DOUT has 4 observations and 10 variables.

Compare this with the following call to PROC OPTLP:

proc optlp data=ex5
  presolver = none
  solver    = dual
  printfreq = 1;
run;

This call to PROC OPTLP solves the modified problem "from scratch" (without using the BASIS=WARMSTART option) and produces the following iteration log.

Output 10.5.2 Iteration Log

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

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

NOTE: The problem has 23 constraint coefficients.

NOTE: The OPTLP presolver value NONE is applied.

NOTE: The DUAL SIMPLEX solver is called.

Objective Entering Leaving

Phase Iteration Value Variable Variable

2 1 8.650000 mi fat (S)

2 2 8.925676 ch protein (S)

2 3 9.174413 po carbs (S)

NOTE: Optimal.

NOTE: Objective = 9.1744132.

It is clear that using the BASIS=WARMSTART option saves computation time. For larger or more complex examples, the benefits of using this option are more pronounced.