MaxSAT Resolution With the Dual Rail Encoding

Maria Luisa Bonet, Sam Buss, Alexey Ignatiev, João Marques-Silva, António MorgadoAAAI 2018 · DOI

Introduction

Modern Boolean Satisfiability (SAT) solvers primarily rely on Conflict-Driven Clause Learning (CDCL), which is theoretically equivalent to General Resolution (RES). While efficient for many real-world problems, RES faces a significant bottleneck: certain combinatorial problems, such as the Pigeonhole Principle (PHP), require an exponential number of steps to solve. This paper introduces DRMaxSAT, a new propositional proof system that combines "dual rail" encoding with MaxSAT resolution to overcome these limitations.

The DRMaxSAT Framework

DRMaxSAT is built upon two core components that distinguish it from traditional SAT solving methods:

  1. Dual Rail Encoding: Instead of representing a variable $x$ and its negation $ eg x$, the system uses two new positive variables: $p_i$ (representing $x_i$ is true) and $n_i$ (representing $x_i$ is false). This transforms the original formula into a "Horn" MaxSAT problem.

  2. MaxSAT Resolution Calculus: Unlike standard resolution, which adds new learned clauses to a database, MaxSAT resolution is "resource-aware." When an inference rule is applied to two clauses, the original clauses are replaced by a new set of conclusions. This allows the system to track the "cost" of falsifying specific constraints.

The MaxSAT resolution calculus uses inference rules where premises are replaced by conclusions to maintain a resource-aware proof state.

A refutation in this system succeeds when it derives more "empty clauses" ($\perp$) than the system's allowed threshold, proving the original formula is unsatisfiable.

Theoretical Power and Insights

The most significant theoretical insight is that DRMaxSAT p-simulates general resolution and can solve the Pigeonhole Principle in polynomial time. This makes it strictly more powerful than the logic used in standard CDCL solvers. By re-encoding a problem into a MaxSAT framework, the solver can use "soft" constraints (which can be violated at a cost) to navigate the search space more effectively than hard Boolean logic.

However, DRMaxSAT is not a universal solution for all hard problems. The authors demonstrate that it still requires exponential time for the Parity Principle and cannot simulate Cutting Planes (CP), a system based on linear inequalities.

Experimental Results

The authors evaluated DRMaxSAT using hard combinatorial benchmarks, specifically the "Doubled Pigeonhole Principle" ($2PHP^{2m+1}_m$). In these tests, standard CDCL solvers like Glucose and Lingeling timed out at very small instances ($m=7$). In contrast, MaxSAT solvers using the dual rail approach, such as MaxHS and MSCG, were able to solve instances up to $m=100$ within the same time limits, provided that certain "harmful" clauses identified by the authors were removed from the encoding.

Cactus plot showing the performance of various solvers; the dual-rail-based MaxSAT solvers significantly outperform standard CDCL solvers on hard instances.

Conclusion

DRMaxSAT represents a promising bridge between theoretical proof complexity and practical solver implementation. By leveraging the resource-aware nature of MaxSAT resolution and the structural advantages of dual rail encoding, it overcomes classic resolution bottlenecks like the Pigeonhole Principle. Future work remains in automating these refutations for general-purpose solvers and exploring the potential of weighted DRMaxSAT variants.

Summary updated

BibTeX
@inproceedings{bonet2018maxsat,
  author = {Maria Luisa Bonet and Sam Buss and Alexey Ignatiev and João Marques-Silva and António Morgado},
  title = {{MaxSAT Resolution With the Dual Rail Encoding}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.1609/aaai.v32i1.12204},
}
Figure