| Abstract: | 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 evaluating and comparing such heuristics. Computational results are presented to support these observations. |
