Laboratoire de Génie Informatique et d’Automatique de l’Artois

Seminar

Position-guided local search for graph coloring

The 2 November 2010 at 14:00 Seminars room of the LGI2A, FSA, Béthune
Daniel PORUMBEL Associate professor LGI2A

We present two "position-guided" algorithms that work on top of a
local search process. These position-guided algorithms use search
space positional information so as to control the trajectory of the
underlying local search (i.e. Tabu Search).

The first algorithm performs a coarse-grained recording of its own
trajectory by recording a limited number of spheres (a sphere is the
set of potential solutions situated within a distance R from its
center). Even if the total number of visited solutions is enormous,
the number of visited spheres is always considerably smaller. The
objective of this first algorithm is to continually guide the
exploration toward as-yet-unvisited R-spheres, and so, to ensure
diversification.

A second intensification algorithm performs deep investigations only
within a "limited perimeter", in the proximity of a given potential
solution. For this, it employs a breath-first-search routine to
enumerate all R-spheres from this "limited perimeter". We
experimentally observed that if such a "limited perimeter" contains a
global optimum, the intensification algorithm does not fail in
eventually finding it.

By coupling the two algorithms, we reached very competitive results
for graph coloring. For example, we found for the first time the upper
bound k=223 for the DIMACS graph djsc1000.9 (available in the
literature since 1991).