COIN-OR::LEMON - Graph Library

source: glpk-cmake/examples/color.mod @ 1:c445c931472f

Last change on this file since 1:c445c931472f was 1:c445c931472f, checked in by Alpar Juttner <alpar@…>, 10 years ago

Import glpk-4.45

  • Generated files and doc/notes are removed
File size: 2.8 KB
Line 
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
12param n, integer, >= 2;
13/* number of nodes */
14
15set V := {1..n};
16/* set of nodes */
17
18set E, within V cross V;
19/* set of arcs */
20
21check{(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
32set EE := setof{(i,j) in E} (i,j) union setof{(i,j) in E} (j,i);
33/* symmetrisized set of arcs */
34
35param 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
57check{(i,j) in E}: z[i,0] != z[j,0];
58/* check that all adjacent nodes are assigned distinct colors */
59
60param 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
64display nc;
65
66var x{i in V, c in 1..nc}, binary;
67/* x[i,c] = 1 means that node i is assigned color c */
68
69var u{c in 1..nc}, binary;
70/* u[c] = 1 means that color c is used, i.e. assigned to some node */
71
72s.t. map{i in V}: sum{c in 1..nc} x[i,c] = 1;
73/* each node must be assigned exactly one color */
74
75s.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
78minimize obj: sum{c in 1..nc} u[c];
79/* objective is to minimize the number of colors used */
80
81data;
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
88param n := 11;
89
90set 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
113end;
Note: See TracBrowser for help on using the repository browser.