 # Untitled

a guest
Aug 21st, 2016
220
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. /* save this file as color.txt then run: ./glpsol --math -o solution.txt color.txt */
2.
3. /* COLOR, Graph Coloring Problem */
4.
5. /* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */
6.
7. /* Given an undirected loopless graph G = (V, E), where V is a set of
8. nodes, E <= V x V is a set of arcs, the Graph Coloring Problem is to
9. find a mapping (coloring) F: V -> C, where C = {1, 2, ... } is a set
10. of colors whose cardinality is as small as possible, such that
11. F(i) != F(j) for every arc (i,j) in E, that is adjacent nodes must
12. be assigned different colors. */
13.
14. param n, integer, >= 2;
15. /* number of nodes */
16.
17. set V := {1..n};
18. /* set of nodes */
19.
20. set E, within V cross V;
21. /* set of arcs */
22.
23. check{(i,j) in E}: i != j;
24. /* there must be no loops */
25.
26. /* We need to estimate an upper bound of the number of colors |C|.
27. The number of nodes |V| can be used, however, for sparse graphs such
28. bound is not very good. To obtain a more suitable estimation we use
29. an easy "greedy" heuristic. Let nodes 1, ..., i-1 are already
30. assigned some colors. To assign a color to node i we see if there is
31. an existing color not used for coloring nodes adjacent to node i. If
32. so, we use this color, otherwise we introduce a new color. */
33.
34. set EE := setof{(i,j) in E} (i,j) union setof{(i,j) in E} (j,i);
35. /* symmetrisized set of arcs */
36.
37. param z{i in V, case in 0..1} :=
38. /* z[i,0] = color index assigned to node i
39. z[i,1] = maximal color index used for nodes 1, 2, ..., i-1 which are
40. adjacent to node i */
41. ( if case = 0 then
42. ( /* compute z[i,0] */
43. min{c in 1..z[i,1]}
44. ( if not exists{j in V: j < i and (i,j) in EE} z[j,0] = c then
45. c
46. else
47. z[i,1] + 1
48. )
49. )
50. else
51. ( /* compute z[i,1] */
52. if not exists{j in V: j < i} (i,j) in EE then
53. 1
54. else
55. max{j in V: j < i and (i,j) in EE} z[j,0]
56. )
57. );
58.
59. check{(i,j) in E}: z[i,0] != z[j,0];
60. /* check that all adjacent nodes are assigned distinct colors */
61.
62. param nc := max{i in V} z[i,0];
63. /* number of colors used by the heuristic; obviously, it is an upper
64. bound of the optimal solution */
65.
66. display nc;
67.
68. var x{i in V, c in 1..nc}, binary;
69. /* x[i,c] = 1 means that node i is assigned color c */
70.
71. var u{c in 1..nc}, binary;
72. /* u[c] = 1 means that color c is used, i.e. assigned to some node */
73.
74. var color{i in 1..n}, integer;
75.
76. s.t. map{i in V}: sum{c in 1..nc} x[i,c] = 1;
77. /* each node must be assigned exactly one color */
78.
79. s.t. arc{(i,j) in E, c in 1..nc}: x[i,c] + x[j,c] <= u[c];
80. /* adjacent nodes cannot be assigned the same color */
81.
82. minimize obj: sum{c in 1..nc} u[c];
83. /* objective is to minimize the number of colors used */
84.
85. solve;
86.
87. for{i in V,c in 1..nc:x[i,c]}printf"%d %d\n",i,c;
88.
89. data;
90.
91. param n := 19;
92.
93. set E :=
94. 1 3
95. 1 8
96. 1 11
97. 1 12
98. 1 16
99. 1 19
100. 2 3
101. 2 4
102. 2 6
103. 2 8
104. 2 10
105. 2 11
106. 2 12
107. 2 15
108. 2 16
109. 3 11
110. 3 12
111. 3 14
112. 3 16
113. 4 5
114. 4 9
115. 4 12
116. 4 14
117. 4 15
118. 4 16
119. 5 12
120. 6 14
121. 6 19
122. 7 18
123. 7 19
124. 8 16
125. 8 18
126. 10 14
127. 10 19
128. 11 19
129. 12 13
130. 12 15
131. 12 17
132. 12 18
133. 13 19
134. 14 18
135. 14 19
136. 16 19
137. ;
138.
139. end;