MPL Model Library MPL Model Library



Maximum Flow,  Example 5.3-5,  H.P.Williams

   {  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 85  }


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



Return to MPL Model Library