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

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