The LP Procedure

Example 5.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 5.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 5.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 5.8.

Output 5.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.