Abstract
This paper introduces CMP (Computational Method for Partitioning), a novel algorithm designed to split an unsatisfiable Boolean formula into a Maximal Satisfiable Subset (MSS) and its complement, the Minimal Correction Subset (CoMSS). By leveraging internal SAT solver features like unsatisfiable cores and backbone literals, CMP significantly outperforms existing state-of-the-art techniques in both speed and robustness across large-scale industrial benchmarks.
Introduction
In many AI applications—ranging from medical diagnosis and belief revision to software debugging—we often encounter "over-constrained" problems where no solution satisfies every constraint. In Boolean logic, this means we have an unsatisfiable formula. To handle this, researchers look for two key structures:
- MSS (Maximal Satisfiable Subset): The largest possible subset of the formula that is still consistent.
- CoMSS (Minimal Correction Subset): The smallest set of clauses you must remove to make the rest of the formula satisfiable.
Finding these is computationally expensive, specifically residing in the $\Delta_2^P$ complexity class. While several algorithms exist, they often struggle with large-scale industrial instances. The authors of this paper aim to bridge the gap between theoretical complexity and practical performance with a more "experimentally efficient" approach.
The CMP Algorithm
The authors propose the CMP algorithm, which moves away from simple linear searches. Its core strategy revolves around identifying transition clauses—clauses that, when removed, turn an unsatisfiable set into a satisfiable one.
As illustrated in the partitioning scheme above, the algorithm maintains a dynamic view of the formula $\Sigma$, divided into a satisfiable part $\Pi$, a set of transition clauses $\Omega$, and a remaining set $\Psi$. Key technical innovations included in CMP are:
- Progress-Saving Initialization: It uses the "progress-saving" state of a CDCL SAT solver to quickly find an initial high-quality approximation of an MSS.
exploitCoreFunction: When the SAT solver finds that a subset is unsatisfiable, it returns a "core" (a smaller unsatisfiable subset). CMP uses this core to prune the search space and identify multiple clauses for the MSS or CoMSS simultaneously.- Opposite Enforcement (oe): A novel technique that uses "backbone literals" (the negation of literals in a clause) to speed up the SAT solver's search for transition clauses.
extendSatPart: It checks logically weaker versions of the formula (using disjunctions of clauses) to quickly move groups of clauses into the MSS.
Experimental Evaluation
The authors evaluated CMP against a massive benchmark suite consisting of 1,343 SAT/MAX-SAT instances and 295 MUS (Minimal Unsatisfiable Subset) instances. These datasets represent a wide variety of real-world and synthetic logic problems, providing a rigorous test for the algorithm's robustness—its ability to solve many different types of problems within a strict time limit.
Key Results and Insights
The experimental results show that CMP is the new state-of-the-art for this problem. On the SAT/MAX-SAT suite, the full version of CMP solved 1,327 out of 1,343 instances, outperforming the previous best algorithm, CLD (1,307), and the basic linear search, BLS (1,287).
As shown in the performance plot, each optional feature (exploitCore, oe, etc.) provided a cumulative boost in performance. The exploitCore feature provided the most significant gain, demonstrating that leveraging solver metadata is more efficient than treating the solver as a black box. In many cases, CMP's performance was nearly identical to the "Virtual Best Solver" (a theoretical best-case scenario).
Conclusion and Future Work
CMP demonstrates that searching for transition clauses is a more efficient way to partition a formula than traditional iterative SAT calls. While CMP is fast in practice, its worst-case complexity involves $O(n^2)$ calls to a SAT solver, whereas a basic linear search only requires $O(n)$.
Future research directions include extending the method to Weighted MAX-SAT, where constraints have varying importance, and developing methods for enumeration—finding all possible (MSS, CoMSS) partitions rather than just one.
Summary updated