Empirical and analytic approaches to understanding local search heuristics

Local search heuristics are algorithms for combinatorial optimization that operate by executing walks over search graphs containing possible solutions. Because these methods have been highly successful in many application domains and can easily be applied to new problems, they are among the most widely utilized optimization techniques. However, the essential task of predicting their performance remains difficult.; In this thesis we first present a new empirical method that can be used to predict and optimize heuristic behavior. Under this approach, statistics about important characteristics of a search graph are gathered directly and used to build a model of the search graph that supports causal prediction about algorithm behavior. In this way the question of how an algorithm will perform on a problem is separated into two distinct questions: what are the features of the search graph, and how will an algorithm behave on a search graph with these features? Using these predictive models we can select appropriate algorithms and design new algorithms for the problem.; The data required for this approach cannot be gathered through random sampling because solutions become exponentially rare with increasing quality. However, search graphs that are well covered by regions of highly connected solutions can be approximately uniformly sampled using a go-with-the-winners algorithm. Our method is founded on experiments to validate the uniformity of samples gathered in this way, which must be done before the search graph models can be constructed.; We illustrate the method using the minimum bisection problem on instances drawn from random graphs with “planted” bisections and geometric graphs. For these problems, the behaviors of novel and standard algorithms are successfully predicted.; We also present a proof that a simple hill-climbing heuristic succeeds in finding optimal solutions for many distributions from the planted bisection model. The proof complements our empirical studies, providing a more complete description of this class of problems. The planted bisection instances are among the few for any NP-hard optimization problem for which local search algorithms have been successfully analyzed. The algorithm analyzed here is a degenerate case of previously studied local search methods on this problem, and therefore our work extends these results.