Divide and concur: A general approach to constraint satisfaction
arXiv:0801.0222 · doi:10.1103/PhysRevE.78.036706
Abstract
Many difficult computational problems involve the simultaneous satisfaction of multiple constraints which are individually easy to satisfy. Such problems occur in diffractive imaging, protein folding, constrained optimization (e.g., spin glasses), and satisfiability testing. We present a simple geometric framework to express and solve such problems and apply it to two benchmarks. In the first application (3SAT, a boolean satisfaction problem), the resulting method exhibits similar performance scaling as a leading context-specific algorithm (walksat). In the second application (sphere packing), the method allowed us to find improved solutions to some old and well-studied optimization problems. Based upon its simplicity and observed efficiency, we argue that this framework provides a competitive alternative to stochastic methods such as simulated annealing.
4 pages, 2 figures
References in corpus (1)
Cited by in corpus (29)
- Dense Regular Packings of Irregular Non-Convex Particles
- Recent Results on Douglas-Rachford Methods for Combinatorial Optimization Problems
- Reformulation of the Covering and Quantizer Problems as Ground States of Interacting Particles
- Dense periodic packings of tetrahedra with small repeating units
- A Cyclic Douglas-Rachford Iteration Scheme
- A Parallel Douglas Rachford Algorithm for Minimizing ROF-like Functionals on Images with Values in Symmetric Hadamard Manifolds
- An Improved Three-Weight Message-Passing Algorithm
- Global Behavior of the Douglas-Rachford Method for a Nonconvex Feasibility Problem
- Three dimensional structure from intensity correlations
- Deep learning for neuroimaging: a validation study
- Reflection methods for inverse problems with application to protein conformation determination
- Parity Quantum Optimization: Encoding Constraints
- A method for dense packing discovery
- A new solution to the curved Ewald sphere problem for 3D image reconstruction in electron microscopy
- A feasibility approach for constructing combinatorial designs of circulant type
- The Douglas--Rachford algorithm for a hyperplane and a doubleton
- Reference-enhanced X-ray Single Particle Imaging
- A Lyapunov function construction for a non-convex Douglas-Rachford iteration
- Disentangling the Seesaw in the Left-Right Model -- An Algorithm for the General Case
- Automating Crystal-Structure Phase Mapping: Combining Deep Learning with Constraint Reasoning
- A Douglas-Rachford construction of non-separable continuous compactly supported multidimensional wavelets
- Mapping constrained optimization problems to quantum annealing with application to fault diagnosis
- Reconstructing cellular automata rules from observations at nonconsecutive times
- Solving a directed percolation inverse problem
- Matrix product constraints by projection methods
- Learning grammar with a divide-and-concur neural network
- Lowering the error floor of Gallager codes: a statistical-mechanical view
- Norm Convergence of Realistic Projection and Reflection Methods
- Divide & Concur and Difference-Map BP Decoders for LDPC Codes