The LP Procedure

The following example illustrates a DATA step program for generating a linear program to solve a multicommodity network flow model that has fixed charges. Consider a network consisting of the following nodes: farm-a, farm-b, farm-c, Chicago, St. Louis, and New York. You can ship four commodities from each farm to Chicago or St. Louis and from Chicago or St. Louis to New York. The following table shows the unit shipping cost for each of the four commodities across each of the arcs. The table also shows the supply (positive numbers) at each of the from nodes and the demand (negative numbers) at each of the to nodes. The fixed charge is a fixed cost for shipping any nonzero amount across an arc. For example, if any amount of any of the four commodities is sent from farm-c to St. Louis, then a fixed charge of 75 units is added to the shipping cost.

                    Unit Shipping  Supply and Demand  Fixed
     From    To         Cost                          Charge
     Node   Node      1  2  3  4     1   2   3   4

   farm-a  Chicago   20 15 17 22   100 100  40   .     100
   farm-b  Chicago   15 15 15 30   100 200  50  50      75
   farm-c  Chicago   30 30 10 10    40 100  75 100     100
   farm-a  StLouis   30 25 27 22     .   .   .   .     150
   farm-c  StLouis   10  9 11 10     .   .   .   .      75
   Chicago NY        75 75 75 75  -150 -200 -50 -75    200
   StLouis NY        80 80 80 80     .   .   .   .     200

The following program is designed to take the data in the form given in the preceding table. It builds the node arc incidence matrix for a network given in this form and adds integer variables to capture the fixed charge using the type of constraints discussed in Example 4.8. The program solves the model using PROC LP, saves the solution in the PRIMALOUT= data set named SOLUTION, and displays the solution. The DATA step can be easily modified to handle larger problems with similar structure.

title 'Multi-commodity Transshipment Problem with Fixed-Charges';
%macro dooversd;
   _coef_=sd{_i_};
   if sd{_i_}>0 then do;                /* the node is a supply node */
      _row_=from||' commodity'||put(_i_,2.);
      if from^=' ' then output;
      end;
   else if sd{_i_}<0 then do;           /* the node is a demand node */
      _row_=to||' commodity'||put(_i_,2.);
      if to^=' ' then output;
   end;
   else if from^=' ' & to^=' ' then do; /* a transshipment node      */
      _coef_=0;
      _row_=from||' commodity'||put(_i_,2.); output;
      _row_=to  ||' commodity'||put(_i_,2.); output;
   end;
%mend dooversd;

%macro dooverc;
   _col_=arc||' commodity'||put(_i_,2.);
   if from^=' ' & to^=' ' then do;  /* add node arc incidence matrix */
      _type_='le'; _row_=from||' commodity'||put(_i_,2.);
      _coef_=1;  output;
      _row_=to  ||' commodity'||put(_i_,2.);
      _coef_=-1; output;
      _type_='  '; _row_='obj';
      _coef_=c{_i_};  output;
      /* add fixed charge variables   */
      _type_='le'; _row_=arc;
      _coef_=1;  output;
      _col_='_rhs_';
      _type_='  ';
      _coef_=0;  output;
      _col_=arc||'fx';
      _coef_=-M; output;
      _row_='int';
      _coef_=1;  output;
      _row_='obj';
      _coef_=fx; output;
      _row_='upper';
      _coef_=1;  output;
   end;
%mend dooverc;

data network;
retain M 1.0e6;
length _col_ $ 22 _row_ $ 22;
keep _type_ _col_ _row_ _coef_ ;
array sd sd1-sd4;
array c c1-c4;

input arc $10. from $ to $ c1 c2 c3 c4 sd1 sd2 sd3 sd4 fx;

/* for the first observation define some of the rows */

if _n_=1 then do;
   _type_='upperbd'; _row_='upper'; output;
   _type_='lowerbd'; _row_='lower'; output;
   _type_='min';     _row_='obj';   output;
   _type_='integer'; _row_='int';   output;
end;

_col_='_rhs_';  _type_='le';

do _i_ = 1 to dim(sd);
   %dooversd;
end;
do _i_ = 1 to dim(c);
   %dooverc;
end;

datalines;
a-Chicago   farm-a  Chicago    20 15 17 22     100 100  40   .  100
b-Chicago   farm-b  Chicago    15 15 15 30     100 200  50  50   75
c-Chicago   farm-c  Chicago    30 30 10 10      40 100  75 100  100
a-StLouis   farm-a  StLouis    30 25 27 22       .   .   .   .  150
c-StLouis   farm-c  StLouis    10  9 11 10       .   .   .   .   75
Chicago-NY  Chicago NY         75 75 75 75    -150 -200 -50 -75 200
StLous-NY   StLouis NY         80 80 80 80       .   .   .   .  200
;

/* solve the model */

proc lp sparsedata pout=solution noprint;
run;

 /* print the solution */

data;
   set solution;
   rename _var_=arc _value_=amount;
   if _value_^=0 & _type_='NON-NEG';
run;

proc print;
   id arc;
   var amount;
run;

The results from this example are shown in Output 4.14.1. The NOPRINT option in the PROC LP statement suppresses the Variable and Constraint Summary sections. This is useful when solving large models for which a report program is available. Here, the solution is saved in data set SOLUTION and reported using PROC PRINT. The solution shows the amount that is shipped over each arc.