The LP Procedure

Example 4.2 A Sparse View of the Oil Blending Problem

Typically, mathematical programming models are very sparse. This means that only a small percentage of the coefficients are nonzero. The sparse problem input is ideal for these models. The oil blending problem in the section An Introductory Example has a sparse form. This example shows the same problem in a sparse form with the data given in a different order. In addition to representing the problem in a concise form, the sparse format

allows long column names
enables easy matrix generation (see Example 4.12, Example 4.13, and Example 4.14)
is compatible with MPS sparse format

The model in the sparse format is solved by invoking PROC LP with the SPARSEDATA option as follows.

data oil;
      format _type_ $8. _col_ $14. _row_ $16. ;
      input _type_ $ _col_ $ _row_ $ _coef_ ;
datalines;
max      .             profit                    .
.        arabian_light profit                 -175
.        arabian_heavy profit                 -165
.        brega         profit                 -205
.        jet_1         profit                  300
.        jet_2         profit                  300
eq       .             napha_l_conv              .
.        arabian_light napha_l_conv           .035
.        arabian_heavy napha_l_conv           .030
.        brega         napha_l_conv           .045
.        naphtha_light napha_l_conv             -1
eq       .             napha_i_conv              .
.        arabian_light napha_i_conv           .100
.        arabian_heavy napha_i_conv           .075
.        brega         napha_i_conv           .135
.        naphtha_inter napha_i_conv             -1
eq       .             heating_oil_conv          .
.        arabian_light heating_oil_conv       .390
.        arabian_heavy heating_oil_conv       .300
.        brega         heating_oil_conv       .430
.        heating_oil   heating_oil_conv         -1
eq       .             recipe_1                  .
.        naphtha_inter recipe_1                 .3
.        heating_oil   recipe_1                 .7
eq       .             recipe_2                  .
.        jet_1         recipe_1                 -1
.        naphtha_light recipe_2                 .2
.        heating_oil   recipe_2                 .8
.        jet_2         recipe_2                 -1
.        _rhs_         profit                    0
upperbd  .             available                 .
.        arabian_light available               110
.        arabian_heavy available               165
.        brega         available                80
;

proc lp SPARSEDATA;
run;

The output from PROC LP follows.

Output 4.2.1: Output for the Sparse Oil Blending Problem

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

The LP Procedure

Solution Summary
Terminated Successfully
Objective Value	1544

Phase 1 Iterations	0
Phase 2 Iterations	5
Phase 3 Iterations	0
Integer Iterations	0
Integer Solutions	0
Initial Basic Feasible Variables	5
Time Used (seconds)	0
Number of Inversions	3

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

The LP Procedure

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	UPPBD	UPPERBD	-205	80	3.35
4	heating_oil	BASIC	NON-NEG	0	77.3	0
5	jet_1	BASIC	NON-NEG	300	60.65	0
6	jet_2	BASIC	NON-NEG	300	63.33	0
7	naphtha_inter	BASIC	NON-NEG	0	21.8	0
8	naphtha_light	BASIC	NON-NEG	0	7.45	0

The LP Procedure

Constraint Summary
Row	Constraint Name	Type	S/S Col	Rhs	Activity	Dual Activity
1	profit	OBJECTVE	.	0	1544	.
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