| The LP Procedure |
Example 3.14: A Multicommodity Transshipment Problem with Fixed Charges
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.
Table 3.8: Farms to Cities Network Problem
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 3.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';
data network;
retain M 1.0e6;
length _col_ $ 22 _row_ $ 22;
keep _type_ _col_ _row_ _coef_;
array sd sd1-sd4;
array c c1-c4;
format arc $10.;
input arc $ 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 over sd; /* loop for each commodity */
_coef_=sd;
if sd>0 then do; /* the node is a supply node */
_row_=from||' commodity'||put(_i_,2.);
if from^=' ' then output;
end;
else if sd<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;
end;
do over c; /* loop for each commodity */
_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;
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;
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 3.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.
Output 3.14.1: Multicommodity Transshipment Problem with Fixed Charges
Copyright © 2008 by SAS Institute Inc., Cary, NC, USA. All rights reserved.