General optimization problems are intractable; they are also vital for many areas of computer science ranging from VLSI CAD to artificial intelligence to computational biology.  This has led to the use of many heuristics for optimization which have no worst-case guarantees on performance, but sometimes do well for ``typical'' problems.   Understanding when and to what extent heuristic methods succeed and fail is a challenge for both theory and practice.  We present an approach to provide some such understanding for a large class of heuristics based on exploring search graphs. Many such heuristic strategies have been proposed and observed to have success on many problems (e.g. Metropolis, Simulated Annealing, WalkSAT Genetic algorithms, Go-With-the-Winners ). These algorithms present various intuitively appealing mechanisms to mix greedy behavior with randomness to explore the search graph while biasing the search towards areas with better solutions. However, there is currently little understanding of why these various heuristic methods succeed or fail for various problem domains, either theoretical or empirical. Because of this limited understanding, implementations of these algorithms for hard combinatorial optimization problems is just trail-and-error, and performance predictability and confidence is low.

Our method combines mathematical rigor and experiments to answer questions such as:  What features of the search graph cause heuristic methods to succeed or fail? Are some methods more powerful than others, or does the preferred method depend on the problem? How can we set the parameters of a heuristic for best performance?

While this is a long-term project, we have had some initial success on several fronts. A common link is a "go-with-the-winners" algorithm devised by Dimitriou and Impagliazzo based on an idea of Aldous and Vazirani's.  This algorithm is a conservative, genetic algorithm-like heuristic, that maintains a collection of solutions uniformly distributed among those that meet a given quality criterion.  Dimitriou and Impagliazzo gave a combinatorial criterion of search graphs called "local expansion" that is sufficient for the heuristic method to succeed. Carson and Impagliazzo showed how to use this algorithm as a sampler to do experimental, statistical studies of the structure of search graphs. This work led to a clearer picture of how and why various heuristics succeed and fail on some instances of the graph bisection problem.

A related theoretical challenge is to find examples of instances that distinguish between various heuristics, where one method provably performs better than others.  Carson and Impagliazzo prove that the leading candidate for such problems, a certain distribution of graph bisections, does not distinguish, because almost all heuristic methods solve the problem.  However, their experimental work points to a related distribution where there does seem to be  a distinction:  simulated annealing is better than Metropolis, which in turn is better than hill-climbing.

Much work remains.  We want to find provable distinctions between methods.  We want a theoretical understanding of when widely used heuristics like simulated annealing succeed. We want to experimentally classify the structure of search graphs from "typical" instances that arise from applications, and see if we can identify common features. Finally, we want to apply our new understanding to improve performance of optimization heuristics for ``real-world'' problem instances.