Group for Research in Decision Analysis

G-91-33

Local Optima Topology for the k-coloring Problem

, , and

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

This cahier was revised in January 1992