Focused local search for random 3-satisfiability

Reference:

Sakari Seitz, Mikko Alava, and Pekka Orponen. Focused local search for random 3-satisfiability. Journal of Statistical Mechanics: Theory and Experiment, P06006:1–27, June 2005.

Abstract:

A local search algorithm solving an NP-complete optimisation problem can be viewed as a stochastic process moving in an 'energy landscape' towards eventually finding an optimal solution. For the random 3-satisfiability problem, the heuristic of em focusing the local moves on the presently unsatisfied clauses is known to be very effective: the time to solution has been observed to grow only linearly in the number of variables, for a given clauses-to-variables ratio sufficiently far below the critical satisfiability threshold . We present numerical results on the behaviour of three focused local search algorithms for this problem, considering in particular the characteristics of a focused variant of simple Metropolis dynamics. We estimate the optimal value for the ``temperature'' parameter for this algorithm, such that its linear-time regime extends as close to as possible. Similar parameter optimisation is performed also for the well-known WalkSAT algorithm and for the less studied, but very well performing Focused Record-to-Record Travel method. We observe that with an appropriate choice of parameters, the linear time regime for each of these algorithms seems to extend well into ratios — much further than has so far been generally assumed. We discuss the statistics of solution times for the algorithms, relate their performance to the process of ``whitening'', and present some conjectures on the shape of their computational phase diagrams.

Keywords:

satisfiability, local search, phase transition, WalkSAT, Metropolis algorithm, Record to Record Travel

Suggested BibTeX entry:

@article{SeAO05b,
    author = {Sakari Seitz and Mikko Alava and Pekka Orponen},
    journal = {Journal of Statistical Mechanics: Theory and Experiment},
    month = {June},
    pages = {1--27},
    title = {Focused local search for random 3-satisfiability},
    volume = {P06006},
    year = {2005},
}