Multicommodity Flow Problem (dcmpe01)
/***************************************************************/
/* */
/* S A S S A M P L E L I B R A R Y */
/* */
/* NAME: dcmpe01 */
/* TITLE: Multicommodity Flow Problem (dcmpe01) */
/* PRODUCT: OR */
/* SYSTEM: ALL */
/* KEYS: OR */
/* PROCS: OPTMODEL */
/* DATA: */
/* */
/* SUPPORT: UPDATE: */
/* REF: */
/* MISC: Example 1 from the Decomposition Algorithm */
/* chapter of Mathematical Programming. */
/* */
/***************************************************************/
data arc_comm_data;
input k i j cost;
datalines;
1 1 2 1
1 1 3 5
1 5 3 1
1 5 6 5
1 3 4 1
1 4 2 5
1 4 6 1
2 1 2 1
2 1 3 5
2 5 3 1
2 5 6 5
2 3 4 1
2 4 2 5
2 4 6 1
;
data arc_data;
input i j capacity;
datalines;
1 2 5
1 3 30
5 3 30
5 6 30
3 4 10
4 2 30
4 6 30
;
data supply_data;
input k i supply;
datalines;
1 1 10
1 2 -10
2 5 20
2 6 -20
;
proc optmodel;
set <num,num,num> ARC_COMM;
num cost {ARC_COMM};
read data arc_comm_data into ARC_COMM=[i j k] cost;
set ARCS = setof {<i,j,k> in ARC_COMM} <i,j>;
set COMMODITIES = setof {<i,j,k> in ARC_COMM} k;
set NODES = union {<i,j> in ARCS} {i,j};
num arcCapacity {ARCS};
read data arc_data into [i j] arcCapacity=capacity;
num supply {NODES, COMMODITIES} init 0;
read data supply_data into [i k] supply;
var Flow {<i,j,k> in ARC_COMM} >= 0;
min TotalCost =
sum {<i,j,k> in ARC_COMM} cost[i,j,k] * Flow[i,j,k];
con Balance {i in NODES, k in COMMODITIES}:
sum {<(i),j,(k)> in ARC_COMM} Flow[i,j,k]
- sum {<j,(i),(k)> in ARC_COMM} Flow[j,i,k] = supply[i,k];
con Linking {<i,j> in ARCS}:
sum {<(i),(j),k> in ARC_COMM} Flow[i,j,k] <= arcCapacity[i,j];
for{i in NODES, k in COMMODITIES} Balance[i,k].block = k;
solve with LP / presolver=none decomp subprob=(algorithm=nspure);
print Flow;
quit;