Divide and concur: A general approach to constraint satisfaction

Many difficult computational problems involve the simultaneous satisfaction of multiple constraints that are individually easy to satisfy. These constraints might be derived from measurements (as in tomography or diffractive imaging), interparticle interactions (as in spin glasses), or a combination of sources (as in protein folding). 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.

Figure 1

(Color online) Median number of variable updates needed to find a solution for WALKSAT (WS) and divide and concur $\left(D\text{−}C\right)$ on the same set of random 3SAT instances with $\alpha =4.2$. Each median was calculated by solving the same instance 10 times starting from different random initial guesses, for parameter values $\beta =0.9$ $\left(D\text{−}C\right)$ and $p=0.57$ (WALKSAT). Variations resulting from changing $\beta$ and $p$ are indicated by the shaded areas; both methods exhibit parameter sensitivity for problems with more than ${10}^4$ variables. A point at the top edge indicates that the median exceeded the cutoff on the number of updates, $3\times {10}^{10}$.

Figure 2

(Color online) An example of an improved packing for 169 disks in a square found by the $D\text{−}C$ algorithm. The figure at the top (a) shows the previously best-known packing [16], with density 0.8393. The density of the improved packing shown at the bottom (b) is 0.8399. Contacts are shown with dotted lines; colors indicate the number of contacts.