/* COLOR, Graph Coloring Problem */

/* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */

/* Given an undirected loopless graph G = (V, E), where V is a set of

   nodes, E <= V x V is a set of arcs, the Graph Coloring Problem is to

   find a mapping (coloring) F: V -> C, where C = {1, 2, ... } is a set

   of colors whose cardinality is as small as possible, such that

   F(i) != F(j) for every arc (i,j) in E, that is adjacent nodes must

   be assigned different colors. */

param n, integer, >= 2;

/* number of nodes */

set V := {1..n};

/* set of nodes */

set E, within V cross V;

/* set of arcs */

check{(i,j) in E}: i != j;

/* there must be no loops */

/* We need to estimate an upper bound of the number of colors |C|.

   The number of nodes |V| can be used, however, for sparse graphs such

   bound is not very good. To obtain a more suitable estimation we use

   an easy "greedy" heuristic. Let nodes 1, ..., i-1 are already

   assigned some colors. To assign a color to node i we see if there is

   an existing color not used for coloring nodes adjacent to node i. If

   so, we use this color, otherwise we introduce a new color. */

set EE := setof{(i,j) in E} (i,j) union setof{(i,j) in E} (j,i);

/* symmetrisized set of arcs */

param z{i in V, case in 0..1} :=

/* z[i,0] = color index assigned to node i

   z[i,1] = maximal color index used for nodes 1, 2, ..., i-1 which are

            adjacent to node i */

(  if case = 0 then

   (  /* compute z[i,0] */

      min{c in 1..z[i,1]}

      (  if not exists{j in V: j < i and (i,j) in EE} z[j,0] = c then

            c

         else

            z[i,1] + 1

      )

   )

   else

   (  /* compute z[i,1] */

      if not exists{j in V: j < i} (i,j) in EE then

         1

      else

         max{j in V: j < i and (i,j) in EE} z[j,0]

   )

);

check{(i,j) in E}: z[i,0] != z[j,0];

/* check that all adjacent nodes are assigned distinct colors */

param nc := max{i in V} z[i,0];

/* number of colors used by the heuristic; obviously, it is an upper

   bound of the optimal solution */

display nc;

var x{i in V, c in 1..nc}, binary;

/* x[i,c] = 1 means that node i is assigned color c */

var u{c in 1..nc}, binary;

/* u[c] = 1 means that color c is used, i.e. assigned to some node */

s.t. map{i in V}: sum{c in 1..nc} x[i,c] = 1;

/* each node must be assigned exactly one color */

s.t. arc{(i,j) in E, c in 1..nc}: x[i,c] + x[j,c] <= u[c];

/* adjacent nodes cannot be assigned the same color */

minimize obj: sum{c in 1..nc} u[c];

/* objective is to minimize the number of colors used */

data;

/* These data correspond to the instance myciel3.col from:

   http://mat.gsia.cmu.edu/COLOR/instances.html */

/* The optimal solution is 4 */

param n := 11;

set E :=

 1 2

 1 4

 1 7

 1 9

 2 3

 2 6

 2 8

 3 5

 3 7

 3 10

 4 5

 4 6

 4 10

 5 8

 5 9

 6 11

 7 11

 8 11

 9 11

 10 11

;

end;