The following example has been adapted from the example “A Multicommodity Transshipment Problem with Fixed Charges” in Chapter 5: The LP Procedure in SAS/OR 12.3 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 is for each of the four commodities c across each of the arcs . In addition, there is a fixed charge for the use of each arc . 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) 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 define the flow of commodity c across arc . Let if arc is used, and 0 otherwise. Since the total flow on an arc must be at most the total demand across all nodes , you can define the trivial upper bound as

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

Constraint (balance_con) ensures conservation of flow for both supply and demand. Constraint (fixed_charge_con) models the fixed charge cost by forcing if for some commodity .

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 | Single-Machine |

Number of Threads | 1 |

Solution Summary | |
---|---|

Solver | MILP |

Algorithm | Branch and Cut |

Objective Function | TotalCost |

Solution Status | Optimal within Relative Gap |

Objective Value | 42825 |

Relative Gap | 2.3350852E-7 |

Absolute Gap | 0.01 |

Primal Infeasibility | 0 |

Bound Infeasibility | 0 |

Integer Infeasibility | 0 |

Best Bound | 42824.99 |

Nodes | 1 |

Iterations | 30 |

Presolve Time | 0.00 |

Solution Time | 0.14 |

[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 | 10 |

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 | 90 |

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 |