lemon-project-template-glpk
diff 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 diff
1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 1.2 +++ b/deps/glpk/examples/maxflow.mod Sun Nov 06 20:59:10 2011 +0100 1.3 @@ -0,0 +1,83 @@ 1.4 +/* MAXFLOW, Maximum Flow Problem */ 1.5 + 1.6 +/* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */ 1.7 + 1.8 +/* The Maximum Flow Problem in a network G = (V, E), where V is a set 1.9 + of nodes, E within V x V is a set of arcs, is to maximize the flow 1.10 + from one given node s (source) to another given node t (sink) subject 1.11 + to conservation of flow constraints at each node and flow capacities 1.12 + on each arc. */ 1.13 + 1.14 +param n, integer, >= 2; 1.15 +/* number of nodes */ 1.16 + 1.17 +set V, default {1..n}; 1.18 +/* set of nodes */ 1.19 + 1.20 +set E, within V cross V; 1.21 +/* set of arcs */ 1.22 + 1.23 +param a{(i,j) in E}, > 0; 1.24 +/* a[i,j] is capacity of arc (i,j) */ 1.25 + 1.26 +param s, symbolic, in V, default 1; 1.27 +/* source node */ 1.28 + 1.29 +param t, symbolic, in V, != s, default n; 1.30 +/* sink node */ 1.31 + 1.32 +var x{(i,j) in E}, >= 0, <= a[i,j]; 1.33 +/* x[i,j] is elementary flow through arc (i,j) to be found */ 1.34 + 1.35 +var flow, >= 0; 1.36 +/* total flow from s to t */ 1.37 + 1.38 +s.t. node{i in V}: 1.39 +/* node[i] is conservation constraint for node i */ 1.40 + 1.41 + sum{(j,i) in E} x[j,i] + (if i = s then flow) 1.42 + /* summary flow into node i through all ingoing arcs */ 1.43 + 1.44 + = /* must be equal to */ 1.45 + 1.46 + sum{(i,j) in E} x[i,j] + (if i = t then flow); 1.47 + /* summary flow from node i through all outgoing arcs */ 1.48 + 1.49 +maximize obj: flow; 1.50 +/* objective is to maximize the total flow through the network */ 1.51 + 1.52 +solve; 1.53 + 1.54 +printf{1..56} "="; printf "\n"; 1.55 +printf "Maximum flow from node %s to node %s is %g\n\n", s, t, flow; 1.56 +printf "Starting node Ending node Arc capacity Flow in arc\n"; 1.57 +printf "------------- ----------- ------------ -----------\n"; 1.58 +printf{(i,j) in E: x[i,j] != 0}: "%13s %11s %12g %11g\n", i, j, 1.59 + a[i,j], x[i,j]; 1.60 +printf{1..56} "="; printf "\n"; 1.61 + 1.62 +data; 1.63 + 1.64 +/* These data correspond to an example from [Christofides]. */ 1.65 + 1.66 +/* Optimal solution is 29 */ 1.67 + 1.68 +param n := 9; 1.69 + 1.70 +param : E : a := 1.71 + 1 2 14 1.72 + 1 4 23 1.73 + 2 3 10 1.74 + 2 4 9 1.75 + 3 5 12 1.76 + 3 8 18 1.77 + 4 5 26 1.78 + 5 2 11 1.79 + 5 6 25 1.80 + 5 7 4 1.81 + 6 7 7 1.82 + 6 8 8 1.83 + 7 9 15 1.84 + 8 9 20; 1.85 + 1.86 +end;