TL;DR
This paper introduces MS-Builder, a novel tool that generates verifiable "certificates" for Max-SAT problems. These certificates, in the form of equivalence-preserving transformations, bridge the gap between standard SAT refutations and Max-SAT proofs, offering a more robust way to validate Max-SAT solver results.
What Problem Does This Paper Address?
The Maximum Satisfiability (Max-SAT) problem is a crucial extension of the Satisfiability (SAT) problem, aiming to find an assignment that satisfies the maximum possible number of clauses in a given Boolean formula. While SAT solvers can produce refutations (proofs of unsatisfiability), adapting these refutations to the Max-SAT context has been a long-standing challenge. Specifically, directly translating a SAT refutation into a Max-SAT refutation often leads to a significant, potentially exponential, increase in proof size, making it impractical. This paper addresses this gap by developing methods to efficiently transform SAT refutations into Max-SAT refutations, thereby enabling the creation of verifiable certificates for Max-SAT solutions.
Methods
The core of this work lies in developing techniques to adapt standard SAT resolution refutations into Max-SAT refutations. The authors introduce a modified Max-SAT resolution rule that includes a "split rule," allowing for the generation of two clauses from one, which helps in preserving Max-SAT equivalence.
Key methodological contributions include:
- Adapting Resolution Refutations: The paper presents theoretical results showing that SAT refutations can be transformed into Max-SAT refutations with a linear increase in size for specific types of refutations (read-once, semi-read-once, tree-like regular, tree-like, and semi-tree-like). For general, unrestricted refutations, an exponential blow-up is possible but a method is provided.
- MS-Builder Tool: This is a practical implementation that iteratively calls a SAT oracle to obtain resolution refutations. These refutations are then adapted for Max-SAT using the developed techniques. The process continues until the formula becomes satisfiable, at which point the accumulated transformations form a certificate.
- MS-Checker Tool: A companion tool designed to verify the validity of the certificates generated by MS-Builder, ensuring their correctness.
Datasets
The paper evaluates MS-Builder on the complete track benchmarks from the 2020 Max-SAT Evaluation. These benchmarks consist of both unweighted and weighted (partial) Max-SAT instances.
Key Insights and Ideas
- Bridging the SAT-MaxSAT Divide: The most significant insight is that the gap between SAT and Max-SAT refutations is not insurmountable. By carefully adapting resolution rules, it's possible to create efficient Max-SAT proofs, which is crucial for building trust in Max-SAT solvers.
- The Power of the Split Rule: The introduction of the split rule in Max-SAT resolution is a key enabler for transforming SAT refutations. It provides a mechanism to handle clauses that might be problematic in a direct translation.
- Practical Implications of Proof Size: The paper highlights that while general transformations are possible, the size of the resulting Max-SAT refutation is a critical factor. Achieving linear-sized transformations for many common refutation types makes the certificate generation practical.
- Empirical Differences: The study reveals interesting empirical differences between unweighted and weighted Max-SAT instances. Weighted instances tend to yield a lower percentage of "easy" refutation types (read-once and semi-read-once), suggesting they are inherently harder to prove.
Key Results
- Theoretical Guarantees: The paper provides theoretical guarantees for transforming various types of SAT refutations into Max-SAT refutations. For semi-read-once, tree-like regular, tree-like, and semi-tree-like refutations, the Max-SAT refutation size is linear with respect to the original SAT refutation size. For unrestricted refutations, a linear transformation is possible but with a potential exponential blow-up in size.
- MS-Builder Performance: MS-Builder successfully generated full proofs for a significant number of instances from the 2020 Max-SAT Evaluation benchmarks. Specifically, it succeeded on 163 out of 576 unweighted instances and 144 out of 600 weighted instances within a 1-hour time limit and 16GB memory constraint.
- Partial Proofs: For many other instances, MS-Builder was able to generate proofs that covered at least half of the optimum cost, demonstrating its utility even when full proofs are not achievable within the given constraints.
- Refutation Type Distribution: The experiments showed that read-once and semi-read-once refutations were prevalent (83.7%) in unweighted instances, whereas weighted instances showed a more diverse distribution, with only 35.60% being of these types.
Limitations and Future Work
- Unrestricted Refutations: While the paper provides a method to adapt unrestricted SAT refutations to Max-SAT, the potential for exponential blow-up in proof size remains a limitation. Future work could explore more efficient ways to handle these cases.
- Scalability for Complex Instances: Although MS-Builder performed well on many instances, the time and memory constraints of the evaluation might have limited its success on the most challenging problems. Further optimization of the MS-Builder and MS-Checker tools could improve scalability.
- Exploration of Other Proof Systems: The paper focuses on resolution-based refutations. Future research could investigate adapting other SAT proof systems to Max-SAT or explore entirely new Max-SAT proof systems.
- Broader Benchmark Evaluation: While the 2020 Max-SAT Evaluation benchmarks are standard, evaluating MS-Builder on a wider range of real-world Max-SAT problems could provide further insights into its practical applicability.
Summary updated