Focused Local Search for Random 3-Satisfiability

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 focusing the local moves on the presently unsatisfiedclauses 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 $\alpha$ sufficiently far below the critical satisfiability threshold ${\alpha }_c\approx 4.27$. 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 the simple Metropolis dynamics. We estimate the optimal value for the ``temperature'' parameter $\eta$ for this algorithm, such that its linear-time regime extends as close to ${\alpha }_c$ 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 $\alpha >4.2$ -- 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.

20 pages, lots of figures

References in corpus (10)

• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• Survey propagation: an algorithm for satisfiability
• Survey Propagation as local equilibrium equations
• Instability of one-step replica-symmetry-broken phase in satisfiability problems
• Relaxation and Metastability in the RandomWalkSAT search procedure
• Solving satisfiability problems by fluctuations: The dynamics of stochastic local search algorithms
• On local equilibrium equations for clustering states
• Comparing Beliefs, Surveys and Random Walks
• Alternative solutions to diluted p-spin models and XORSAT problems
• Approximate analysis of search algorithms with "physical" methods

Cited by in corpus (26)

• Phase Transitions in the Coloring of Random Graphs
• Optimization hardness as transient chaos in an analog approach to constraint satisfaction
• Clusters of solutions and replica symmetry breaking in random k-satisfiability
• Generalization of the cavity method for adiabatic evolution of Gibbs states
• Inducing Effect on the Percolation Transition in Complex Networks
• Circumspect descent prevails in solving random constraint satisfaction problems
• On the cavity method for decimated random constraint satisfaction problems and the analysis of belief propagation guided decimation algorithms
• Behavior of heuristics and state space structure near SAT/UNSAT transition
• The backtracking survey propagation algorithm for solving random K-SAT problems
• The Phase Diagram of 1-in-3 Satisfiability Problem
• Quiet Planting in the Locked Constraint Satisfaction Problems
• From one solution of a 3-satisfiability formula to a solution cluster: Frozen variables and entropy
• Communities of solutions in single solution clusters of a random K-Satisfiability formula
• Numerical Solution-Space Analysis of Satisfiability Problems
• A theory of non-equilibrium local search on random satisfaction problems
• Learning by random walks in the weight space of the Ising perceptron
• Statistical mechanics of combinatorial auctions
• Clustering of solutions in hard satisfiability problems
• Large deviation function and fluctuation theorem for classical particle transport
• Cutting-Plane Algorithms and Solution Whitening for the Vertex-Cover Problem
• Decimation flows in constraint satisfaction problems
• A high-performance analog Max-SAT solver and its application to Ramsey numbers
• Biased thermodynamics can explain the behaviour of smart optimization algorithms that work above the dynamical threshold
• Mismatching as a tool to enhance algorithmic performances of Monte Carlo methods for the planted clique model
• Finite-size scaling in random $K$-satisfiability problems
• Algorithmic thresholds in combinatorial optimization depend on the time scaling