The Mixed Integer Linear Programming Solver

Example 7.2 Multicommodity Transshipment Problem with Fixed Charges

The following example has been adapted from the example A Multicommodity Transshipment Problem with Fixed Charges in Chapter 6: The LP Procedure in SAS/OR 12.1 User's Guide: Mathematical Programming Legacy Procedures.

This example illustrates the use of PROC OPTMODEL to generate a mixed integer linear program to solve a multicommodity network flow model with fixed charges. Consider a network with nodes N, arcs A, and a set C of commodities to be shipped between the nodes. The commodities are defined in the data set COMMODITY_DATA, as follows:

title 'Multicommodity Transshipment Problem with Fixed Charges';

data commodity_data;
   do c = 1 to 4;
      output;
   end;
run;

Shipping cost $s_{ijc}$ is for each of the four commodities c across each of the arcs $(i,j)$. In addition, there is a fixed charge $f_{ij}$ for the use of each arc $(i,j)$. The shipping costs and fixed charges are defined in the data set ARC_DATA, as follows:

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;

The supply (positive numbers) or demand (negative numbers) $d_{ic}$ at each of the nodes for each commodity c is shown in the data set SUPPLY_DATA, as follows:

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;

Let $x_{ijc}$ define the flow of commodity c across arc $(i,j)$. Let $y_{ij} = 1$ if arc $(i,j)$ is used, and 0 otherwise. Since the total flow on an arc $(i,j)$ must be at most the total demand across all nodes $k \in N$, you can define the trivial upper bound $u_{ijc}$ as

\[  x_{ijc} \leq u_{ijc} = \sum _{k \in N | d_{kc} < 0} (-d_{kc})  \]

This model can be represented using the following mixed integer linear program:

\[  \begin{array}{llllll} \min &  \displaystyle \sum _{(i,j) \in A} \displaystyle \sum _{c \in C} s_{ijc} x_{ijc} + \displaystyle \sum _{(i,j) \in A} f_{ij} y_{ij} \\ \mr {s.t.} &  \displaystyle \sum _{j \in N | (i,j) \in A} x_{ijc} - \displaystyle \sum _{j \in N | (j,i) \in A} x_{jic} &  \leq &  d_{ic} &  \forall i \in N, c \in C &  \mr {(balance\_ con)}\\ &  x_{ijc} &  \leq &  u_{ijc} y_{ij} &  \forall (i,j) \in A, c \in C &  \mr {(fixed\_ charge\_ con)} \\ &  x_{ijc} &  \geq &  0 &  \forall (i,j) \in A, c \in C \\ &  y_{ij} \in \{ 0,1\}  & & &  \forall (i,j) \in A \end{array}  \]

Constraint (balance_con) ensures conservation of flow for both supply and demand. Constraint (fixed_charge_con) models the fixed charge cost by forcing $y_{ij} = 1$ if $x_{ijc} > 0$ for some commodity $c \in C$.

The PROC OPTMODEL statements follow:

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 the PROC LP example 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 ensures that only the nonzero parts of the solution appear in the SOLUTION data set.

The problem summary, solution summary, and the output from the two PRINT statements are shown in Output 7.2.1.

Output 7.2.1: Multicommodity Transshipment Problem with Fixed Charges Solution Summary

Multicommodity Transshipment Problem with Fixed Charges

The OPTMODEL Procedure

[1] [2] [3] unit_cost
Chicago NY 1 75
Chicago NY 2 75
Chicago NY 3 75
Chicago NY 4 75
StLouis NY 1 80
StLouis NY 2 80
StLouis NY 3 80
StLouis NY 4 80
farm-a Chicago 1 20
farm-a Chicago 2 15
farm-a Chicago 3 17
farm-a Chicago 4 22
farm-a StLouis 1 30
farm-a StLouis 2 25
farm-a StLouis 3 27
farm-a StLouis 4 22
farm-b Chicago 1 15
farm-b Chicago 2 15
farm-b Chicago 3 15
farm-b Chicago 4 30
farm-c Chicago 1 30
farm-c Chicago 2 30
farm-c Chicago 3 10
farm-c Chicago 4 10
farm-c StLouis 1 10
farm-c StLouis 2 9
farm-c StLouis 3 11
farm-c StLouis 4 10

[1] [2] fixed_charge
Chicago NY 200
StLouis NY 200
farm-a Chicago 100
farm-a StLouis 150
farm-b Chicago 75
farm-c Chicago 100
farm-c StLouis 75

supply
  1 2 3 4
Chicago 0 0 0 0
NY -150 -200 -50 -75
StLouis 0 0 0 0
farm-a 100 100 40 0
farm-b 100 200 50 50
farm-c 40 100 75 100

Problem Summary
Objective Sense Minimization
Objective Function TotalCost
Objective Type Linear
   
Number of Variables 35
Bounded Above 0
Bounded Below 0
Bounded Below and Above 35
Free 0
Fixed 0
Binary 7
Integer 0
   
Number of Constraints 52
Linear LE (<=) 52
Linear EQ (=) 0
Linear GE (>=) 0
Linear Range 0
   
Constraint Coefficients 112

Performance Information
Execution Mode On Client
Number of Threads 1

Solution Summary
Solver MILP
Algorithm Branch and Cut
Objective Function TotalCost
Solution Status Optimal
Objective Value 42825
Iterations 28
Best Bound 42825
Nodes 1
   
Relative Gap 0
Absolute Gap 0
Primal Infeasibility 0
Bound Infeasibility 0
Integer Infeasibility 9.999113E-12

[1] [2] [3] AmountShipped
Chicago NY 1 110
Chicago NY 2 100
Chicago NY 3 50
Chicago NY 4 75
StLouis NY 1 40
StLouis NY 2 100
StLouis NY 3 0
StLouis NY 4 0
farm-a Chicago 1 10
farm-a Chicago 2 100
farm-a Chicago 3 0
farm-a Chicago 4 0
farm-a StLouis 1 0
farm-a StLouis 2 0
farm-a StLouis 3 0
farm-a StLouis 4 0
farm-b Chicago 1 100
farm-b Chicago 2 0
farm-b Chicago 3 0
farm-b Chicago 4 0
farm-c Chicago 1 0
farm-c Chicago 2 0
farm-c Chicago 3 50
farm-c Chicago 4 75
farm-c StLouis 1 40
farm-c StLouis 2 100
farm-c StLouis 3 0
farm-c StLouis 4 0