Abstract
The survey propagation (SP) algorithm has been shown to work well on large instances of the random 3-SAT problem near its phase transition. It was shown that SP estimates marginals over covers, using joker states to represent clusters of configurations. The SP-y algorithm generalizes SP to work on the Max-SAT problem, but the cover interpretation of SP does not generalize to SP-y. Recently, a relaxed survey propagation (RSP) algorithm has been proposed for inference in Markov random fields (MRF). RSP for MRFs assigns zero probability to joker states, and hence the cover interpretation is also inapplicable. We adapt RSP to solve Max-SAT problems, and show that it has an interpretation of estimating marginals over covers violating a minimum number of clauses. This naturally generalizes the cover interpretation of SP. Empirically, we show that RSP out-performs SP-y and other state-of-the-art solvers on random as well as benchmark instances of Max-SAT.
Introduction
The Boolean satisfiability problem (SAT) is a cornerstone of computer science, but real-world scenarios often involve "over-constrained" systems where no perfect solution exists. This leads to the Max-SAT problem: finding an assignment that violates the minimum number of clauses.
While Survey Propagation (SP) is legendary for solving massive, hard 3-SAT instances near the phase transition, it was originally designed for satisfiable problems. Previous extensions for Max-SAT, such as SP-$y$, lacked the elegant "cover" interpretation that made the original SP theoretically robust. This paper introduces a version of Relaxed Survey Propagation (RSP) specifically adapted for Max-SAT, re-introducing "joker states" to provide a unified framework for both satisfiable and unsatisfiable instances.
The RSP Framework and Min-Cover Interpretation
The authors adapt RSP by constructing a Markov Random Field (MRF) where variables can take three states: 0, 1, or a "joker" state (*). A joker state indicates that a variable can take either value without increasing the number of violated constraints within a cluster of configurations.
A critical component of the algorithm is the penalty parameter $y$. A violated clause incurs a cost proportional to $\exp(-y)$. As $y \to \infty$, the algorithm recovers the original SP behavior, where violations are strictly forbidden.
The theoretical breakthrough of this work is the min-cover interpretation. The authors prove that RSP estimates marginals over min-covers—clusters of assignments that violate the absolute minimum number of constraints. This gives RSP a clear physical meaning rooted in statistical mechanics, identifying regions of the search space that are "almost" satisfying.
Empirical Evaluation
The performance of RSP was evaluated on large-scale random Max-3-SAT instances ($N=10,000$) and benchmark problems from the SAT 2003 competition. The algorithm uses a decimation procedure: it iteratively identifies the most biased variables based on RSP marginals, fixes their values, and simplifies the problem until a local search solver (like WalkSAT) can find the final minimum.
As shown in the experimental results, RSP consistently outperforms SP-$y$ and standard local search suites (UBCSAT) on over-constrained problems ($\alpha \geq 4.7$). For instance, at a clause-to-variable ratio of $\alpha = 5.0$, RSP reduced violations significantly compared to SP-$y$. On benchmark instances, the gap was even more pronounced, with RSP finding solutions with 24 violations where local search found 73.
Conclusion and Future Work
RSP provides a powerful, theoretically grounded extension of Survey Propagation to the Max-SAT domain. By generalizing the cover interpretation, it offers a systematic way to navigate the landscape of unsatisfiable constraints. While the algorithm faces challenges regarding convergence at very high penalty values and sensitivity during decimation, its superior performance on hard random and benchmark instances marks a significant step forward in combinatorial optimization.
Summary updated