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; |
---|