! Max Flow (dual of Min cut) problem;
! Given a network, e.g., a railroad network,
where each arc (i,j) has a capacity c(i,j),
and a source node and a sink, 
find the maximum possible flow from the source
to the sink;
! References: Ford and Fulkerson, Harris and Ross;
! Keywords: Min cut, Max flow, Network, Interdiction;

SETS:
 NODE;
 ARC( NODE, NODE): C, FLO;
ENDSETS
DATA:
 NODE = S  1 2 3 4 5 6 7 8 9 T;
! The arcs and their capacities;
  ARC, C =
  S 1  23
  S 2  29
  1 3   6
  1 4   9
  2 3  19
  3 4   9
  3 5  17
  4 6  11
  4 7  13
  5 6   8
  5 8   7
  6 7  12
  6 9  14
  6 T   6
  7 T  21
  8 9  15
  9 T  16; 
ENDDATA
! Variables:
    FLO(i,j) = flow from node i to node j;

! Get number of nodes in network;
 NODET = @SIZE( NODE);

! Maximize flow out of S ;
 MAX = @SUM( ARC(i,j) | i #EQ# 1: FLO(i,j));

 ! Conservation of flow at each intermediate nodes;
 @FOR( NODE( k) | k #GT# 1 #AND# k #LT# NODET:
  [Y]  @SUM( ARC(i,k): FLO(i,k)) = @SUM( ARC(k,j): FLO(k,j));
     );

 ! Flow out of 1/S = Flow into NODET/T;
   [Y1] @SUM( ARC(k,j) | k #EQ# 1: FLO(k,j))
  =@SUM( ARC(i,k) | k #EQ# NODET: FLO(i,k));

 ! Upper limit on flow on each arc;
  @FOR( ARC(i,j):
    [Z] FLO(i,j) <= C(i,j); 
      );