Abstract
This paper presents a novel core-guided MaxSAT solver that leverages a sound inference rule, MaxSAT Resolution (MAXRES), to replace traditional cardinality constraints. By introducing a "compressed" version of MAXRES using auxiliary variables, the authors achieve linear clause growth instead of quadratic blowup. This optimization significantly improves performance, allowing the solver to dominate the 2013 Max-SAT Evaluation industrial benchmarks.
Introduction
Maximum Satisfiability (MaxSAT) is an optimization variant of the Boolean Satisfiability (SAT) problem. Given a set of hard and soft clauses, the goal is to find an assignment that satisfies all hard clauses while maximizing the weight of satisfied soft clauses. Modern solvers typically employ a core-guided approach, iteratively identifying unsatisfiable cores—subsets of soft clauses that cannot be simultaneously satisfied—and relaxing them to allow for a solution at a specific cost.
Traditionally, relaxation involves adding cardinality constraints (e.g., "at most $k$ variables can be true"). However, these constraints often introduce significant complexity, leading to performance degradation in large-scale industrial problems.
Methodology: Core-Guided MaxSAT Resolution
The authors propose a shift from cardinality constraints to MaxSAT Resolution (MAXRES). MAXRES is an inference rule that transforms a set of clauses into a cost-equivalent set. When an unsatisfiable core is identified, MAXRES extracts the cost of unsatisfiability into an empty clause (incrementing the lower bound) and generates "compensation clauses" that enable the SAT solver to continue its search.
The high-level procedure, PMRes, is outlined in Algorithm 1. It iteratively calls a SAT solver to find cores, reifies them, and applies MaxSAT resolution to update the formula for the next iteration.
Innovation: Compressed MAXRES
A major drawback of standard MAXRES is the potential for a quadratic blowup in the number of clauses. For a core of size $n$, standard application can result in $O(n^2)$ new clauses. To address this, the authors introduced Compressed MAXRES.
By utilizing auxiliary "reification" variables to represent disjunctions of literals, the growth is reduced to $O(n)$ (linear). This linearization is critical for maintaining formula tractability across many iterations, preventing the solver from crashing due to memory limits.
As shown in the optimized PMRes process, each step uses reification and resolution to maintain a compact representation of the problem state, allowing the underlying SAT solver to maintain its efficiency.
Evaluation and Results
The approach was evaluated using industrial benchmarks from the 2013 Max-SAT Evaluation, covering domains such as bioinformatics, hardware verification, and satellite scheduling.
The authors implemented their algorithm in the EVAC solver. Key findings include:
- Superior Performance: EVAC solved 877 instances, significantly outperforming top competitors like
wpm2(761 instances) andmsunc(733 instances). - Industrial Lead: On industrial benchmarks specifically, EVAC solved 126 more instances than the next best non-MAXRES solver.
- Robustness: The compressed logic was particularly effective on benchmarks with large cores, such as the
sean-safarpourfamily, where standard MAXRES previously failed.
Conclusion
The transition to linear-growth MAXRES transformations represents a significant advancement in MaxSAT solving. By keeping transformations local and avoiding the global dependencies of cardinality constraints, the solver maintains the efficiency of underlying SAT heuristics. Future work may explore the impact of reification variables on problem symmetry and the extension of these techniques to weighted MaxSAT instances.
Summary updated