When solving a problem requires computing time that is exponential in the problem's size, reason dictates a tradeoff: sacrifice a small degree of accuracy for a large gain in speed. For hard discrete optimization problems, this is the motivating principle behind local search heuristics, which find approximate rather than exact solutions. In many applications, local search has become the method of choice. Simulated annealing is one well-known example of local search.

But how well do such methods actually work, and how can we improve on them? A heuristic method currently under development, called Extremal Optimization, has the advantage that it is effective yet simple - simple enough that realistically we may hope to analyze its performance over a wide range of problems. Using techniques and models from sources as diverse as graph theory, computational complexity and statistical physics, we will explore the performance of Extremal Optimization and relate this to the behavior of other local search methods.

Equipped with a better understanding of local search heuristics such as Extremal Optimization, we will be able to implement improvements to the existing heuristics. There is an immediate need for these improved methods in a number of applications at Los Alamos National Laboratory. The world's fastest computer, the ASCI Q machine (30 Teraops), is about to be put into service at Los Alamos. In machines such as this one, complicated resource allocation problems must be solved in real-time. Scheduling, load balancing and similar issues must be addressed as the computation evolves, and the most efficient method is often to make local improvements to a previous "good" solution. Applications of local search heuristics to the problem of Constraint Satisfaction are also of interest at Los Alamos, for projects related to homeland security, where inductive reasoning problems play a key role. Being able to find quick solutions to satisfiability problems with minimal constraint violation could make it possible to address mathematical reasoning challenges that presently are considered too complex to solve.

Last modified: 2 June 2002