lemon-project-template-glpk
view deps/glpk/examples/maxflow.mod @ 9:33de93886c88
Import GLPK 4.47
| author | Alpar Juttner <alpar@cs.elte.hu> |
|---|---|
| date | Sun, 06 Nov 2011 20:59:10 +0100 |
| parents | |
| children |
line source
1 /* MAXFLOW, Maximum Flow Problem */
3 /* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */
5 /* The Maximum Flow Problem in a network G = (V, E), where V is a set
6 of nodes, E within V x V is a set of arcs, is to maximize the flow
7 from one given node s (source) to another given node t (sink) subject
8 to conservation of flow constraints at each node and flow capacities
9 on each arc. */
11 param n, integer, >= 2;
12 /* number of nodes */
14 set V, default {1..n};
15 /* set of nodes */
17 set E, within V cross V;
18 /* set of arcs */
20 param a{(i,j) in E}, > 0;
21 /* a[i,j] is capacity of arc (i,j) */
23 param s, symbolic, in V, default 1;
24 /* source node */
26 param t, symbolic, in V, != s, default n;
27 /* sink node */
29 var x{(i,j) in E}, >= 0, <= a[i,j];
30 /* x[i,j] is elementary flow through arc (i,j) to be found */
32 var flow, >= 0;
33 /* total flow from s to t */
35 s.t. node{i in V}:
36 /* node[i] is conservation constraint for node i */
38 sum{(j,i) in E} x[j,i] + (if i = s then flow)
39 /* summary flow into node i through all ingoing arcs */
41 = /* must be equal to */
43 sum{(i,j) in E} x[i,j] + (if i = t then flow);
44 /* summary flow from node i through all outgoing arcs */
46 maximize obj: flow;
47 /* objective is to maximize the total flow through the network */
49 solve;
51 printf{1..56} "="; printf "\n";
52 printf "Maximum flow from node %s to node %s is %g\n\n", s, t, flow;
53 printf "Starting node Ending node Arc capacity Flow in arc\n";
54 printf "------------- ----------- ------------ -----------\n";
55 printf{(i,j) in E: x[i,j] != 0}: "%13s %11s %12g %11g\n", i, j,
56 a[i,j], x[i,j];
57 printf{1..56} "="; printf "\n";
59 data;
61 /* These data correspond to an example from [Christofides]. */
63 /* Optimal solution is 29 */
65 param n := 9;
67 param : E : a :=
68 1 2 14
69 1 4 23
70 2 3 10
71 2 4 9
72 3 5 12
73 3 8 18
74 4 5 26
75 5 2 11
76 5 6 25
77 5 7 4
78 6 7 7
79 6 8 8
80 7 9 15
81 8 9 20;
83 end;