• API
• FAQ
• Tools
• Archive
SHARE
TWEET # Untitled a guest Aug 21st, 2016 110 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;
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top