On the Resiliency of Unit Propagation to Max-Resolution

André Abramé, Djamal HabetIJCAI 2015

Introduction

In the domain of Max-SAT solving, efficiency is often dictated by the quality of lower bound estimations. While empirical evidence has long suggested that certain "learning" patterns enhance solver performance, the theoretical underpinnings of this phenomenon remained unclear. This paper, originally presented at IJCAI 2015, introduces the concept of UP-resiliency to explain why specific formula transformations succeed where others fail.

The Fragmentation Problem

Modern Branch and Bound (BnB) solvers for Max-SAT identify disjoint Inconsistent Subsets (IS) using Unit Propagation (UP). Once an IS is found, the solver applies max-resolution to transform the formula, effectively "marking" the inconsistency to prevent double-counting. However, this process often leads to "fragmentation."

Fragmentation occurs when the logical information necessary for UP to detect future inconsistencies is scattered across multiple new clauses. A poor transformation can render UP "blind," resulting in weak lower bounds and an exponentially larger search space. The authors argue that while max-resolution is logically sound, it can be "computationally destructive" if it hinders the propagation power of the solver.

Quantifying UP-Resiliency

To address fragmentation, the authors propose a formal metric: UP-resiliency. A transformation is considered UP-resilient if the Unit Propagation mechanism can still propagate the same literals after the transformation as it could before, given the same variable assignments.

A max-resolution derivation showing the transformation of original clauses into a set of resolvents and compensation clauses.

The study explores how the order of resolution steps affects this metric. For instance, the "Smallest Resolvent" (SIR) heuristic was found to preserve significantly more resiliency than standard propagation-order methods. By increasing average resiliency from 54% to 60%, the SIR heuristic reduced average solving times from 135.5 seconds to 108.4 seconds in experimental trials.

Key Results and Solver Performance

The researchers validated their framework using the AHMAXSAT solver on benchmarks from the Max-SAT Evaluation 2013. Their analysis confirmed that established learning patterns (like P1, P2, and P3) are effective precisely because they maintain nearly 100% UP-resiliency. In contrast, schemes like IRS (used in MiniMaxSat) showed lower resiliency (~78%) and required exploring four times as many nodes.

3D surface plots showing the relationship between UP-resiliency percentages and solver performance (solving time and decision count).

Experimental data revealed a "sweet spot" for solver health: performance is optimal when the minimum UP-resiliency of transformations is maintained between 60% and 100%. As shown in the performance surfaces above, dropping below this threshold causes a dramatic explosion in the number of search decisions and total solving time required to reach a solution.

Conclusion

The introduction of UP-resiliency provides a vital theoretical bridge between the logical soundness of max-resolution and the computational efficiency of Unit Propagation. While the current implementation for checking resiliency adds some overhead (roughly 25%), the insights gained pave the way for more intelligent, resiliency-aware search algorithms that can avoid the pitfalls of formula fragmentation.

Summary updated

BibTeX
@inproceedings{abrame2015resiliency,
  author = {André Abramé and Djamal Habet},
  title = {{On the Resiliency of Unit Propagation to Max-Resolution}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure