A Cardinal Improvement to Pseudo-Boolean Solving

Jan Elffers, Jakob NordströmAAAI 2020 · DOI

Introduction

Modern Boolean satisfiability (SAT) solvers have revolutionized automated reasoning, yet they remain fundamentally limited by their reliance on Conflict-Driven Clause Learning (CDCL). While efficient, CDCL is based on resolution, a reasoning method that struggles with certain classes of problems, such as the Pigeonhole Principle, requiring exponential time to reach a solution. This paper presents a novel technique to bridge this gap by automatically recovering higher-level "cardinality constraints" from standard Conjunctive Normal Form (CNF) inputs during the search process.

The Challenge of CNF Encoding

Pseudo-Boolean (PB) solvers utilize a more powerful reasoning method known as cutting planes. In theory, this allows them to solve "hard" problems much faster than resolution-based solvers. However, when these problems are encoded in CNF—the standard format for SAT—the high-level structure is often lost. Previous attempts to recover this structure typically relied on preprocessing, which misses critical information that only emerges as the solver learns new clauses during its search. Consequently, PB solvers often "collapse" and perform no better than standard CDCL solvers when faced with CNF inputs.

Dynamic Cardinality Recovery

The authors propose a dynamic, two-phase approach integrated directly into the solver's execution to recover cardinality constraints on the fly:

  1. The Forward Phase (Detection): The solver monitors the implication graph during unit propagation. By analyzing "cuts" in this graph, it identifies sets of clauses that serve as building blocks for higher-level constraints (e.g., "at most $k$ variables can be true").
  2. The Backward Phase (Recovery): During conflict analysis, the solver greedily combines these building blocks to reconstruct full cardinality constraints.

This "on-the-fly" detection is a significant advancement over static methods, as it allows the solver to find structure within both the original input and the newly learned clauses. To maintain efficiency, a filtering system ensures only promising building blocks are tracked, keeping computational overhead to a minimum. Furthermore, the solver employs heuristics like the VSIDS score to prioritize which variables to include when multiple potential constraints are detected.

Experimental Results

The researchers evaluated their implementation, RoundingSat-Card (RSCard), against a variety of benchmarks, including the SAT and Pseudo-Boolean Competitions and specialized "torture tests."

On the Pigeonhole Principle, RSCard demonstrated a dramatic performance advantage. While standard solvers like Clasp and Sat4jCard experienced exponential growth in running time as the number of pigeons increased, RSCard solved the instances almost instantaneously, maintaining a flat running time near zero.

Performance on the Pigeonhole Principle benchmark, showing RSCard's near-zero running time compared to the exponential growth of other solvers.

Similar results were observed in graph-based benchmarks, such as $k$-clique formulas. RSCard successfully scaled to much larger instances than its competitors, maintaining low running times where other solvers reached the 5000-second timeout threshold. This demonstrates that on-the-fly detection can effectively prevent the "collapse to CDCL" that plagues PB solvers.

Scaling performance on vertex-based benchmarks, where RSCard significantly delays the 'timeout' threshold compared to its competitors.

Key Insights and Conclusion

The study highlights that cardinality constraints represent a "sweet spot" in automated reasoning—powerful enough to provide exponential speedups over resolution while remaining computationally feasible to detect. By learning from learned clauses, the solver can maintain its theoretical reasoning advantage even when the input is flattened into CNF.

While challenges remain—particularly with constraints involving very large sets of variables where the clausal representation becomes too bulky to track—this work proves that dynamic structure recovery is a viable path toward more robust and powerful Pseudo-Boolean solvers. The minimal overhead of the detection mechanism ensures that the solver remains competitive even on problems where no higher-level structure is found, paying only a small "tax" for the potential of massive speedups.

Summary updated

BibTeX
@inproceedings{elffers2020cardinal,
  author = {Jan Elffers and Jakob Nordström},
  title = {{A Cardinal Improvement to Pseudo-Boolean Solving}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i02.5508},
}
Figure