New Length Dependent Algorithm for Maximum Satisfiability Problem

Vasily Alferov, Ivan BliznetsAAAI 2021 · DOI

Introduction

The Maximum Satisfiability (MAXSAT) problem is a fundamental optimization challenge in theoretical computer science. As the optimization counterpart to the Boolean Satisfiability (SAT) problem, MAXSAT seeks to determine the maximum number of clauses in a Boolean formula that can be satisfied by a single assignment. Given its NP-hard nature, researchers have spent decades refining exact algorithms to push the boundaries of solvable instance sizes.

A recent breakthrough has finally surpassed a 20-year-old record in length-dependent complexity bounds. By introducing a novel "discounted length" metric within a measure-and-conquer framework, this research establishes a new state-of-the-art upper bound of $O^*(1.0927^L)$, where $L$ represents the total number of literals in the formula.

Complexity Measures in MAXSAT

The efficiency of MAXSAT algorithms is traditionally analyzed through four primary parameters:

  1. $n$: The number of variables.
  2. $m$: The number of clauses.
  3. $k$: The target number of satisfied clauses.
  4. $L$: The total length of the formula (sum of literals across all clauses).

While clause-dependent ($m$) bounds have seen incremental improvements over the years, the length-dependent ($L$) bound is often considered the most realistic measure of input size because it is closest to the actual bit-size of the input. Prior to this work, the benchmark for $L$-dependent algorithms was set at $O^*(1.1057^L)$ by Bansal and Raman in 1999.

Comparison of clause-dependent (m) running time bounds for MAXSAT.

Methodology: Measure-and-Conquer

The authors utilize a branch-and-bound framework, enhanced by a sophisticated "measure-and-conquer" analysis. The pivotal innovation is the introduction of discounted length ($d$), defined as $d = L - n_3$, where $n_3$ denotes the number of variables appearing exactly three times in the formula.

This metric leverages the observation that variables with low frequency (appearing at most 3 times) can be resolved more efficiently using specialized sub-algorithms. By "discounting" these variables, the complexity analysis more accurately reflects the reduction in problem difficulty during branching. The paper details two algorithmic variants:

  • Simple Algorithm: Employs 7 branching rules to achieve a bound of $O^*(1.1049^L)$. Despite its simplicity, it outperforms the long-standing 1999 record.
  • Main Algorithm: Incorporates a dense case analysis and refined branching rules to reach the headline bound of $O^*(1.0927^L)$.

Key Results and Theoretical Impact

The primary contribution is the establishment of the $O^*(1.0927^L)$ upper bound. This represents a significant theoretical leap, allowing for the solution of formulas approximately 13.3% longer than previously possible within the same computational time limits. For context, recent breakthroughs in clause-dependent ($m$) algorithms only yielded a 7.5% improvement.

Comparison of length-dependent (L) running time bounds for MAXSAT, highlighting the new record.

Beyond the headline figure, the research demonstrates that the "Simple Algorithm" is not only faster than previous state-of-the-art methods but also significantly easier to implement. Furthermore, the authors developed specific reduction rules for unit clauses—literals appearing alone in a clause—which are notoriously difficult to handle in MAXSAT compared to standard SAT.

Conclusion and Future Directions

While these results represent a major theoretical milestone, the authors acknowledge that worst-case bounds do not always translate directly to average-case performance on real-world datasets. The "Main Algorithm," while theoretically superior, involves complex branching rules that pose implementation challenges.

Future work may involve refining the "discounted length" measure or applying it to related satisfiability variants. Additionally, integrating these theoretical insights into heuristic-based practical solvers could yield substantial performance gains for industry-standard MAXSAT solvers.

Summary updated

BibTeX
@inproceedings{alferov2021new,
  author = {Vasily Alferov and Ivan Bliznets},
  title = {{New Length Dependent Algorithm for Maximum Satisfiability Problem}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i5.16479},
}
Figure