Maximum Flow

   {  Exmpl5.3-5_MaximumFlow.mpl  }

   {  H.P. Williams, Model Building in Mathematical Programming, 3rd ed.  }

   {  Chapter 5.3,  Example 5,  Maximum Flow,  Size: 8x16,  Page 91  }


TITLE
    MaximumFlow;

INDEX
    node      := 0..7;

    FromNode  := node;
    ToNode    := node;

    SourceNodes[node] := (0, 1);
    SinkNodes[node]   := (5, 6, 7);
DATA
    FlowCapacity[FromNode,ToNode] := [ 0, 2,  12,
                                       1, 3,  20,
                                       2, 3,   6,
                                       2, 4,   3,
                                       2, 5,   6,
                                       3, 4,   7,
                                       3, 7,   9,
                                       4, 2,   2,
                                       4, 5,   5,
                                       4, 6,   8,
                                       7, 6,   4];


VARIABLES
    Flow[FromNode,ToNode] -> x
        WHERE (FlowCapacity);

    Sources[node IN SourceNodes];
    Sinks[node IN SinkNodes];

MODEL

    MAX TotalFlow = SUM(node IN SourceNodes: Sources);

SUBJECT TO

    FlowBalance[node]:

        SUM(FromNode: Flow[FromNode,ToNode:=node]) + Sources
      =
        SUM(ToNode: Flow[FromNode:=node,ToNode]) + Sinks;

BOUNDS
    Flow <= FlowCapacity;

END