Structural analysis of local search heuristics in combinatorial optimization (Q1095797)

Neighborhood, or local, search is a popular and practical heuristic for many combinational optimization problems. We examine the neighborhood structures of two classes of problems, 0-1 integer programming and the mean tardiness job sequencing problem - from the viewpoint of state-space graphs in artificial intelligence. Such analysis is shown to provide fundamental insights into the nature of local search algorithms, and provides a useful framework for evaluation and comparing such heurstics. Computational results are presented to support these observations.