The LP Procedure

Example 4.6 Special Ordered Sets and the Oil Blending Problem

Often managers want to evaluate the cost of making a choice among alternatives. In particular, they want to make the most profitable choice. Suppose that only one oil crude can be used in the production process. This identifies a set of variables of which only one can be above its lower bound. This additional restriction could be included in the model by adding a binary integer variable for each of the three crudes. Constraints would be needed that would drive the appropriate binary variable to 1 whenever the corresponding crude is used in the production process. Then a constraint limiting the total of these variables to only one would be added. A similar formulation for a fixed charge problem is shown in Example 4.8.

The SOSLE type implicitly does this. The following DATA step adds a row to the model that identifies which variables are in the set. The SOSLE type tells the LP procedure that only one of the variables in this set can be above its lower bound. If you use the SOSEQ type, it tells PROC LP that exactly one of the variables in the set must be above its lower bound. Only integer variables can be in an SOSEQ set. 

data special;
   format _type_ $6. _col_ $14. _row_ $8. ;
   input _type_ $ _col_ $ _row_ $ _coef_;
   datalines;
SOSLE .             special .
.     arabian_light special 1
.     arabian_heavy special 1
.     brega         special 1
;

data;
   set oil special;
run;

proc lp sparsedata;
run;

Output 4.6.1 includes an Integer Iteration Log. This log shows the progress that PROC LP is making in solving the problem. This is discussed in some detail in Example 4.8.

Output 4.6.1: The Oil Blending Problem with a Special Ordered Set

The LP Procedure

Problem Summary
Objective Function Max profit
Rhs Variable _rhs_
Type Variable _type_
Problem Density (%) 45.00
   
Variables Number
   
Non-negative 5
Upper Bounded 3
   
Total 8
   
Constraints Number
   
EQ 5
Objective 1
   
Total 6

Integer Iteration Log
Iter Problem Condition Objective Branched Value Sinfeas Active Proximity
1 0 ACTIVE 1544 arabian_light 110 0 2 .
2 -1 SUBOPTIMAL 1276 . . . 1 268
3 1 FATHOMED 268 . . . 0 .

Solution Summary

Integer Optimal Solution
Objective Value 1276
   
Phase 1 Iterations 0
Phase 2 Iterations 5
Phase 3 Iterations 0
Integer Iterations 3
Integer Solutions 1
Initial Basic Feasible Variables 5
Time Used (seconds) 0
Number of Inversions 5
   
Epsilon 1E-8
Infinity 1.797693E308
Maximum Phase 1 Iterations 100
Maximum Phase 2 Iterations 100
Maximum Phase 3 Iterations 99999999
Maximum Integer Iterations 100
Time Limit (seconds) 120

Variable Summary
Col Variable Name Status Type Price Activity Reduced Cost
1 arabian_heavy   UPPERBD -165 0 -21.45
2 arabian_light UPPBD UPPERBD -175 110 11.6
3 brega   UPPERBD -205 0 3.35
4 heating_oil BASIC NON-NEG 0 42.9 0
5 jet_1 BASIC NON-NEG 300 33.33 0
6 jet_2 BASIC NON-NEG 300 35.09 0
7 naphtha_inter BASIC NON-NEG 0 11 0
8 naphtha_light BASIC NON-NEG 0 3.85 0

Constraint Summary
Row Constraint Name Type S/S Col Rhs Activity Dual Activity
1 profit OBJECTVE . 0 1276 .
2 napha_l_conv EQ . 0 0 -60
3 napha_i_conv EQ . 0 0 -90
4 heating_oil_conv EQ . 0 0 -450
5 recipe_1 EQ . 0 0 -300
6 recipe_2 EQ . 0 0 -300 




            

            


            
The solution shows that only the ARABIAN_LIGHT crude is purchased. The requirement that only one crude be used in the production
               is met, and the profit is 1276. This tells you that the value of purchasing crude from an additional source, namely BREGA,
               is worth 1544 $-$ 1276 = 268.