Heuristic rope team : a parallel algorithm for graph coloring

Optimization problems are often compared to mountain climbing. In particular, the classical Hill Climber is a so used local search. In this paper we propose to explore further the analogy with climbing a mountain, not alone as it is generally the case but in rope team. Indeed, for difficult problems a single climber (heuristic) can easily be trapped into a local optimum. This situation can be compared to a crevasse which the heuristic can not escape from. In this paper we propose the Rope Team heuristic dealing with several elementary memetic heuristics which corresponds to climbers. The leader of the rope team bring with him at least one other climber, linked by a rope, in order to help him to escape from a local optimum. This approach has been successfully applied to one of the most studied combinatorial problem: the Graph Coloring Problem. The advantage of this approach is twofold: on one hand, it is able to find the best known solution for most of the difficult graphs coming from the DIMACS benchmark; on the other hand, all climbers can be considered simultaneously, allowing parallelization of the algorithm. Among the significant results of this work we can notice 3 well-studied graphs, DSJC500.5 colored with 47 colors, DSJC1000.5 with 82 colors and flat1000 76 0 with 81 colors.