Decimation flows in constraint satisfaction problems
arXiv:0908.1599 · doi:10.1088/1742-5468/2009/12/P12009
Abstract
We study hard constraint satisfaction problems with a decimation approach based on message passing algorithms. Decimation induces a renormalization flow in the space of problems, and we exploit the fact that this flow transforms some of the constraints into linear constraints over GF(2). In particular, when the flow hits the subspace of linear problems, one can stop decimation and use Gaussian elimination. We introduce a new decimation algorithm which uses this linear structure and shows a strongly improved performance with respect to the usual decimation methods on some of the hardest locked occupation problems.
arXiv comment14 pages, 2 figures
References in corpus (13)
- Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
- The random K-satisfiability problem: from an analytic solution to an efficient algorithm
- Polynomial iterative algorithms for coloring and analyzing random graphs
- Focused Local Search for Random 3-Satisfiability
- How to Compute Loop Corrections to Bethe Approximation
- 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
- Survey-propagation decimation through distributed local computations
- Locked constraint satisfaction problems
- Constraint satisfaction problems with isolated solutions are hard
- The Phase Diagram of 1-in-3 Satisfiability Problem
- Renormalization for Discrete Optimization
- On Cavity Approximations for Graphical Models