MODEL:
! Keywords: multi-commodity, network flow, routing;
! Multi-commodity network flow problem;
SETS:
! The nodes in the network;
NODES/1..6/:;
! The set of nodes that are origins;
COMMO(NODES)/1, 2, 5/:;
EDGES(NODES, NODES): D, C, U, V;
NET(EDGES, COMMO): X;
ENDSETS DATA:
! Demand: amount to be shipped from
origin(row) to destination(col);
D = 0 5 9 7 0 4
0 0 4 0 1 0
0 0 0 0 0 0
0 0 0 0 0 0
0 4 0 2 0 8
0 0 0 0 0 0;
! Cost per unit shipped over a arc/link;
C = 0 4 5 8 9 9
3 0 3 2 4 6
5 3 0 2 3 5
7 3 3 0 5 6
8 5 3 6 0 3
9 7 4 5 5 0;
! Upper limit on amount shipped on each link;
U = 0 2 3 2 1 20
0 0 2 8 3 9
3 0 0 1 3 9
5 4 6 0 5 9
1 0 2 7 0 9
9 9 9 9 9 0;
! Whether an arc/link exists or not;
! V = 0 if U = 0;
! V = 1 otherwise;
V = 0 1 1 1 1 1
0 0 1 1 1 1
1 0 0 1 1 1
1 1 1 0 1 1
1 0 1 1 0 1
1 1 1 1 1 0;
ENDDATA
! Minimize shipping cost over all links;
MIN = @SUM( NET(I, J, K): C(I, J) * X(I, J, K));
! This is the balance constraint. There are two cases:
Either the node that needs to be balanced is not a supply,
in which case the sum of incoming amounts
minus the sum of outgoing amounts must equal
the demand for that commodity for that city;
!or where the node is a supply,
the sum of incoming minus outgoing amounts must equal
the negative of the sum of the demand for the commodity
that the node supplies;
@FOR(COMMO(K): @FOR(NODES(J)|J #NE# K:
@SUM(NODES(I): V(I, J) * X(I, J, K) - V(J, I) * X(J, I, K))
= D(K, J);
);
@FOR(NODES(J)|J #EQ# K:
@SUM(NODES(I): V(I, J) * X(I, J, K) - V(J, I) * X(J, I, K))
= -@SUM( NODES(L): D(K, L))););
! This is a capacity constraint;
@FOR(EDGES(I, J)|I #NE# J:
@SUM(COMMO(K): X(I, J, K)) <= U(I, J);
);
END
|