Improving the Effectiveness of SAT-Based Preprocessing for MaxSAT

Jeremias Berg, Paul Saikko, Matti JärvisaloIJCAI 2015

Introduction

In Boolean Satisfiability (SAT) solving, preprocessing—the act of simplifying a formula before the main search begins—is a critical component of modern high-performance solvers. However, extending these techniques to MaxSAT, the optimization variant of SAT, presents significant challenges. Naive application of standard SAT simplifications like variable elimination can inadvertently alter the optimal solution. While the Labelled CNF (LCNF) framework was introduced to make preprocessing "safe" for MaxSAT, its use as a simple front-end often leads to performance degradation. The solver remains "blind" to the logical simplifications, resulting in redundant variables and lost inferences.

The Lifted MaxHS Approach

This paper introduces LMHS+pre, a "lifted" version of the MaxHS algorithm designed to integrate directly with LCNF-based preprocessing. MaxHS typically alternates between a SAT solver to identify unsatisfiable cores and an Integer Programming (IP) solver to find minimum hitting sets.

The core innovation of LMHS+pre lies in three areas:

  1. Direct Label Re-use: Instead of translating preprocessed formulas back into standard MaxSAT, which introduces unnecessary complexity, the solver uses LCNF labels directly as assumption variables within the SAT solver loop.
  2. Tighter Integration: By maintaining label consistency from preprocessing through the entire solving process, the algorithm avoids the "translation tax" associated with traditional encodings.
  3. Enhanced Logical Inference: Working at the LCNF level allows the IP solver to derive more powerful linear constraints (eq-seeding), helping it understand logical relationships between soft clauses that would otherwise be invisible.
Figure 6: Performance comparison between MHS, MHS+pre, and the proposed LMHS+pre across different benchmarks.

As shown in the scatter plots above, the "lifted" approach (LMHS+pre) consistently outperforms both the baseline MHS and the naive black-box preprocessing approach (MHS+pre). The middle plot specifically highlights how LMHS+pre shifts many instances toward faster solve times compared to standard MHS.

Experimental Results

The authors evaluated LMHS+pre on 624 instances from the 2014 MaxSAT Evaluation, comprising 214 "crafted" and 410 "industrial" problems.

The results demonstrate a clear advantage for the integrated approach. On crafted benchmarks, where standard preprocessing often hindered performance, the lifted version achieved significant gains. In the industrial category, LMHS+pre reduced the number of timeouts from 111 (standard MHS) to 99.

Figure 3: Cactus plot showing the number of instances solved within a given timeout for various solver configurations.

The cactus plot illustrates that LMHS+pre (represented by black circles) solves the highest number of instances across the entire time spectrum, outperforming other state-of-the-art configurations like Eva and various MHS baselines.

Conclusion

By "lifting" the MaxHS algorithm to operate directly on the LCNF framework, the authors have bridged the gap between powerful SAT preprocessing and MaxSAT optimization. This tighter integration avoids the overhead of traditional encodings and allows for more sophisticated logical inferences during the search process. Future work may involve deeper "in-process" integration and exploring similar lifting techniques for core-guided MaxSAT solvers.

Summary updated

BibTeX
@inproceedings{berg2015improving,
  author = {Jeremias Berg and Paul Saikko and Matti Järvisalo},
  title = {{Improving the Effectiveness of SAT-Based Preprocessing for MaxSAT}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure