Lindo Systems

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