alpar@1: /* MAXFLOW, Maximum Flow Problem */
alpar@1: 
alpar@1: /* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */
alpar@1: 
alpar@1: /* The Maximum Flow Problem in a network G = (V, E), where V is a set
alpar@1:    of nodes, E within V x V is a set of arcs, is to maximize the flow
alpar@1:    from one given node s (source) to another given node t (sink) subject
alpar@1:    to conservation of flow constraints at each node and flow capacities
alpar@1:    on each arc. */
alpar@1: 
alpar@1: param n, integer, >= 2;
alpar@1: /* number of nodes */
alpar@1: 
alpar@1: set V, default {1..n};
alpar@1: /* set of nodes */
alpar@1: 
alpar@1: set E, within V cross V;
alpar@1: /* set of arcs */
alpar@1: 
alpar@1: param a{(i,j) in E}, > 0;
alpar@1: /* a[i,j] is capacity of arc (i,j) */
alpar@1: 
alpar@1: param s, symbolic, in V, default 1;
alpar@1: /* source node */
alpar@1: 
alpar@1: param t, symbolic, in V, != s, default n;
alpar@1: /* sink node */
alpar@1: 
alpar@1: var x{(i,j) in E}, >= 0, <= a[i,j];
alpar@1: /* x[i,j] is elementary flow through arc (i,j) to be found */
alpar@1: 
alpar@1: var flow, >= 0;
alpar@1: /* total flow from s to t */
alpar@1: 
alpar@1: s.t. node{i in V}:
alpar@1: /* node[i] is conservation constraint for node i */
alpar@1: 
alpar@1:    sum{(j,i) in E} x[j,i] + (if i = s then flow)
alpar@1:    /* summary flow into node i through all ingoing arcs */
alpar@1: 
alpar@1:    = /* must be equal to */
alpar@1: 
alpar@1:    sum{(i,j) in E} x[i,j] + (if i = t then flow);
alpar@1:    /* summary flow from node i through all outgoing arcs */
alpar@1: 
alpar@1: maximize obj: flow;
alpar@1: /* objective is to maximize the total flow through the network */
alpar@1: 
alpar@1: solve;
alpar@1: 
alpar@1: printf{1..56} "="; printf "\n";
alpar@1: printf "Maximum flow from node %s to node %s is %g\n\n", s, t, flow;
alpar@1: printf "Starting node   Ending node   Arc capacity   Flow in arc\n";
alpar@1: printf "-------------   -----------   ------------   -----------\n";
alpar@1: printf{(i,j) in E: x[i,j] != 0}: "%13s   %11s   %12g   %11g\n", i, j,
alpar@1:    a[i,j], x[i,j];
alpar@1: printf{1..56} "="; printf "\n";
alpar@1: 
alpar@1: data;
alpar@1: 
alpar@1: /* These data correspond to an example from [Christofides]. */
alpar@1: 
alpar@1: /* Optimal solution is 29 */
alpar@1: 
alpar@1: param n := 9;
alpar@1: 
alpar@1: param : E :   a :=
alpar@1:        1 2   14
alpar@1:        1 4   23
alpar@1:        2 3   10
alpar@1:        2 4    9
alpar@1:        3 5   12
alpar@1:        3 8   18
alpar@1:        4 5   26
alpar@1:        5 2   11
alpar@1:        5 6   25
alpar@1:        5 7    4
alpar@1:        6 7    7
alpar@1:        6 8    8
alpar@1:        7 9   15
alpar@1:        8 9   20;
alpar@1: 
alpar@1: end;