|
1 /* MAXFLOW, Maximum Flow Problem */ |
|
2 |
|
3 /* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */ |
|
4 |
|
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. */ |
|
10 |
|
11 param n, integer, >= 2; |
|
12 /* number of nodes */ |
|
13 |
|
14 set V, default {1..n}; |
|
15 /* set of nodes */ |
|
16 |
|
17 set E, within V cross V; |
|
18 /* set of arcs */ |
|
19 |
|
20 param a{(i,j) in E}, > 0; |
|
21 /* a[i,j] is capacity of arc (i,j) */ |
|
22 |
|
23 param s, symbolic, in V, default 1; |
|
24 /* source node */ |
|
25 |
|
26 param t, symbolic, in V, != s, default n; |
|
27 /* sink node */ |
|
28 |
|
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 */ |
|
31 |
|
32 var flow, >= 0; |
|
33 /* total flow from s to t */ |
|
34 |
|
35 s.t. node{i in V}: |
|
36 /* node[i] is conservation constraint for node i */ |
|
37 |
|
38 sum{(j,i) in E} x[j,i] + (if i = s then flow) |
|
39 /* summary flow into node i through all ingoing arcs */ |
|
40 |
|
41 = /* must be equal to */ |
|
42 |
|
43 sum{(i,j) in E} x[i,j] + (if i = t then flow); |
|
44 /* summary flow from node i through all outgoing arcs */ |
|
45 |
|
46 maximize obj: flow; |
|
47 /* objective is to maximize the total flow through the network */ |
|
48 |
|
49 solve; |
|
50 |
|
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"; |
|
58 |
|
59 data; |
|
60 |
|
61 /* These data correspond to an example from [Christofides]. */ |
|
62 |
|
63 /* Optimal solution is 29 */ |
|
64 |
|
65 param n := 9; |
|
66 |
|
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; |
|
82 |
|
83 end; |