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