1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/examples/color.mod Mon Dec 06 13:09:21 2010 +0100
1.3 @@ -0,0 +1,113 @@
1.4 +/* COLOR, Graph Coloring Problem */
1.5 +
1.6 +/* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */
1.7 +
1.8 +/* Given an undirected loopless graph G = (V, E), where V is a set of
1.9 + nodes, E <= V x V is a set of arcs, the Graph Coloring Problem is to
1.10 + find a mapping (coloring) F: V -> C, where C = {1, 2, ... } is a set
1.11 + of colors whose cardinality is as small as possible, such that
1.12 + F(i) != F(j) for every arc (i,j) in E, that is adjacent nodes must
1.13 + be assigned different colors. */
1.14 +
1.15 +param n, integer, >= 2;
1.16 +/* number of nodes */
1.17 +
1.18 +set V := {1..n};
1.19 +/* set of nodes */
1.20 +
1.21 +set E, within V cross V;
1.22 +/* set of arcs */
1.23 +
1.24 +check{(i,j) in E}: i != j;
1.25 +/* there must be no loops */
1.26 +
1.27 +/* We need to estimate an upper bound of the number of colors |C|.
1.28 + The number of nodes |V| can be used, however, for sparse graphs such
1.29 + bound is not very good. To obtain a more suitable estimation we use
1.30 + an easy "greedy" heuristic. Let nodes 1, ..., i-1 are already
1.31 + assigned some colors. To assign a color to node i we see if there is
1.32 + an existing color not used for coloring nodes adjacent to node i. If
1.33 + so, we use this color, otherwise we introduce a new color. */
1.34 +
1.35 +set EE := setof{(i,j) in E} (i,j) union setof{(i,j) in E} (j,i);
1.36 +/* symmetrisized set of arcs */
1.37 +
1.38 +param z{i in V, case in 0..1} :=
1.39 +/* z[i,0] = color index assigned to node i
1.40 + z[i,1] = maximal color index used for nodes 1, 2, ..., i-1 which are
1.41 + adjacent to node i */
1.42 +( if case = 0 then
1.43 + ( /* compute z[i,0] */
1.44 + min{c in 1..z[i,1]}
1.45 + ( if not exists{j in V: j < i and (i,j) in EE} z[j,0] = c then
1.46 + c
1.47 + else
1.48 + z[i,1] + 1
1.49 + )
1.50 + )
1.51 + else
1.52 + ( /* compute z[i,1] */
1.53 + if not exists{j in V: j < i} (i,j) in EE then
1.54 + 1
1.55 + else
1.56 + max{j in V: j < i and (i,j) in EE} z[j,0]
1.57 + )
1.58 +);
1.59 +
1.60 +check{(i,j) in E}: z[i,0] != z[j,0];
1.61 +/* check that all adjacent nodes are assigned distinct colors */
1.62 +
1.63 +param nc := max{i in V} z[i,0];
1.64 +/* number of colors used by the heuristic; obviously, it is an upper
1.65 + bound of the optimal solution */
1.66 +
1.67 +display nc;
1.68 +
1.69 +var x{i in V, c in 1..nc}, binary;
1.70 +/* x[i,c] = 1 means that node i is assigned color c */
1.71 +
1.72 +var u{c in 1..nc}, binary;
1.73 +/* u[c] = 1 means that color c is used, i.e. assigned to some node */
1.74 +
1.75 +s.t. map{i in V}: sum{c in 1..nc} x[i,c] = 1;
1.76 +/* each node must be assigned exactly one color */
1.77 +
1.78 +s.t. arc{(i,j) in E, c in 1..nc}: x[i,c] + x[j,c] <= u[c];
1.79 +/* adjacent nodes cannot be assigned the same color */
1.80 +
1.81 +minimize obj: sum{c in 1..nc} u[c];
1.82 +/* objective is to minimize the number of colors used */
1.83 +
1.84 +data;
1.85 +
1.86 +/* These data correspond to the instance myciel3.col from:
1.87 + http://mat.gsia.cmu.edu/COLOR/instances.html */
1.88 +
1.89 +/* The optimal solution is 4 */
1.90 +
1.91 +param n := 11;
1.92 +
1.93 +set E :=
1.94 + 1 2
1.95 + 1 4
1.96 + 1 7
1.97 + 1 9
1.98 + 2 3
1.99 + 2 6
1.100 + 2 8
1.101 + 3 5
1.102 + 3 7
1.103 + 3 10
1.104 + 4 5
1.105 + 4 6
1.106 + 4 10
1.107 + 5 8
1.108 + 5 9
1.109 + 6 11
1.110 + 7 11
1.111 + 8 11
1.112 + 9 11
1.113 + 10 11
1.114 +;
1.115 +
1.116 +end;