A MaxSAT Algorithm Using Cardinality Constraints of Bounded Size

Mario Alviano, Carmine Dodaro, Francesco RiccaIJCAI 2015

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:

  1. 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.
  2. 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.

Overall comparison of MAXINO-K48 against state-of-the-art solvers. The cactus plot shows the number of instances solved within specific execution time limits.

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.

Scatter plots comparing the execution time of MAXINO-K48 against EVA and MSCG. Points below the diagonal indicate instances where MAXINO-K48 was faster.

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

BibTeX
@inproceedings{alviano2015maxsat,
  author = {Mario Alviano and Carmine Dodaro and Francesco Ricca},
  title = {{A MaxSAT Algorithm Using Cardinality Constraints of Bounded Size}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}

Loading related content...

Figure