The LP Procedure

Example 4.17 Migration to OPTMODEL: Multicommodity Transshipment

The following example shows how to solve Example 4.14 using PROC OPTMODEL. Three data sets contain the input data used in that example.

title 'Multicommodity Transshipment Problem with Fixed Charges';

data commodity_data;
   do c = 1 to 4;
      output;
   end;
run;
data arc_data;
   input from $ to $ c1 c2 c3 c4 fx;
   datalines;
farm-a  Chicago 20 15 17 22 100
farm-b  Chicago 15 15 15 30  75
farm-c  Chicago 30 30 10 10 100
farm-a  StLouis 30 25 27 22 150
farm-c  StLouis 10 9 11 10   75
Chicago NY      75 75 75 75 200
StLouis NY      80 80 80 80 200
;
run;
data supply_data;
   input node $ sd1 sd2 sd3 sd4;
   datalines;
farm-a  100  100  40   .
farm-b  100  200  50  50
farm-c   40  100  75 100
NY     -150 -200 -50 -75
;
run;

The following PROC OPTMODEL statements read the data sets, print the input parameters, build the mixed-integer linear programming model, solve the model, and output the optimal solution to a SAS data set called SOLUTION:

proc optmodel;
   set COMMODITIES;
   read data commodity_data into COMMODITIES=[c];

   set <str,str> ARCS;
   num unit_cost {ARCS, COMMODITIES};
   num fixed_charge {ARCS};
   read data arc_data into ARCS=[from to] {c in COMMODITIES}
      <unit_cost[from,to,c]=col('c'||c)> fixed_charge=fx;
   print unit_cost fixed_charge;

   set <str> NODES = union {<i,j> in ARCS} {i,j};
   num supply {NODES, COMMODITIES} init 0;
   read data supply_data nomiss into [node] {c in COMMODITIES}
      <supply[node,c]=col('sd'||c)>;
   print supply;

   var AmountShipped {ARCS, c in COMMODITIES} >= 0 <= sum {i in NODES}
      max(supply[i,c],0);

   /* UseArc[i,j] = 1 if arc (i,j) is used, 0 otherwise */
   var UseArc {ARCS} binary;

   /* TotalCost = variable costs + fixed charges */
   min TotalCost = sum {<i,j> in ARCS, c in COMMODITIES}
      unit_cost[i,j,c] * AmountShipped[i,j,c]
      + sum {<i,j> in ARCS} fixed_charge[i,j] * UseArc[i,j];

   con flow_balance {i in NODES, c in COMMODITIES}:
      sum {<(i),j> in ARCS} AmountShipped[i,j,c] -
      sum {<j,(i)> in ARCS} AmountShipped[j,i,c] <= supply[i,c];

   /* if AmountShipped[i,j,c] > 0 then UseArc[i,j] = 1 */
   con fixed_charge_def {<i,j> in ARCS, c in COMMODITIES}:
      AmountShipped[i,j,c] <= AmountShipped[i,j,c].ub * UseArc[i,j];

   solve;

   print AmountShipped;

   create data solution from [from to commodity]={<i,j> in ARCS,
   c in COMMODITIES: AmountShipped[i,j,c].sol ne 0} amount=AmountShipped;
quit;

Although Example 4.14 used M = 1.0e6 in the FIXED_CHARGE_DEF constraint that links the continuous variable to the binary variable, it is numerically preferable to use a smaller, data-dependent value. Here, the upper bound on AmountShipped[i,j,c] is used instead. This upper bound is calculated in the first VAR statement as the sum of all positive supplies for commodity c. The logical condition AmountShipped[i,j,k].sol ne 0 in the CREATE DATA statement makes sure that only the nonzero parts of the solution appear in the SOLUTION data set.

The optimal solution is the same as in Output 4.14.1. The log is displayed in Output 4.17.1.

Output 4.17.1: OPTMODEL Log

NOTE: There were 4 observations read from the data set WORK.COMMODITY_DATA.     
NOTE: There were 7 observations read from the data set WORK.ARC_DATA.           
NOTE: There were 4 observations read from the data set WORK.SUPPLY_DATA.        
NOTE: Problem generation will use 4 threads.                                    
NOTE: The problem has 35 variables (0 free, 0 fixed).                           
NOTE: The problem has 7 binary and 0 integer variables.                         
NOTE: The problem has 52 linear constraints (52 LE, 0 EQ, 0 GE, 0 range).       
NOTE: The problem has 112 linear constraint coefficients.                       
NOTE: The problem has 0 nonlinear constraints (0 LE, 0 EQ, 0 GE, 0 range).      
NOTE: The OPTMODEL presolver is disabled for linear problems.                   
NOTE: The MILP presolver value AUTOMATIC is applied.                            
NOTE: The MILP presolver removed 8 variables and 16 constraints.                
NOTE: The MILP presolver removed 30 constraint coefficients.                    
NOTE: The MILP presolver modified 22 constraint coefficients.                   
NOTE: The presolved problem has 27 variables, 36 constraints, and 82 constraint 
      coefficients.                                                             
NOTE: The MILP solver is called.                                                
NOTE: The parallel Branch and Cut algorithm is used.                            
NOTE: The Branch and Cut algorithm is using up to 4 threads.                    
          Node  Active    Sols    BestInteger      BestBound      Gap    Time   
             0       1       1  42850.0000000  35825.0000000   19.61%       0   
             0       1       1  42850.0000000  42635.0000000    0.50%       0   
             0       1       1  42850.0000000  42635.0000000    0.50%       0   
             0       1       1  42850.0000000  42635.0000000    0.50%       0   
NOTE: The MILP presolver is applied again.                                      
             0       1       1  42850.0000000  42707.5433526    0.33%       0   
NOTE: The MILP presolver is applied again.                                      
             0       1       2  42825.0000000  42707.5433526    0.28%       0   
             0       1       2  42825.0000000  42825.0000000    0.00%       0   
             0       0       2  42825.0000000  42825.0000000    0.00%       0   
NOTE: Optimal.                                                                  
NOTE: Objective = 42825.                                                        
NOTE: The data set WORK.SOLUTION has 13 observations and 4 variables.