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:
- 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.
- Tighter Integration: By maintaining label consistency from preprocessing through the entire solving process, the algorithm avoids the "translation tax" associated with traditional encodings.
- 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.
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.
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