New Inference Rules for Efficient Max-SAT Solving

Federico Heras, Javier LarrosaAAAI 2006

Abstract

This paper presents a novel approach to Maximum Satisfiability (Max-SAT) solving by introducing three new inference rules: Directed Resolution (DRES), 2-RES, and 3-RES. By treating inference as a "movement of knowledge" to derive smaller, more restrictive clauses, the proposed Max-DPLL algorithm significantly improves lower bound quality. Experimental results across various benchmarks, including Max-2-SAT, Max-3-SAT, and Max-Cut, demonstrate speedups of up to two orders of magnitude over existing state-of-the-art solvers.

Introduction

The Maximum Satisfiability (Max-SAT) problem is the optimization counterpart to the classic Boolean Satisfiability (SAT) problem. While SAT asks whether a formula can be satisfied, Max-SAT seeks an assignment that satisfies the maximum number of clauses. This problem is central to many real-world optimization tasks, such as circuit routing, scheduling, and bioinformatics.

Most high-performance Max-SAT solvers employ a branch-and-bound search strategy. The efficiency of this approach is heavily dependent on the quality of the lower bound—the estimate of the minimum number of unsatisfied clauses in a given subproblem. If the lower bound is weak, the solver explores many branches that cannot lead to an optimal solution. While previous research often focused on procedural methods for calculating these bounds, this paper proposes a logical framework based on inference rules to transform the problem and make contradictions explicit, thereby naturally improving lower bound quality.

Methodology: Inference as Knowledge Movement

The authors introduce the Max-DPLL algorithm, which incorporates three specialized inference rules derived from the general Max-SAT resolution principle. Unlike standard SAT resolution, where new clauses are simply added to the formula, Max-SAT resolution is a transformation that preserves the total weight of the formula.

  1. Directed Resolution (DRES): This rule utilizes a fixed variable ordering to "move" weight from clauses involving variables later in the order to those involving earlier variables. This consolidation of information makes it easier for other rules to identify contradictions.
  2. Hyper-Resolution (2-RES and 3-RES): These rules are designed to identify specific patterns of clauses that, when resolved together, produce a clause with fewer literals than its parents. In Max-SAT, smaller clauses (especially unary ones) are significantly more effective at pruning the search space.

The authors conceptualize this process as a "movement of knowledge" throughout the formula. By shifting weight until it accumulates into empty clauses ($\square$), the solver identifies guaranteed costs, which serve as high-quality lower bounds for the branch-and-bound search.

Experimental Evaluation

The performance of Max-DPLL was evaluated against several state-of-the-art solvers, including MEDAC, MaxSolver, and LB4A, across a diverse set of benchmarks:

  • Random Max-2-SAT: Instances with 80 and 100 variables.
  • Random Max-3-SAT: Instances with 40 variables and varying clause densities.
  • Max-Cut: Formulated as Max-2-SAT problems based on random graphs with 60 nodes.
  • Max-Clique: 66 instances from the DIMACS challenge.

Results and Discussion

The experimental results indicate that Max-DPLL consistently outperforms its competitors, often by significant margins.

Performance comparison on Max-2-SAT benchmarks with 80 and 100 variables.

As shown in the Max-2-SAT benchmarks, Max-DPLL exhibits superior scalability as the number of clauses increases. On instances with repeated clauses, Max-DPLL achieved speedups of up to 35 times over MEDAC and over 70 times over other solvers. This advantage is most pronounced in the "hard" region of the problem space, where the clause-to-variable ratio is high.

Performance comparison on Max-3-SAT (40 variables) and Max-CUT (60 variables) benchmarks.

Similar performance gains were observed in Max-3-SAT and Max-CUT problems. In the Max-CUT benchmark, Max-DPLL was nearly 20 times faster than LB4A. Furthermore, in the Max-Clique DIMACS challenge, Max-DPLL solved 37 instances within a 2-hour limit, outperforming MEDAC (32 instances) and rivaling dedicated Max-Clique algorithms. These results highlight the power of logical inference in identifying contradictions that procedural methods might miss.

Conclusion

The introduction of Directed Resolution and hyper-resolution rules (2-RES and 3-RES) represents a significant advancement in Max-SAT solving. By treating inference as a logical transformation that concentrates "cost" into explicit contradictions, Max-DPLL achieves substantial speedups across a wide range of benchmarks.

Future research will focus on reducing the implementation overhead associated with rule matching and extending these inference techniques to handle higher-arity clauses. Additionally, integrating modern SAT solving features such as clause learning and restarts into the Max-DPLL framework remains a promising direction for further improving performance.

Summary updated

BibTeX
@inproceedings{heras2006new,
  author = {Federico Heras and Javier Larrosa},
  title = {{New Inference Rules for Efficient Max-SAT Solving}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
}
Figure