The Linear Programming Solver

Example 6.2 Reoptimizing the Diet Problem Using BASIS=WARMSTART

After an LP is solved, you might want to change a set of the parameters of the LP and solve the problem again. This can be done efficiently in PROC OPTMODEL. The warm start technique uses the optimal solution of the solved LP as a starting point and solves the modified LP problem faster than it can be solved again from scratch. This example illustrates reoptimizing the diet problem described in Example 6.1.

Assume the optimal solution is found by the SOLVE statement. Instead of quitting the OPTMODEL procedure, you can continue to solve several variations of the original problem.

Suppose the cost of cheese increases from 8 to 10 per unit and the cost of fish decreases from 11 to 7 per serving unit. You can change the parameters and solve the modified problem by submitting the following code:

   cost['Cheese']=10; cost['Fish']=7;
   solve with lp/presolver=none
                 basis=warmstart
                 algorithm=ps
                 logfreq=1;
   print diet;

Note that the primal simplex solver is preferred because the primal solution to the last-solved LP is still feasible for the modified problem in this case. The solutions to the original diet problem and the modified problem are shown in Output 6.2.1.

Output 6.2.1: Optimal Solutions to the Original Diet Problem and the Diet Problem with Modified Objective Function

The OPTMODEL Procedure

Problem Summary
Objective Sense Minimization
Objective Function f
Objective Type Linear
   
Number of Variables 6
Bounded Above 0
Bounded Below 5
Bounded Below and Above 1
Free 0
Fixed 0
   
Number of Constraints 4
Linear LE (<=) 1
Linear EQ (=) 0
Linear GE (>=) 3
Linear Range 0
   
Constraint Coefficients 23

Performance Information
Execution Mode Single-Machine
Number of Threads 1

Solution Summary
Solver LP
Algorithm Dual Simplex
Objective Function f
Solution Status Optimal
Objective Value 12.081337881
   
Primal Infeasibility 0
Dual Infeasibility 0
Bound Infeasibility 0
   
Iterations 7
Presolve Time 0.00
Solution Time 0.03

[1] diet
Bread 0.000000
Cheese 0.449499
Fish 0.500000
Milk 0.053599
Potato 1.865168
Yogurt 0.000000

Problem Summary
Objective Sense Minimization
Objective Function f
Objective Type Linear
   
Number of Variables 6
Bounded Above 0
Bounded Below 5
Bounded Below and Above 1
Free 0
Fixed 0
   
Number of Constraints 4
Linear LE (<=) 1
Linear EQ (=) 0
Linear GE (>=) 3
Linear Range 0
   
Constraint Coefficients 23

Performance Information
Execution Mode Single-Machine
Number of Threads 1

Solution Summary
Solver LP
Algorithm Primal Simplex
Objective Function f
Solution Status Optimal
Objective Value 10.980335514
   
Primal Infeasibility 1.776357E-15
Dual Infeasibility 0
Bound Infeasibility 0
   
Iterations 1
Presolve Time 0.00
Solution Time 0.03

[1] diet
Bread 0.000000
Cheese 0.449499
Fish 0.500000
Milk 0.053599
Potato 1.865168
Yogurt 0.000000


The following iteration log indicates that it takes the LP solver no more iterations to solve the modified problem by using BASIS=WARMSTART, since the optimal solution to the original problem remains optimal after the objective function is changed.

Output 6.2.2: Log

NOTE: There were 6 observations read from the data set WORK.FOODDATA.           
NOTE: Problem generation will use 4 threads.                                    
NOTE: The problem has 6 variables (0 free, 0 fixed).                            
NOTE: The problem has 4 linear constraints (1 LE, 0 EQ, 3 GE, 0 range).         
NOTE: The problem has 23 linear constraint coefficients.                        
NOTE: The problem has 0 nonlinear constraints (0 LE, 0 EQ, 0 GE, 0 range).      
NOTE: The LP presolver value AUTOMATIC is applied.                              
NOTE: The LP presolver removed 0 variables and 0 constraints.                   
NOTE: The LP presolver removed 0 constraint coefficients.                       
NOTE: The presolved problem has 6 variables, 4 constraints, and 23 constraint   
      coefficients.                                                             
NOTE: The LP solver is called.                                                  
NOTE: The Dual Simplex algorithm is used.                                       
                           Objective                                            
      Phase Iteration        Value         Time                                 
       D 1          1    0.000000E+00         0                                 
       D 2          2    0.000000E+00         0                                 
       D 2          7    9.503132E+00         0                                 
NOTE: Optimal.                                                                  
NOTE: Objective = 9.5031323959.                                                 
NOTE: The Dual Simplex solve time is 0.05 seconds.                              
NOTE: Problem generation will use 4 threads.                                    
NOTE: The problem has 6 variables (0 free, 0 fixed).                            
NOTE: The problem has 4 linear constraints (1 LE, 0 EQ, 3 GE, 0 range).         
NOTE: The problem has 23 linear constraint coefficients.                        
NOTE: The problem has 0 nonlinear constraints (0 LE, 0 EQ, 0 GE, 0 range).      
NOTE: The LP presolver value NONE is applied.                                   
NOTE: The LP solver is called.                                                  
NOTE: The Primal Simplex algorithm is used.                                     
                           Objective                Entering          Leaving   
      Phase Iteration        Value         Time     Variable          Variable  
       P 2          1    1.098034E+01         0                                 
NOTE: Optimal.                                                                  
NOTE: Objective = 10.980335514.                                                 
NOTE: The Primal Simplex solve time is 0.03 seconds.                            


Next, restore the original coefficients of the objective function and consider the case that you need a diet that supplies at least 150 calories. You can change the parameters and solve the modified problem by submitting the following code:

   cost['Cheese']=8; cost['Fish']=11;cal_con.lb=150;
   solve with lp/presolver=none
                 basis=warmstart
                 algorithm=ds
                 logfreq=1;
   print diet;

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 solution is shown in Output 6.2.3.

Output 6.2.3: Optimal Solution to the Diet Problem with Modified RHS

The OPTMODEL Procedure

Problem Summary
Objective Sense Minimization
Objective Function f
Objective Type Linear
   
Number of Variables 6
Bounded Above 0
Bounded Below 5
Bounded Below and Above 1
Free 0
Fixed 0
   
Number of Constraints 4
Linear LE (<=) 1
Linear EQ (=) 0
Linear GE (>=) 3
Linear Range 0
   
Constraint Coefficients 23

Performance Information
Execution Mode Single-Machine
Number of Threads 1

Solution Summary
Solver LP
Algorithm Dual Simplex
Objective Function f
Solution Status Optimal
Objective Value 9.1744131985
   
Primal Infeasibility 0
Dual Infeasibility 0
Bound Infeasibility 0
   
Iterations 6
Presolve Time 0.00
Solution Time 0.05

[1] diet
Bread 0.00000
Cheese 0.18481
Fish 0.50000
Milk 0.56440
Potato 0.14702
Yogurt 0.00000


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

Output 6.2.4: Log

NOTE: There were 6 observations read from the data set WORK.FOODDATA.           
NOTE: Problem generation will use 4 threads.                                    
NOTE: The problem has 6 variables (0 free, 0 fixed).                            
NOTE: The problem has 4 linear constraints (1 LE, 0 EQ, 3 GE, 0 range).         
NOTE: The problem has 23 linear constraint coefficients.                        
NOTE: The problem has 0 nonlinear constraints (0 LE, 0 EQ, 0 GE, 0 range).      
NOTE: No basis information is available.  The BASIS=WARMSTART option is ignored.
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     diet[Milk]                  
      fat_con (S)                                                               
       D 2          3    8.650000E+00         0   diet[Cheese]                  
      prot_con (S)                                                              
       D 2          4    8.925676E+00         0   diet[Potato]                  
      carb_con (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.                              


Next, restore the original constraint on calories and consider the case that you need a diet that supplies no more than 550 mg of sodium per day. The following row is appended to Table 6.5.

Table 6.6: (continued)

 

Bread

Milk

Cheese

Potato

Fish

Yogurt

sodium, mg

148

122

337

186

56

132


You can change the parameters, add the new constraint, and solve the modified problem by submitting the following code:

   cal_con.lb=300;
   num sod{FOOD}=[148 122 337 186 56 132];
   con sodium: sum{i in FOOD}sod[i]*diet[i] <= 550;
   solve with lp/presolver=none
                 basis=warmstart
                 logfreq=1;
   print diet;

The solution is shown in Output 6.2.5.

Output 6.2.5: Optimal Solution to the Diet Problem with Additional Constraint

The OPTMODEL Procedure

Problem Summary
Objective Sense Minimization
Objective Function f
Objective Type Linear
   
Number of Variables 6
Bounded Above 0
Bounded Below 5
Bounded Below and Above 1
Free 0
Fixed 0
   
Number of Constraints 5
Linear LE (<=) 2
Linear EQ (=) 0
Linear GE (>=) 3
Linear Range 0
   
Constraint Coefficients 29

Performance Information
Execution Mode Single-Machine
Number of Threads 1

Solution Summary
Solver LP
Algorithm Dual Simplex
Objective Function f
Solution Status Optimal
Objective Value 12.081337881
   
Primal Infeasibility 0
Dual Infeasibility 0
Bound Infeasibility 0
   
Iterations 7
Presolve Time 0.00
Solution Time 0.03

[1] diet
Bread 0.000000
Cheese 0.449499
Fish 0.500000
Milk 0.053599
Potato 1.865168
Yogurt 0.000000


The following iteration log indicates that it takes the LP 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 6.2.6: Log

NOTE: There were 6 observations read from the data set WORK.FOODDATA.           
NOTE: Problem generation will use 4 threads.                                    
NOTE: The problem has 6 variables (0 free, 0 fixed).                            
NOTE: The problem has 5 linear constraints (2 LE, 0 EQ, 3 GE, 0 range).         
NOTE: The problem has 29 linear constraint coefficients.                        
NOTE: The problem has 0 nonlinear constraints (0 LE, 0 EQ, 0 GE, 0 range).      
NOTE: No basis information is available.  The BASIS=WARMSTART option is ignored.
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     diet[Milk]                  
      fat_con (S)                                                               
       D 2          3    8.650000E+00         0   diet[Yogurt]                  
      cal_con (S)                                                               
       D 2          4    8.894231E+00         0   diet[Potato]                  
      prot_con (S)                                                              
       D 2          5    1.155221E+01         0   diet[Cheese]                  
      diet[Yogurt]                                                              
       D 2          6    1.208134E+01         0                                 
       D 2          7    1.208134E+01         0                                 
NOTE: Optimal.                                                                  
NOTE: Objective = 12.081337881.                                                 
NOTE: The Dual Simplex solve time is 0.06 seconds.