lemon-project-template-glpk
comparison 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 |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:ce72246e44f7 |
---|---|
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; |