1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
|
/* MAXFLOW, Maximum Flow Problem */
/* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */
/* The Maximum Flow Problem in a network G = (V, E), where V is a set
of nodes, E within V x V is a set of arcs, is to maximize the flow
from one given node s (source) to another given node t (sink) subject
to conservation of flow constraints at each node and flow capacities
on each arc. */
param n, integer, >= 2;
/* number of nodes */
set V, default {1..n};
/* set of nodes */
set E, within V cross V;
/* set of arcs */
param a{(i,j) in E}, > 0;
/* a[i,j] is capacity of arc (i,j) */
param s, symbolic, in V, default 1;
/* source node */
param t, symbolic, in V, != s, default n;
/* sink node */
var x{(i,j) in E}, >= 0, <= a[i,j];
/* x[i,j] is elementary flow through arc (i,j) to be found */
var flow, >= 0;
/* total flow from s to t */
s.t. node{i in V}:
/* node[i] is conservation constraint for node i */
sum{(j,i) in E} x[j,i] + (if i = s then flow)
/* summary flow into node i through all ingoing arcs */
= /* must be equal to */
sum{(i,j) in E} x[i,j] + (if i = t then flow);
/* summary flow from node i through all outgoing arcs */
maximize obj: flow;
/* objective is to maximize the total flow through the network */
solve;
printf{1..56} "="; printf "\n";
printf "Maximum flow from node %s to node %s is %g\n\n", s, t, flow;
printf "Starting node Ending node Arc capacity Flow in arc\n";
printf "------------- ----------- ------------ -----------\n";
printf{(i,j) in E: x[i,j] != 0}: "%13s %11s %12g %11g\n", i, j,
a[i,j], x[i,j];
printf{1..56} "="; printf "\n";
data;
/* These data correspond to an example from [Christofides]. */
/* Optimal solution is 29 */
param n := 9;
param : E : a :=
1 2 14
1 4 23
2 3 10
2 4 9
3 5 12
3 8 18
4 5 26
5 2 11
5 6 25
5 7 4
6 7 7
6 8 8
7 9 15
8 9 20;
end;
|
