Exploiting the Structure of Unsatisfiable Cores in MaxSAT

Carlos Ansótegui, Frédéric Didier, Joel GabàsIJCAI 2015

Introduction

Maximum Satisfiability (MaxSAT) is a fundamental optimization problem in computer science, extending the Boolean Satisfiability (SAT) problem to find assignments that satisfy the maximum number of constraints. While critical for industrial applications such as hardware verification, bioinformatics, and scheduling, large-scale MaxSAT instances remain computationally challenging. Modern SAT-based MaxSAT solvers typically employ either core-guided strategies (finding unsatisfiable subsets to raise lower bounds) or model-guided strategies (finding satisfying assignments to lower upper bounds). The WPM3 algorithm addresses the challenge of efficiently integrating these two paradigms by exploiting the hierarchical structure of unsatisfiable cores.

Methodology: The WPM3 Algorithm

WPM3 is a complete MaxSAT algorithm designed to be "globally aware" of the problem's core structure. It introduces several key innovations to bridge the gap between core-guided and model-guided approaches:

  1. Structured Cardinality Encodings: Traditional solvers often treat cardinality constraints as independent blocks. WPM3 builds a tree structure using "totalizer" encodings that mirror the lineage of merged unsatisfiable cores. By keeping related variables close together in the encoding, the solver significantly boosts the underlying SAT solver's ability to propagate information.
  2. MaxSAT Phase Saving: While standard phase saving remembers the last polarity of a variable, WPM3 stores polarities from the best global assignment found so far. This "warm starts" the SAT solver during lower-bound refinement, biasing the search toward promising regions of the optimization landscape.
  3. Hybrid Search: WPM3 utilizes a core-guided backbone but periodically calls an optimize function—a model-guided step—to refine upper bounds on sub-problems. This allows the solver to produce high-quality solutions quickly, even before optimality is proven.
Ablation study showing the impact of different WPM3 components (t: totalizer, k: keep cores, o: optimize, p: phase saving) on solving performance across MS, PMS, and WPMS categories.

Experimental Evaluation

The performance of WPM3 was evaluated using 1,033 industrial instances from the MaxSAT Evaluation 2014 (MSE14). This benchmark suite is divided into three categories: MaxSAT (MS), Partial MaxSAT (PMS), and Weighted Partial MaxSAT (WPMS). The evaluation included 32 different problem families, providing a comprehensive test of solver robustness.

Key Results

The wpm3_tkop variant demonstrated a clear lead over the winners of the 2014 MaxSAT Evaluation. As shown in the results table, WPM3 solved 909 out of 1,033 instances, significantly outperforming other top-tier solvers like eva500a (885 solved) and open-wbo (849 solved).

Comparison of WPM3 with state-of-the-art solvers on MSE14 industrial instances, highlighting its dominance in total solved instances.

Beyond total counts, WPM3 proved highly robust, achieving the highest solve ratio in 30 out of 32 problem families. In the incomplete track, where solvers are given a tight 300-second timeout to find the best possible upper bound, WPM3 consistently outperformed dedicated incomplete solvers like optimax. Component analysis revealed that the addition of MaxSAT-specific phase saving alone allowed the solver to crack 7 additional "hard" instances that were previously unsolvable within the time limit.

Conclusion

WPM3 represents a significant advancement in MaxSAT solving by exploiting the inherent structure of unsatisfiable cores. The integration of tree-based cardinality encodings and optimization-aware phase saving provides a robust framework for industrial-scale optimization. Future work will explore the integration of incremental cardinality constraint construction to further improve efficiency and memory usage, potentially yielding even greater performance gains on complex industrial benchmarks.

Summary updated

BibTeX
@inproceedings{ansotegui2015exploiting,
  author = {Carlos Ansótegui and Frédéric Didier and Joel Gabàs},
  title = {{Exploiting the Structure of Unsatisfiable Cores in MaxSAT}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure