1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/examples/maxflow.mod	Mon Dec 06 13:09:21 2010 +0100
     1.3 @@ -0,0 +1,83 @@
     1.4 +/* MAXFLOW, Maximum Flow Problem */
     1.5 +
     1.6 +/* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */
     1.7 +
     1.8 +/* The Maximum Flow Problem in a network G = (V, E), where V is a set
     1.9 +   of nodes, E within V x V is a set of arcs, is to maximize the flow
    1.10 +   from one given node s (source) to another given node t (sink) subject
    1.11 +   to conservation of flow constraints at each node and flow capacities
    1.12 +   on each arc. */
    1.13 +
    1.14 +param n, integer, >= 2;
    1.15 +/* number of nodes */
    1.16 +
    1.17 +set V, default {1..n};
    1.18 +/* set of nodes */
    1.19 +
    1.20 +set E, within V cross V;
    1.21 +/* set of arcs */
    1.22 +
    1.23 +param a{(i,j) in E}, > 0;
    1.24 +/* a[i,j] is capacity of arc (i,j) */
    1.25 +
    1.26 +param s, symbolic, in V, default 1;
    1.27 +/* source node */
    1.28 +
    1.29 +param t, symbolic, in V, != s, default n;
    1.30 +/* sink node */
    1.31 +
    1.32 +var x{(i,j) in E}, >= 0, <= a[i,j];
    1.33 +/* x[i,j] is elementary flow through arc (i,j) to be found */
    1.34 +
    1.35 +var flow, >= 0;
    1.36 +/* total flow from s to t */
    1.37 +
    1.38 +s.t. node{i in V}:
    1.39 +/* node[i] is conservation constraint for node i */
    1.40 +
    1.41 +   sum{(j,i) in E} x[j,i] + (if i = s then flow)
    1.42 +   /* summary flow into node i through all ingoing arcs */
    1.43 +
    1.44 +   = /* must be equal to */
    1.45 +
    1.46 +   sum{(i,j) in E} x[i,j] + (if i = t then flow);
    1.47 +   /* summary flow from node i through all outgoing arcs */
    1.48 +
    1.49 +maximize obj: flow;
    1.50 +/* objective is to maximize the total flow through the network */
    1.51 +
    1.52 +solve;
    1.53 +
    1.54 +printf{1..56} "="; printf "\n";
    1.55 +printf "Maximum flow from node %s to node %s is %g\n\n", s, t, flow;
    1.56 +printf "Starting node   Ending node   Arc capacity   Flow in arc\n";
    1.57 +printf "-------------   -----------   ------------   -----------\n";
    1.58 +printf{(i,j) in E: x[i,j] != 0}: "%13s   %11s   %12g   %11g\n", i, j,
    1.59 +   a[i,j], x[i,j];
    1.60 +printf{1..56} "="; printf "\n";
    1.61 +
    1.62 +data;
    1.63 +
    1.64 +/* These data correspond to an example from [Christofides]. */
    1.65 +
    1.66 +/* Optimal solution is 29 */
    1.67 +
    1.68 +param n := 9;
    1.69 +
    1.70 +param : E :   a :=
    1.71 +       1 2   14
    1.72 +       1 4   23
    1.73 +       2 3   10
    1.74 +       2 4    9
    1.75 +       3 5   12
    1.76 +       3 8   18
    1.77 +       4 5   26
    1.78 +       5 2   11
    1.79 +       5 6   25
    1.80 +       5 7    4
    1.81 +       6 7    7
    1.82 +       6 8    8
    1.83 +       7 9   15
    1.84 +       8 9   20;
    1.85 +
    1.86 +end;