Groupe d’études et de recherche en analyse des décisions

G-91-33

Local Optima Topology for the k-coloring Problem

, et

In a first attempt to explain the good behavior of local improvement heuristics (such as Tabu Search and Simulated Annealing) for the k-coloring problem, we study the topology of the local optima. We first propose an efficient procedure for generating all local optima. Then, we devise statistical tests for analyzing their topology, e.g., the number of local optima with respect to their value or the depth of the valleys. Finally, computational results are presented.

, 37 pages

Ce cahier a été révisé en janvier 1992