The LP Procedure

Example 3.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 3.12, Example 3.13, and Example 3.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 
    upperbd .             available           . 
    .       arabian_light available         110 
    .       arabian_heavy available         165 
    .       brega         available          80 
    ; 
  
    proc lp data=oil sparsedata; 
    run;
 

The output from PROC LP follows.

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