Introduction
MaxSAT is the optimization variant of the Boolean Satisfiability (SAT) problem, where the objective is to satisfy all "hard" clauses and maximize the number of satisfied "soft" clauses. Modern solvers typically employ core-guided algorithms, which iteratively identify unsatisfiable cores—subsets of clauses that cannot be simultaneously satisfied—and relax them. However, existing relaxation strategies often face a trade-off between logical strength and computational efficiency.
The Core-Guided Trade-off
Two primary strategies have dominated the field:
- OLL-style algorithms utilize powerful cardinality constraints (e.g., "at most $n$ clauses can be false"). While logically robust, they often trigger an exponential number of refutations, leading to significant slowdowns on complex industrial instances.
- PMRES-style algorithms use simpler, bounded clauses. These are more stable but introduce numerous variables and may require many iterations to reach an optimal solution.
Algorithm K: Bounded Cardinality Constraints
To bridge this gap, the authors propose Algorithm K, a core-guided approach that introduces a parameter $k$ to limit the size of cardinality constraints. If a detected core exceeds size $k$, it is partitioned into smaller components, each handled by its own constraint. These constraints are then linked hierarchically.
This parameterization allows Algorithm K to span the spectrum of existing methods: at $k=1$, it behaves similarly to PMRES, while at large $k$, it approaches the behavior of OLL. The authors implemented this in the MAXINO solver, built upon the GLUCOSE SAT engine.
Experimental Evaluation
The solver was evaluated against the 2014 MaxSAT Evaluation industrial benchmarks, covering MaxSAT (MS), Partial MaxSAT (PMS), and Weighted Partial MaxSAT (WPMS) tracks.
The results demonstrate that MAXINO-$K^{48}$ (with $k=48$) is highly effective, solving a total of 894 instances—12 more than the previous state-of-the-art solver, EVA. It also significantly outperformed other prominent solvers such as MSCG, OPENWBO, and CLASP.
As shown in the scatter plots, MAXINO-$K^{48}$ maintains a competitive edge across a wide range of problem difficulties. On the WPMS track, the bounded approach proved particularly efficient, often reaching solutions in a fraction of the time required by pure OLL-based solvers.
Conclusion
By controlling the size of cardinality constraints, Algorithm K effectively manages the number of refutations during the search process. This "Goldilocks" approach provides the logical strength necessary for industrial problems without the exponential overhead of unbounded constraints. Future research may explore dynamic adjustment of the parameter $k$ during execution to further optimize performance across diverse problem domains.
Summary updated