Last modified: 18 November 2005
Some of the most widely used heuristic tools for computationally hard problems have been inspired by equilibrium statistical mechanics. These methods -- simulated annealing is an example -- have been particularly successful because of their generality: given a new optimization problem about which one knows virtually nothing, one can often apply such heuristics with minimal effort, obtaining good near-optimal solutions. Equilibrium approaches, however, typically fail as one approaches criticality (another loan-word from statistical physics). The critical point is the transitional point that separates instances into distinct regimes of parameter space; computer scientists have observed that the instances of highest complexity in a hard problem lie close to this point.
Curiously, we have found that heuristic algorithms inspired by non-equilibrium physical processes do not seem to experience difficulties at criticality. A general-purpose method that we have been developing, called extremal optimization, shows no signs of diminished performance near the critical point, when tested on graph partitioning problems. We are currently analyzing such approaches. The development of non-equilibrium optimization methods is likely, we believe, to lead to the next generation of general-purpose algorithms -- intended, like simulated annealing, for broad application. We expect that this analysis will lead us to new insights into the role criticality plays in combinatorial optimization, as well as to a deeper (and more applied) understanding of computational complexity.
Last modified: 18 November 2005