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