Generalised graph colouring by a hybrid of local search and constraint programming

AbstractThe IMPASSE class of local search algorithms have given good results on many vertex colouring benchmarks. Previous work enhanced IMPASSE by adding the constraint programming technique of forward checking, in order to prune colouration neighbourhoods during search. On several large graphs the algorithm found the best known colourings. This paper extends the work by improving the heuristics and generalising the approach to bandwidth multicolouring. It is shown to give better results than a related search algorithm on an integer programming model, and to be competitive with published results. Experiments indicate that stronger constraint propagation further improves search performance, but that a symmetry breaking technique has unpredictable effects