Augmenting the Power of (Partial) MaxSat Resolution with Extension

Javier Larrosa, Emma RollonAAAI 2020 · DOI

Abstract

Standard resolution systems face significant challenges when dealing with certain classes of problems, most notably the Pigeon Hole Problem (PHP), where proof sizes grow exponentially with the number of variables. This paper introduces MaxResE, a novel proof system that augments MaxSAT resolution with an "extension rule." By allowing the temporary use of negative weights during the inference process, MaxResE enables polynomial-time solutions for problems that were previously computationally intractable for standard solvers.

Introduction

In automated reasoning, resolution serves as the primary engine for proving formula unsatisfiability or finding optimal solutions. However, standard resolution has a well-documented weakness: it cannot efficiently handle problems like the Pigeon Hole Problem (PHP). For a PHP instance with $m$ holes and $m+1$ pigeons, the proof size increases exponentially, causing even state-of-the-art solvers to fail as $m$ grows. While MaxSAT resolution—which incorporates weighted soft constraints—offers more flexibility, it still suffers from this same exponential explosion. MaxResE aims to bridge this gap by introducing a mechanism to handle these "hard" problems efficiently.

The MaxResE Framework

The core innovation of the proposed system is the Extension Rule. Unlike standard MaxSAT resolution, which requires all weights to remain non-negative, MaxResE allows weights to become negative during intermediate steps of the proof.

Comparison between standard MaxSAT resolution (top) and the MaxResE system (bottom) incorporating extension rules (ext) and negative weights.

The rule allows a solver to introduce a triplet of clauses: $(C, -u)$, $(x \lor C, u)$, and $(\neg x \lor C, u)$. This process effectively "extracts" a lower bound (a guaranteed minimum cost) from the formula. The remaining "residual formula" must have non-negative weights upon completion of the proof. This approach is inspired by soft arc consistency in Constraint Satisfaction Problems (CSPs) but provides a more general and complete proof system.

Key Results and Theoretical Breakthroughs

The authors prove that MaxResE is both sound and complete, and strictly more powerful than standard MaxSAT resolution. Theoretically, MaxResE can produce a refutation for PHP in $O(m^3)$ steps, transforming an exponentially hard problem into one that is polynomially easy.

General resolution structure for n variables in the MaxResE framework, demonstrating the systematic extraction of the empty clause.

Empirical evaluations support these theoretical claims. While standard solvers like Glucose or Minisat typically time out on PHP instances with more than 15–20 holes, the MaxResE approach successfully solved instances for $m=75$ in less than 20 seconds. A key finding is that once the lower bound is extracted, the residual formula—though large—becomes extremely easy for off-the-shelf SAT solvers to satisfy, with solving times scaling linearly relative to the number of clauses.

Conclusion and Future Work

MaxResE represents a significant advancement in MaxSAT solving by generalizing techniques like dual rail encoding into a fundamental and powerful framework. However, challenges remain regarding automation. Currently, the polynomial-time proofs for PHP are manually constructed based on theoretical insights. Future research will focus on developing heuristics—such as using syntactical cues like clause width—to allow general-purpose solvers to automatically determine when and where to apply the extension rule. Integrating MaxResE into modern branch-and-bound solvers could provide superior lower bounds for a wide array of real-world optimization problems.

Summary updated

BibTeX
@inproceedings{larrosa2020augmenting,
  author = {Javier Larrosa and Emma Rollon},
  title = {{Augmenting the Power of (Partial) MaxSat Resolution with Extension}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i02.5516},
}
Figure