Solving Constraint Satisfaction Problems through Belief Propagation-guided decimation

Abstract

Message passing algorithms have proved surprisingly successful in solving hard constraint satisfaction problems on sparse random graphs. In such applications, variables are fixed sequentially to satisfy the constraints. Message passing is run after each step. Its outcome provides an heuristic to make choices at next step. This approach has been referred to as `decimation,' with reference to analogous procedures in statistical physics. The behavior of decimation procedures is poorly understood. Here we consider a simple randomized decimation algorithm based on belief propagation (BP), and analyze its behavior on random k-satisfiability formulae. In particular, we propose a tree model for its analysis and we conjecture that it provides asymptotically exact predictions in the limit of large instances. This conjecture is confirmed by numerical simulations.

10 pages, 4 figures. A longer version can be found as arXiv:0904.3395 [cond-mat.dis-nn]

References in corpus (4)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• On the freezing of variables in random constraint satisfaction problems
• Can rare SAT formulas be easily recognized? On the efficiency of message passing algorithms for K-SAT at large clause-to-variable ratios
• Counting good truth assignments of random k-SAT formulae

Cited by in corpus (16)

• Perturbation Biology: inferring signaling networks in cellular systems
• A better algorithm for random k-SAT
• Biased landscapes for random Constraint Satisfaction Problems
• Glassy Critical Points and Random Field Ising Model
• 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
• The random 2-SAT partition function
• On belief propagation guided decimation for random k-SAT
• Polar Codes are Optimal for Lossy Source Coding
• Erasure Decoding for Quantum LDPC Codes via Belief Propagation with Guided Decimation
• PDP: A General Neural Framework for Learning Constraint Satisfaction Solvers
• The network source location problem: ground state energy, entropy and effects of freezing
• Typical case behaviour of spin systems in random graph and composite ensembles
• Aspects of Statistical Physics in Computational Complexity
• Perturbed Message Passing for Constraint Satisfaction Problems
• Improving variational methods via pairwise linear response identities