Abstract
Max-SAT solvers rely on tight lower bounds to prune search trees effectively. This work introduces five methods to detect disjoint inconsistent subformulas more efficiently. By prioritizing shorter contradictions through breadth-first unit propagation ($UP^*$) and utilizing strategic failed literal detection ($UP_{FL}$), the authors developed a solver that significantly reduces branching and improves runtime performance across random Max-SAT and Max-Cut benchmarks. The resulting $UP^*_{FL}$ solver is shown to be up to 30 times faster than previous state-of-the-art tools on hard instances.
Introduction
The Maximum Satisfiability (Max-SAT) problem is a fundamental optimization task: given a set of logic clauses, determine the maximum number that can be satisfied simultaneously. Modern exact solvers typically employ a Branch and Bound (BnB) approach, exploring a search tree of variable assignments. To manage the exponential search space, solvers compute a Lower Bound (LB) at each node—an estimate of the minimum number of clauses that will inevitably be unsatisfied. If the LB exceeds the current best solution (Upper Bound), the branch is pruned.
The efficiency of a BnB solver hinges on the quality of its lower bound. A "tight" bound prunes more branches but is computationally expensive, while a "loose" bound is fast but less effective at pruning. This paper explores techniques to find a "sweet spot" by more efficiently detecting disjoint inconsistent subformulas—independent sets of clauses that cannot be satisfied together.
Methodology
The authors propose two primary enhancements to standard lower-bounding techniques:
1. Optimized Unit Propagation ($UP^*$ and $UP^S$)
Standard solvers use Unit Propagation (UP) to find contradictions. The authors observe that the order of clause processing is critical. They introduce $UP^*$ (Breadth-First), which uses a two-queue system to prioritize newly derived unit clauses. This strategy aims to find the shortest possible contradictions, thereby "consuming" fewer clauses and leaving more of the formula available to identify additional disjoint contradictions.
2. Failed Literal Detection ($UP_{FL}$)
This look-ahead technique checks if assuming a variable $x$ is true leads to a contradiction, and if assuming $x$ is false also leads to a contradiction. If both cases fail, a new inconsistent subformula is identified. To mitigate the high computational cost of this check, the authors apply it selectively to variables appearing frequently in binary clauses.
Experimental Results
The methods were evaluated on standard benchmarks, including random Max-2SAT (100 variables), random Max-3SAT (70 variables), and Max-Cut problems (50 nodes).
Pruning Power
The $UP^*_{FL}$ method demonstrated a dramatic reduction in the size of the search tree. By identifying more disjoint inconsistent subformulas, the solver prunes branches much earlier than standard UP-based methods.
Computational Performance and Competitive Edge
While $UP_{FL}$ adds overhead, the reduction in search tree size leads to significant net speedups. On the most difficult Max-2SAT and Max-3SAT instances, the $UP^*_{FL}$ solver outperformed other contemporary state-of-the-art solvers, such as MaxSolver and Toolbar, by approximately 30 times.
Conclusion
The research highlights that "contradiction economy"—finding minimal contradictions to preserve the rest of the formula—is a powerful principle for Max-SAT solving. The $UP^*$ breadth-first approach, combined with strategic failed literal detection, provides a robust and highly competitive lower bound. Future work may involve refining the heuristics used to select variables for failed literal detection to further reduce computational overhead.
Summary updated