The OPTLP Procedure

Example 15.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. We illustrate this case by using the same diet problem as in Example 15.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 15.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.

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 15.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.