Reducing SAT to Max2SAT

Carlos Ansótegui, Jordi LevyIJCAI 2021 · DOI

TL;DR

This paper introduces a novel, constructive method for transforming SAT problems into Max2SAT problems, aiming to leverage the efficiency of MaxSAT solvers for challenging SAT instances. The authors demonstrate that this transformation can lead to more efficient solutions for certain hard SAT problems, particularly those related to the Pigeon Hole Principle, and propose a framework for a new generation of SAT solvers.

What Problem Does This Paper Address?

The paper tackles the challenge of solving computationally difficult Satisfiability (SAT) problems. While SAT solvers have made significant progress, certain classes of problems remain intractable. The authors propose using Max2SAT solvers, which optimize the number of satisfied clauses, as a potential avenue to overcome these limitations. The core of this approach lies in "gadgets" – combinatorial structures that translate constraints from one problem type (SAT) to another (Max2SAT). However, existing methods for constructing these gadgets are often ad-hoc and lack intuitive or efficient generalizable approaches. This paper aims to provide a systematic and efficient way to construct these gadgets, thereby enabling the use of Max2SAT solvers for SAT problems.

Methods

The paper introduces a new "regular gadget" for transforming kSAT clauses into Max2SAT clauses. This gadget is designed to be constructive and generalizable for any clause length $k$. The authors then refine this regular gadget by applying MaxSAT resolution rules, resulting in a more efficient gadget with a better "alpha" parameter (a measure of gadget quality). They also explore automatically computing gadgets using Mixed Integer Programming (MIP) to find optimal gadgets for small $k$, comparing these results to their constructive methods.

A key contribution is the demonstration of how this SAT-to-Max2SAT reduction can be used to solve SAT problems in practice. They propose an algorithm that strategically decides which clauses to keep as "hard" (directly passed to the SAT solver) and which to translate using the gadget. This approach aims to balance the strengths of SAT and MaxSAT solvers.

Datasets

Not discussed in the paper. The paper focuses on theoretical constructions and experimental evaluation using instances of the Pigeon Hole Principle (PHPm).

Key Insights and Ideas

  • Constructive Gadget Generation: The paper moves beyond ad-hoc gadget design by providing a systematic, constructive method for creating gadgets from kSAT to Max2SAT. This makes the transformation process more accessible and scalable.
  • MaxSAT Resolution for Gadget Refinement: Applying MaxSAT resolution rules to existing gadgets can significantly improve their quality (reducing the 'alpha' parameter), leading to more efficient translations.
  • MaxSAT Solvers as SAT Solvers: The core idea is that MaxSAT solvers, when fed appropriately transformed SAT instances, can outperform traditional SAT solvers on certain hard problem classes. This opens up a new paradigm for SAT solving.
  • Strategic Clause Handling: The proposed algorithm for SAT solving via Max2SAT intelligently distinguishes between clauses that are "hard" and those that are translated. This hybrid approach leverages the strengths of both SAT and MaxSAT solvers.
  • Pigeon Hole Principle as a Benchmark: The Pigeon Hole Principle (PHP) is used as a challenging benchmark. The paper shows that translating PHP instances into Max2SAT and using MaxSAT solvers can lead to significantly faster solutions compared to direct SAT solving.

Key Results

  • The paper presents a "regular gadget" for kSAT to Max2SAT, which is then refined to achieve a gadget with an alpha parameter of $2.5(k-2) + 1$. This refined gadget is shown to be optimal for $k=3, 4, 5$ when compared to automatically computed gadgets.
  • Experimental results on Pigeon Hole Principle instances (PHPm) demonstrate that using MaxSAT solvers with the proposed gadgets significantly outperforms traditional SAT solvers (like CaDiCaL) and other MaxSAT approaches. For instance, solving PHPm instances up to $n=100$ took seconds with the regular gadget, whereas SAT solvers timed out or took much longer.
  • The proposed algorithm for SAT solving via Max2SAT, when applied to PHPm, achieved impressive speedups, with MaxSAT solvers solving instances up to $n=100$ in under 2 seconds using the regular gadget.

Limitations and Future Work

  • Gadget Optimality for Large k: While the refined regular gadget is shown to be optimal for small $k$ and competitive, the paper acknowledges that it might not be the absolute optimal gadget for all $k$. Further research into constructive methods for optimal gadgets is suggested.
  • Generalizability of the Approach: The paper demonstrates the effectiveness of the approach on the Pigeon Hole Principle. Future work could explore its applicability to a wider range of hard SAT problem classes.
  • Algorithm 1 Refinement: The paper proposes Algorithm 1 as a conceptual base for a new generation of SAT solvers. Further research is needed to refine this algorithm, particularly the "harden" function, to optimize the balance between hard clauses and translated clauses.
  • Theoretical Implications: The paper hints at theoretical advantages, such as translating problems with exponentially long resolution proofs into problems solvable with polynomial MaxSAT resolution steps. Further exploration of these theoretical connections is warranted.

Summary updated

BibTeX
@inproceedings{ansotegui2021reducing,
  author = {Carlos Ansótegui and Jordi Levy},
  title = {{Reducing SAT to Max2SAT}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.24963/ijcai.2021/189},
}
Figure