Circumspect descent prevails in solving random constraint satisfaction problems

Abstract

We study the performance of stochastic local search algorithms for random instances of the $K$-satisfiability ($K$-SAT) problem. We introduce a new stochastic local search algorithm, ChainSAT, which moves in the energy landscape of a problem instance by {\em never going upwards} in energy. ChainSAT is a \emph{focused} algorithm in the sense that it considers only variables occurring in unsatisfied clauses. We show by extensive numerical investigations that ChainSAT and other focused algorithms solve large $K$-SAT instances almost surely in linear time, up to high clause-to-variable ratios $\alpha$; for example, for K=4 we observe linear-time performance well beyond the recently postulated clustering and condensation transitions in the solution space. The performance of ChainSAT is a surprise given that by design the algorithm gets trapped into the first local energy minimum it encounters, yet no such minima are encountered. We also study the geometry of the solution space as accessed by stochastic local search algorithms.

6 figures, about 17 pates

References in corpus (10)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Clustering of solutions in the random satisfiability problem
• On the freezing of variables in random constraint satisfaction problems
• Focused Local Search for Random 3-Satisfiability
• Behavior of heuristics and state space structure near SAT/UNSAT transition
• 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
• Source coding by efficient selection of ground states clusters

Cited by in corpus (25)

• The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
• Decentralized Constraint Satisfaction
• Biased landscapes for random Constraint Satisfaction Problems
• From one solution of a 3-satisfiability formula to a solution cluster: Frozen variables and entropy
• The large deviations of the whitening process in random constraint satisfaction problems
• 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
• Glassy Behavior and Jamming of a Random Walk Process for Sequentially Satisfying a Constraint Satisfaction Formula
• Learning by random walks in the weight space of the Ising perceptron
• Combined local search strategy for learning in networks of binary synapses
• Maximally flexible solutions of a random $K$-satisfiability formula
• Perturbative large deviation analysis of non-equilibrium dynamics
• Biased measures for random Constraint Satisfaction Problems: larger interaction range and asymptotic expansion
• Cutting-Plane Algorithms and Solution Whitening for the Vertex-Cover Problem
• Circumventing spin glass traps by microcanonical spontaneous symmetry breaking
• Criticality and Heterogeneity in the Solution Space of Random Constraint Satisfaction Problems
• Decimation flows in constraint satisfaction problems
• Witness of unsatisfiability for a random 3-satisfiability formula
• Biased thermodynamics can explain the behaviour of smart optimization algorithms that work above the dynamical threshold
• Bose-Einstein Condensation in Satisfiability Problems
• Algorithmic thresholds in combinatorial optimization depend on the time scaling
• Approaching the ground states of the random maximum two-satisfiability problem by a greedy single-spin flipping process
• Finite-size scaling in random $K$-satisfiability problems
• A novel local search based on variable-focusing for random K-SAT