alpar@1: /* COLOR, Graph Coloring Problem */
alpar@1: 
alpar@1: /* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */
alpar@1: 
alpar@1: /* Given an undirected loopless graph G = (V, E), where V is a set of
alpar@1:    nodes, E <= V x V is a set of arcs, the Graph Coloring Problem is to
alpar@1:    find a mapping (coloring) F: V -> C, where C = {1, 2, ... } is a set
alpar@1:    of colors whose cardinality is as small as possible, such that
alpar@1:    F(i) != F(j) for every arc (i,j) in E, that is adjacent nodes must
alpar@1:    be assigned different colors. */
alpar@1: 
alpar@1: param n, integer, >= 2;
alpar@1: /* number of nodes */
alpar@1: 
alpar@1: set V := {1..n};
alpar@1: /* set of nodes */
alpar@1: 
alpar@1: set E, within V cross V;
alpar@1: /* set of arcs */
alpar@1: 
alpar@1: check{(i,j) in E}: i != j;
alpar@1: /* there must be no loops */
alpar@1: 
alpar@1: /* We need to estimate an upper bound of the number of colors |C|.
alpar@1:    The number of nodes |V| can be used, however, for sparse graphs such
alpar@1:    bound is not very good. To obtain a more suitable estimation we use
alpar@1:    an easy "greedy" heuristic. Let nodes 1, ..., i-1 are already
alpar@1:    assigned some colors. To assign a color to node i we see if there is
alpar@1:    an existing color not used for coloring nodes adjacent to node i. If
alpar@1:    so, we use this color, otherwise we introduce a new color. */
alpar@1: 
alpar@1: set EE := setof{(i,j) in E} (i,j) union setof{(i,j) in E} (j,i);
alpar@1: /* symmetrisized set of arcs */
alpar@1: 
alpar@1: param z{i in V, case in 0..1} :=
alpar@1: /* z[i,0] = color index assigned to node i
alpar@1:    z[i,1] = maximal color index used for nodes 1, 2, ..., i-1 which are
alpar@1:             adjacent to node i */
alpar@1: (  if case = 0 then
alpar@1:    (  /* compute z[i,0] */
alpar@1:       min{c in 1..z[i,1]}
alpar@1:       (  if not exists{j in V: j < i and (i,j) in EE} z[j,0] = c then
alpar@1:             c
alpar@1:          else
alpar@1:             z[i,1] + 1
alpar@1:       )
alpar@1:    )
alpar@1:    else
alpar@1:    (  /* compute z[i,1] */
alpar@1:       if not exists{j in V: j < i} (i,j) in EE then
alpar@1:          1
alpar@1:       else
alpar@1:          max{j in V: j < i and (i,j) in EE} z[j,0]
alpar@1:    )
alpar@1: );
alpar@1: 
alpar@1: check{(i,j) in E}: z[i,0] != z[j,0];
alpar@1: /* check that all adjacent nodes are assigned distinct colors */
alpar@1: 
alpar@1: param nc := max{i in V} z[i,0];
alpar@1: /* number of colors used by the heuristic; obviously, it is an upper
alpar@1:    bound of the optimal solution */
alpar@1: 
alpar@1: display nc;
alpar@1: 
alpar@1: var x{i in V, c in 1..nc}, binary;
alpar@1: /* x[i,c] = 1 means that node i is assigned color c */
alpar@1: 
alpar@1: var u{c in 1..nc}, binary;
alpar@1: /* u[c] = 1 means that color c is used, i.e. assigned to some node */
alpar@1: 
alpar@1: s.t. map{i in V}: sum{c in 1..nc} x[i,c] = 1;
alpar@1: /* each node must be assigned exactly one color */
alpar@1: 
alpar@1: s.t. arc{(i,j) in E, c in 1..nc}: x[i,c] + x[j,c] <= u[c];
alpar@1: /* adjacent nodes cannot be assigned the same color */
alpar@1: 
alpar@1: minimize obj: sum{c in 1..nc} u[c];
alpar@1: /* objective is to minimize the number of colors used */
alpar@1: 
alpar@1: data;
alpar@1: 
alpar@1: /* These data correspond to the instance myciel3.col from:
alpar@1:    http://mat.gsia.cmu.edu/COLOR/instances.html */
alpar@1: 
alpar@1: /* The optimal solution is 4 */
alpar@1: 
alpar@1: param n := 11;
alpar@1: 
alpar@1: set E :=
alpar@1:  1 2
alpar@1:  1 4
alpar@1:  1 7
alpar@1:  1 9
alpar@1:  2 3
alpar@1:  2 6
alpar@1:  2 8
alpar@1:  3 5
alpar@1:  3 7
alpar@1:  3 10
alpar@1:  4 5
alpar@1:  4 6
alpar@1:  4 10
alpar@1:  5 8
alpar@1:  5 9
alpar@1:  6 11
alpar@1:  7 11
alpar@1:  8 11
alpar@1:  9 11
alpar@1:  10 11
alpar@1: ;
alpar@1: 
alpar@1: end;