Theory of Nonequilibrium Local Search on Random Satisfaction Problems

by Erik Aurell (KTH)

Friday 10 Jan 2020, 14:00 → 15:00 Europe/Stockholm

112:028 (Nordita South)

The simulated annealing method to solve combinatorial optimization problems relies on the Monte Carlo method to simulate Gibbs distributions representing the cost function of the problem. As temperature is lowered distributions concentrate on states at low energy, which eventually tend to the solution(s). From a physical point of view this approach is based on the principle of detailed balance.

Empirically it has been known for a long time that other methods which break detailed balance can find solutions to combinatorial optimization problems in ways that can be faster, or that work in wider parameter ranges, or with better accuracy; in short better.

The performance of those methods is however not trivial to analyse as they amount to non-equilibrium dynamics of very high-dimensional systems with complex interactions.

I will present one approach to such an analysis applied to a local search heuristic which finds solutions to a well-studied benchmark, the random 3-satisfiability problem. I will also discuss the pros and cons of this method, and possible extensions. 

The talk is based on joint work with Eduardo Domínguez, David Machado and Roberto Mulet, published in PRL vol 123:230602 (2019)