1 /* COLOR, Graph Coloring Problem */
3 /* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */
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. */
12 param n, integer, >= 2;
18 set E, within V cross V;
21 check{(i,j) in E}: i != j;
22 /* there must be no loops */
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. */
32 set EE := setof{(i,j) in E} (i,j) union setof{(i,j) in E} (j,i);
33 /* symmetrisized set of arcs */
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
40 ( /* compute z[i,0] */
42 ( if not exists{j in V: j < i and (i,j) in EE} z[j,0] = c then
49 ( /* compute z[i,1] */
50 if not exists{j in V: j < i} (i,j) in EE then
53 max{j in V: j < i and (i,j) in EE} z[j,0]
57 check{(i,j) in E}: z[i,0] != z[j,0];
58 /* check that all adjacent nodes are assigned distinct colors */
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 */
66 var x{i in V, c in 1..nc}, binary;
67 /* x[i,c] = 1 means that node i is assigned color c */
69 var u{c in 1..nc}, binary;
70 /* u[c] = 1 means that color c is used, i.e. assigned to some node */
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 */
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 */
78 minimize obj: sum{c in 1..nc} u[c];
79 /* objective is to minimize the number of colors used */
83 /* These data correspond to the instance myciel3.col from:
84 http://mat.gsia.cmu.edu/COLOR/instances.html */
86 /* The optimal solution is 4 */