Improving the Lower Bound in Branch-and-Bound Algorithms for MaxSAT

Shuolin Li, Chu-Min Li, Jordi Coll, Djamal Habet, Felip ManyàAAAI 2025 · DOI

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 possible number of clauses. This problem is central to various real-world applications, including hardware routing, scheduling, and protein design. Modern exact solvers typically employ a Branch-and-Bound (BnB) framework. The efficiency of these solvers hinges on the quality of the Lower Bound (LB)—an estimate of the minimum number of clauses that must be falsified in any given search branch. A tighter LB allows the solver to prune sub-optimal branches earlier, significantly reducing the search space.

The Challenge of Disjoint Cores

Traditionally, BnB solvers calculate the lower bound by identifying "cores"—subsets of clauses that are mutually unsatisfiable. However, a significant limitation in existing algorithms is the "disjointness constraint." Once a soft clause is assigned to a core, it is "locked" and cannot be utilized to identify subsequent cores. This constraint often leads to loose lower bounds because many potential cores remain undetected, forcing the solver to explore unnecessary nodes in the search tree.

The Unlocking Mechanism

To address this, researchers have introduced a novel unlocking mechanism that allows clauses to be reused across multiple cores while maintaining mathematical soundness.

Unweighted MaxSAT

In the unweighted case, where every clause has a unit cost, the algorithm leverages unit propagation to detect cores. When a clause within an existing core is falsified during the search, the algorithm "unlocks" the remaining clauses in that core. These clauses are then returned to the pool of available constraints, enabling the detection of new, overlapping cores.

Weighted MaxSAT

The weighted case presents more complexity as clauses carry different penalties. The researchers developed a sophisticated accounting system using two primary metrics: wlock(s, c), the weight of clause $s$ currently locked into core $c$, and rw(s), the "remaining weight" of a clause available for new cores.

Figure 3: Illustration of the weighted unlocking mechanism using weight splitting and tracking metrics within a search tree.

When a core is identified, weights are carefully partitioned. If a core's total weight is exhausted by falsified literals, the remaining weights of its constituent clauses are released. To manage the computational overhead of these calculations, a two-stage lookahead is used: the solver first attempts a standard fast LB calculation and only resorts to the intensive unlocking logic if the initial attempt fails to prune the branch.

Experimental Evaluation

The proposed mechanism was evaluated using benchmarks from the MaxSAT Evaluation (MSE) 2019-2023, comprising nearly 4,000 instances across unweighted and weighted tracks.

Figure 5: Performance comparison (cactus plots) for unweighted (left) and weighted (right) tracks, showing instances solved over time. The red markers represent the solvers using the new unlocking mechanism.

The results demonstrate a clear performance advantage. In the unweighted track, the number of solved instances increased from 1,397 to 1,427. Similarly, in the weighted track, solved instances rose from 1,416 to 1,446. The cactus plots in Figure 5 show that solvers equipped with the unlocking mechanism (MaxCDCL+Unlock and WMaxCDCL+Unlock) consistently outperformed their baselines across various time limits.

Conclusion

By breaking the traditional disjointness constraint, the unlocking mechanism provides a significantly tighter lower bound for MaxSAT solvers. This advancement led to a first-place finish in the 2024 MaxSAT Evaluation. Future research will explore applying this logic to other NP-hard problems like MaxClique and investigating its potential for improving upper bound calculations.

Summary updated

BibTeX
@inproceedings{li2025improving,
  author = {Shuolin Li and Chu-Min Li and Jordi Coll and Djamal Habet and Felip Manyà},
  title = {{Improving the Lower Bound in Branch-and-Bound Algorithms for MaxSAT}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i11.33226},
}
Figure