Exploiting Inference Rules to Compute Lower Bounds for MAX-SAT Solving

Han Lin, Kaile SuIJCAI 2007

Abstract

The weighted MAX-SAT problem is a fundamental optimization challenge in Boolean Satisfiability. Traditional SAT inference rules, such as resolution, are often inapplicable to MAX-SAT because they can alter the optimal solution value. This paper introduces a new logical framework based on the concept of $\Lambda$-equivalence, which identifies transformation rules that are safe for optimization. We propose two novel inference rules, 1-RES and 2-RES, and a superior lower bound function, LB5, for MAX-2-SAT. Our solver, $\Lambda$-SAT, demonstrates significant performance improvements over existing state-of-the-art tools, reducing both the search space and computational time across various random MAX-SAT benchmarks.

Introduction

Boolean Satisfiability (SAT) solvers have seen immense success due to powerful inference rules like unit propagation and resolution. However, extending these techniques to MAX-SAT—the optimization variant where one seeks to satisfy the maximum number of clauses—is non-trivial. The primary difficulty lies in the fact that standard SAT rules often change the minimum cost of unsatisfied clauses. For instance, applying resolution in a MAX-SAT context might "hide" a conflict, leading a branch-and-bound solver to underestimate the lower bound and explore redundant parts of the search tree.

To address this, we seek "safe" inference rules that either preserve the optimal value or provide a mathematically sound lower bound. This paper formalizes these requirements through a new logical framework and introduces practical rules that enhance the efficiency of MAX-SAT solving.

Theoretical Framework: $\Lambda$-equivalence

The core of our approach is the definition of $\Lambda$-equivalence within the context of bounded formulas $(F, k)$, where $k$ represents an upper bound on the cost. Two formulas are considered $\Lambda$-equivalent if they behave identically relative to any auxiliary formula $P$ that only utilizes variables from a specific set $\Lambda$.

This relaxation from strict logical equivalence allows for the application of transformation rules to a variable $x$, provided that $x$ is "local"—meaning it does not appear elsewhere in the formula (i.e., $x \notin \Lambda$). Based on this framework, we introduce:

  1. 1-RES: A simplified resolution rule that eliminates a variable appearing in exactly two specific clauses.
  2. 2-RES: A more sophisticated rule involving three clauses that further simplifies the formula while maintaining sound lower bounds.

Furthermore, we derive LB5, a new lower bound function for MAX-2-SAT. LB5 is proven to be admissible and consistently tighter than the previous standard, LB4a, enabling more effective pruning during the search process.

Experimental Evaluation

We evaluated the performance of our solver, $\Lambda$-SAT, against Toolbar, a leading solver at the time of this research. The benchmarks included random MAX-2-SAT and MAX-3-SAT instances generated via Cnfgen.

MAX-2-SAT Performance

As shown in the experimental results, $\Lambda$-SAT consistently outperforms Toolbar in both node count and execution time. For instance, on MAX-2-SAT problems with 150 variables and 500 clauses, $\Lambda$-SAT explored approximately 527,000 nodes, a substantial reduction from the 1.35 million nodes required by Toolbar. This reduction in search space translated to a nearly 3x speedup.

Performance comparison on random MAX-2-SAT instances

MAX-3-SAT Performance

The advantages of the $\Lambda$-equivalence framework extend to MAX-3-SAT instances as well. As the problem size and clause density increase, the performance gap between the two solvers widens. For instances with 80 variables and 500 clauses, $\Lambda$-SAT was more than twice as fast as Toolbar, demonstrating superior scaling.

Performance comparison on random MAX-3-SAT instances

Conclusion

The success of $\Lambda$-SAT highlights the importance of tighter lower bounds and specialized inference rules in optimization. By identifying "local" variables and resolving them away, we can perfectly capture their contribution to the total cost without exhaustive search.

Despite these gains, certain benchmarks like "Model RB" instances remain challenging. Future work will focus on integrating modern SAT solver features, such as clause learning and restarts, into the MAX-SAT framework. Additionally, extending the specific optimizations of LB5 to general MAX-SAT and higher-order clauses remains an open challenge.

Summary updated

BibTeX
@inproceedings{lin2007exploiting,
  author = {Han Lin and Kaile Su},
  title = {{Exploiting Inference Rules to Compute Lower Bounds for MAX-SAT Solving}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2007},
}
Figure