lemon-project-template-glpk
view deps/glpk/examples/color.mod @ 9:33de93886c88
Import GLPK 4.47
| author | Alpar Juttner <alpar@cs.elte.hu> |
|---|---|
| date | Sun, 06 Nov 2011 20:59:10 +0100 |
| parents | |
| children |
line source
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;
13 /* number of nodes */
15 set V := {1..n};
16 /* set of nodes */
18 set E, within V cross V;
19 /* set of arcs */
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
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 );
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 */
64 display nc;
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 */
81 data;
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 */
88 param n := 11;
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 ;
113 end;