COIN-OR::LEMON - Graph Library

source: lemon-project-template-glpk/deps/glpk/examples/maxflow.mod

subpack-glpk
Last change on this file was 9:33de93886c88, checked in by Alpar Juttner <alpar@…>, 13 years ago

Import GLPK 4.47

File size: 2.0 KB
Line 
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
11param n, integer, >= 2;
12/* number of nodes */
13
14set V, default {1..n};
15/* set of nodes */
16
17set E, within V cross V;
18/* set of arcs */
19
20param a{(i,j) in E}, > 0;
21/* a[i,j] is capacity of arc (i,j) */
22
23param s, symbolic, in V, default 1;
24/* source node */
25
26param t, symbolic, in V, != s, default n;
27/* sink node */
28
29var x{(i,j) in E}, >= 0, <= a[i,j];
30/* x[i,j] is elementary flow through arc (i,j) to be found */
31
32var flow, >= 0;
33/* total flow from s to t */
34
35s.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
46maximize obj: flow;
47/* objective is to maximize the total flow through the network */
48
49solve;
50
51printf{1..56} "="; printf "\n";
52printf "Maximum flow from node %s to node %s is %g\n\n", s, t, flow;
53printf "Starting node   Ending node   Arc capacity   Flow in arc\n";
54printf "-------------   -----------   ------------   -----------\n";
55printf{(i,j) in E: x[i,j] != 0}: "%13s   %11s   %12g   %11g\n", i, j,
56   a[i,j], x[i,j];
57printf{1..56} "="; printf "\n";
58
59data;
60
61/* These data correspond to an example from [Christofides]. */
62
63/* Optimal solution is 29 */
64
65param n := 9;
66
67param : 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
83end;
Note: See TracBrowser for help on using the repository browser.