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