A Clause Tableau Calculus for MaxSAT

Chu Min Li, Felip Manyà, Joan Ramon SolerIJCAI 2016

A Clause Tableau Calculus for MaxSAT

Abstract

This paper introduces the first clause tableau calculus specifically designed for MaxSAT, the optimization version of the Boolean Satisfiability problem. Unlike traditional SAT methods that primarily preserve satisfiability, this calculus preserves the count of falsified clauses. This property allows researchers to determine optimal assignments by counting empty clauses in a saturated proof tree. The calculus is shown to be sound and complete, and it extends naturally to Weighted and Partial MaxSAT problems.

Introduction

In Boolean logic, the Satisfiability (SAT) problem asks whether a given formula can be satisfied by any variable assignment. MaxSAT extends this to an optimization problem: if a formula cannot be fully satisfied, what is the minimum number of clauses that must be falsified?

While SAT solvers have reached high levels of efficiency, many of their core techniques, such as unit propagation, are "unsound" for MaxSAT because they do not necessarily preserve the total number of falsified clauses. Existing MaxSAT-specific inference rules, like MaxSAT resolution, often involve complex "compensation clauses" to maintain this count. The authors address these challenges by adapting the tableau method—a tree-based proof system—into a simpler, more intuitive framework for MaxSAT optimization.

The Clause Tableau Calculus

The proposed calculus builds a "Clause Tableau" using a set of formal rules designed to explore the search space while tracking contradictions.

  1. The Extension Rule: For a clause $(x \lor y \lor z)$, the current branch is split into three sub-branches, each representing a literal in the clause. This performs a case distinction across the possible ways to satisfy the clause.
  2. The Contradiction Rule: When a branch contains both a literal $l$ and its negation $\bar{l}$, an empty clause ($\square$) is added to that branch. Crucially, these two literals are then "marked" as used to prevent double-counting the same conflict.
  3. Saturation: The rules are applied iteratively until no further moves are possible.
  4. Cost Calculation: The "cost" of any branch is defined as the number of empty clauses ($\square$) it contains. The solution to the MaxSAT problem is the minimum cost found across all branches in the fully saturated tableau.
Figure 1: A saturated clause tableau showing multiple branches and the derivation of empty clauses ($\square$).

Key Insights: The Marking Mechanism

A core breakthrough of this calculus is the marking mechanism. By marking unit clauses once they are used in a contradiction, the system ensures that the minimum number of falsified clauses remains invariant throughout the transformation. This allows the tableau to identify multiple independent contradictions within a single branch without overcounting.

Figure 2: Illustration of the marking mechanism (bolded literals) during the application of the contradiction rule.

Unlike MaxSAT resolution, which generates numerous complex clauses to maintain the falsification count, this tableau method only derives empty or unit clauses. Furthermore, the authors note that this approach requires only polynomial space, avoiding the exponential memory requirements of some other MaxSAT algorithms like variable elimination.

Theoretical Results and Extensions

The authors provide a mathematical proof for the soundness and completeness of the calculus. For any multiset of clauses $\phi$, the minimum number of empty clauses in a saturated tableau is exactly equal to the minimum number of clauses falsified in $\phi$.

The paper also extends the calculus to handle more complex variants:

  • Weighted MaxSAT: Where clauses have associated weights. The contradiction rule is modified to subtract weights and pass the "remainder" down the branch.
  • Partial MaxSAT: Where "hard" clauses must be satisfied. These are handled by ensuring any branch falsifying a hard clause is considered invalid (infinite cost).

Limitations and Future Work

While theoretically robust, the paper focuses on foundational logic and does not include empirical benchmarks against state-of-the-art industrial solvers. Additionally, the current calculus is specific to Conjunctive Normal Form (CNF) and is not applicable to MinSAT (maximizing falsified clauses), as the extension rule does not preserve the maximum count. Future research aims to extend this calculus to First-Order Logic and integrate clause branching strategies into existing Branch-and-Bound solvers.

Summary updated

BibTeX
@inproceedings{li2016clause,
  author = {Chu Min Li and Felip Manyà and Joan Ramon Soler},
  title = {{A Clause Tableau Calculus for MaxSAT}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure