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
   algorithm = dual
   primalout = ex5pout
   dualout   = ex5dout
   logfreq   = 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 LP presolver value NONE is applied.                                   
NOTE: The LP solver is called.                                                  
NOTE: The Dual Simplex algorithm is used.                                       
                           Objective                Entering      Leaving       
      Phase Iteration        Value         Time     Variable      Variable      
       D 2          1    8.813205E+00         0   calories (S)      carbs (S)   
       D 2          2    9.174413E+00         0                                 
       D 2          3    9.174413E+00         0                                 
NOTE: Optimal.                                                                  
NOTE: Objective = 9.1744131985.                                                 
NOTE: The Dual Simplex solve time is 0.03 seconds.                              
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
   algorithm = dual
   logfreq   = 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 LP presolver value NONE is applied.                                   
NOTE: The LP solver is called.                                                  
NOTE: The Dual Simplex algorithm is used.                                       
                           Objective                Entering      Leaving       
      Phase Iteration        Value         Time     Variable      Variable      
       D 1          1    0.000000E+00         0                                 
       D 2          2    5.500000E+00         0         mi            fat (S)   
       D 2          3    8.650000E+00         0         ch        protein (S)   
       D 2          4    8.925676E+00         0         po          carbs (S)   
       D 2          5    9.174413E+00         0                                 
       D 2          6    9.174413E+00         0                                 
NOTE: Optimal.                                                                  
NOTE: Objective = 9.1744131985.                                                 
NOTE: The Dual Simplex solve time is 0.05 seconds.                              


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.