Behavior of heuristics and state space structure near SAT/UNSAT transition

Abstract

We study the behavior of ASAT, a heuristic for solving satisfiability problems by stochastic local search near the SAT/UNSAT transition. The heuristic is focused, i.e. only variables in unsatisfied clauses are updated in each step, and is significantly simpler, while similar to, walksat or Focused Metropolis Search. We show that ASAT solves instances as large as one million variables in linear time, on average, up to 4.21 clauses per variable for random 3SAT. For K higher than 3, ASAT appears to solve instances at the ``FRSB threshold'' in linear time, up to K=7.

12 pages, 6 figures, longer version available as MSc thesis of first author at http://biophys.physics.kth.se/docs/ardelius_thesis.pdf

References in corpus (2)

• Clustering of solutions in the random satisfiability problem
• Comparing Beliefs, Surveys and Random Walks

Cited by in corpus (29)

• Phase Transitions in the Coloring of Random Graphs
• A Landscape Analysis of Constraint Satisfaction Problems
• The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
• Generalization of the cavity method for adiabatic evolution of Gibbs states
• Circumspect descent prevails in solving random constraint satisfaction problems
• Locked constraint satisfaction problems
• Following Gibbs States Adiabatically - The Energy Landscape of Mean Field Glassy Systems
• The backtracking survey propagation algorithm for solving random K-SAT problems
• The Phase Diagram of 1-in-3 Satisfiability Problem
• Exhaustive enumeration unveils clustering and freezing in random 3-SAT
• Message Passing for Optimization and Control of Power Grid: Model of Distribution System with Redundancy
• Biased landscapes for random Constraint Satisfaction Problems
• The large deviations of the whitening process in random constraint satisfaction problems
• Numerical Solution-Space Analysis of Satisfiability Problems
• Monte Carlo algorithms are very effective in finding the largest independent set in sparse random graphs
• Phase transition for cutting-plane approach to vertex-cover problem
• Phase Transitions and Computational Difficulty in Random Constraint Satisfaction 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
• Solution to Satisfiability problem by a complete Grover search with trapped ions
• Clustering of solutions in hard satisfiability problems
• Biased measures for random Constraint Satisfaction Problems: larger interaction range and asymptotic expansion
• Barriers and local minima in energy landscapes of stochastic local search
• Geometric properties of graph layouts optimized for greedy navigation
• Cutting-Plane Algorithms and Solution Whitening for the Vertex-Cover Problem
• Biased thermodynamics can explain the behaviour of smart optimization algorithms that work above the dynamical threshold
• Finite-size scaling in random $K$-satisfiability problems
• Mismatching as a tool to enhance algorithmic performances of Monte Carlo methods for the planted clique model