TL;DR
This paper introduces Relaxed Survey Propagation (RSP), a novel algorithm for solving the weighted Maximum Satisfiability (Max-SAT) problem. RSP extends the successful Survey Propagation (SP) algorithm by providing a principled way to handle weighted clauses, offering a more general framework that can interpret SP and SP-y as special cases. Empirically, RSP demonstrates superior performance compared to existing state-of-the-art solvers on both random and benchmark Max-SAT instances.
What Problem Does This Paper Address?
The paper tackles the challenge of solving the Weighted Maximum Satisfiability (Max-SAT) problem, an optimization variant of the Boolean Satisfiability (SAT) problem. In Max-SAT, the goal is to find an assignment of truth values to variables that satisfies the maximum number of clauses, or in the weighted version, maximizes the total weight of satisfied clauses. While the Survey Propagation (SP) algorithm has shown remarkable success on the SAT problem, particularly near its phase transition, and SP-y extends it to Max-SAT, the underlying "cover interpretation" of SP doesn't directly generalize to SP-y. This gap leaves a need for a unified framework that can explain and potentially improve upon these methods for weighted Max-SAT. The authors aim to bridge this gap by developing RSP, which not only addresses weighted Max-SAT but also provides a clearer theoretical understanding of SP and SP-y.
Methods
The core contribution is the Relaxed Survey Propagation (RSP) algorithm. RSP is formulated as a loopy Belief Propagation (BP) algorithm applied to an extended factor graph. This extended graph is designed to represent weighted Max-SAT instances in a way that naturally incorporates the concept of "covers" (assignments that satisfy clauses with minimal total weight).
Key aspects of the method include:
- Extended Factor Graph: A novel factor graph is constructed where variables represent not just truth assignments but also information about which clauses constrain them. This allows for a richer representation of the problem.
- "Don't Care" State: The introduction of a "don't care" state for variables in the extended factor graph is crucial for handling violated clauses gracefully.
- Message Passing Updates: RSP employs message passing updates derived from BP, but adapted for the extended factor graph and the specific semantics of weighted Max-SAT. These updates incorporate penalties for violated clauses.
- Cover Interpretation: The paper establishes that RSP, particularly in its limit, estimates marginals over "min-covers," which are configurations that violate clauses with the minimum possible total weight. This provides a theoretical grounding for its effectiveness.
- Decimation Algorithm: Similar to SP-y, RSP uses a decimation-based approach for solving instances. This involves iteratively fixing variables based on their "bias" (difference in probabilities of taking +1 vs. -1) and simplifying the problem.
Datasets
The paper evaluates RSP on:
- Random Max-3-SAT instances: Generated with varying clause-to-variable ratios (α) in the unsatisfiable region (beyond the phase transition).
- Random Weighted Max-3-SAT instances: Similar to random Max-3-SAT but with clause weights sampled from a uniform distribution.
- Benchmark Max-SAT instances: Specifically, seven large instances from the SAT 2003 competition, used in prior work.
No new benchmarks were introduced.
Key Insights and Ideas
- Unified Framework: RSP provides a principled way to unify SP, SP-y, and BP under a single framework by leveraging an extended factor graph and a "don't care" state. This offers a deeper theoretical understanding of these algorithms.
- Cover Interpretation for Max-SAT: The paper successfully extends the "cover interpretation" of SP to weighted Max-SAT, showing that RSP estimates marginals over configurations that minimize the total weight of violated clauses. This is a significant theoretical advancement.
- Importance of Parameter 'y': The parameter 'y' in RSP plays a crucial role in balancing the penalty for violated clauses. The paper demonstrates that a sufficiently large 'y' is beneficial for performance, aligning with theoretical predictions that RSP should converge to min-covers.
- RSP's Robustness: RSP shows more consistent behavior than SP-y across varying 'y' values, suggesting it's more amenable to systematic parameter tuning.
- Decimation without Backtracking: RSP achieves strong performance without the need for the backtracking mechanism used in SP-y, simplifying its implementation and potentially improving efficiency.
Key Results
- Outperforms SP-y and Local Search: RSP consistently outperforms SP-y and state-of-the-art local search solvers (UBCSAT) on random Max-SAT instances, especially in the unsatisfiable region (α > 4.267).
- Competitive on Weighted Max-SAT: RSP also outperforms UBCSAT on random weighted Max-SAT instances.
- Effective on Benchmark Instances: RSP achieves good results on benchmark Max-SAT instances, often outperforming UBCSAT, though the success on these instances is attributed more to convergence than to exploiting clustering phenomena.
- Parameter 'y' Tuning: The experimental results show that as 'y' increases, RSP's performance generally improves until it fails to converge, indicating a systematic way to find good 'y' values.
Limitations and Future Work
- Convergence: While RSP often converges, there's no absolute guarantee for all instances, especially with very large 'y' values. Failure to converge leads to relying on WalkSAT.
- Parameter Tuning: While 'y' is important, finding the optimal 'y' can still require experimentation. The paper suggests that for RSP, a sufficiently large 'y' is generally good, and the decimation process can help find it.
- Theoretical Explanation for Benchmark Instances: The success of RSP on benchmark instances appears to be more about its convergence properties than its ability to exploit clustering, which is a key theoretical insight for random instances. Further investigation into why RSP converges on these specific instances could be valuable.
- Future Work: The paper suggests that the RSP-p algorithm, a generalization of RSP, could be explored further. The appendix also hints at alternative definitions for single-variable potentials that could be investigated.
Summary updated