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