! Min Cut (dual of Max Flow) problem;
! Given a network, e.g., a railroad network,
where each arc (i,j) has a cost to remove, C(i,j),
and a source node and a sink, 
 Find a minimum cost set of arcs to delete
so that there is no flow (or path) from
the source node to the sink node;
 ! References: Ford and Fulkerson, Harris and Ross;
! Keywords: Min cut, Max flow, Network, Interdiction;
SETS:
 NODE: Y;
 ARC( NODE, NODE): C, Z;
ENDSETS
DATA:
 NODE = S  1 2 3 4 5 6 7 8 9 T;
! The arcs and their costs to delete;
  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

SUBMODEL MINCUT:
! Variables:
  Z(i,j) = 1 if we delete arc i,j
  Y(i) = 1 if node i is on the Source side of cut,
         0 otherwise;

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

! Minimize the cost of deleted arcs;
 MIN = @SUM( ARC(i,j) : C(i,j)*Z(i,j));

! Node 1, the Source, is definitely on S side,
  Node T is not;
 [FLO1] Y(1) - Y(NODET) >= 1;

! If arc (i,j) is on the cut (deleted),
  then node i must be on the S side of cut,
  and j is not.
  If node i is on the S side of the cut,
  then so is node j, except if arc (i,j)
  has been deleted;
  @FOR( ARC(i,j):
   [FLO] Z(i,j) - Y(i) + Y(j) >= 0; 
      );
ENDSUBMODEL


CALC:
  @SOLVE( MINCUT);

  @WRITE( 'The Minimum Cost Set of Arcs to Delete to',
   @NEWLINE(1),'       Split a Network.',@NEWLINE(1));
  @WRITE('   Arc deleted      Cost',@NEWLINE(1));
  SUMDEL = 0;
  @FOR( ARC(i,j) | Z(i,j) #GT# 0.5:
    @WRITE( '     (', NODE(i),', ',NODE(j),')           ', C(i,j),@NEWLINE(1));
    SUMDEL = SUMDEL + C(i,j);
      );
  @WRITE(' Total removal cost= ',SUMDEL,@NEWLINE(1));
ENDCALC