Within-problem Learning for Efficient Lower Bound Computation in Max-SAT Solving

Han Lin, Kaile Su, Chu Min LiAAAI 2008

Introduction

The Maximum Satisfiability (Max-SAT) problem is a cornerstone of combinatorial optimization, with applications ranging from circuit debugging to bioinformatics. Exact solvers typically employ a Branch-and-Bound (BnB) framework, where the efficiency of the search is heavily dependent on the quality of the lower bound (LB)—an estimate of the minimum number of unsatisfied clauses in a given subproblem.

Current lower-bound methods often suffer from three primary inefficiencies:

  1. Redundancy: Solvers frequently rediscover identical inconsistencies as they traverse the search tree.
  2. Wasted Computational Effort: Effort expended on computing lower bounds that do not lead to immediate pruning is often discarded.
  3. Non-monotonicity: In certain solvers, the lower bound can counter-intuitively decrease deeper in the search tree, hindering pruning efficiency.

This paper introduces "within-problem learning" to address these issues, allowing search tree nodes to inherit and refine inconsistent subformulas from their parent nodes.

Methodology: The IncMax Algorithm

The proposed IncMax algorithm implements within-problem learning through several key mechanisms:

  • Inconsistency Inheritance: Child nodes inherit a set of "inconsistent subformulas" (ISS) from their parents. Since an inconsistency in a general formula remains valid when variables are assigned, this approach preserves previous computational work.
  • Subformula Shrinking: Through Unit Propagation (UP), inherited inconsistent subformulas can be simplified as variables are assigned. Smaller subformulas are more efficient, as they "free up" clauses to participate in new, disjoint inconsistencies, potentially increasing the lower bound.
  • Selective Learning ($\alpha$-ratio): To avoid overhead, learning is triggered only when the search is close to a potential prune, determined by a ratio ($\alpha$) between the current lower bound and the upper bound.
  • Adaptive Failed Literal (FL) Detection: The solver dynamically monitors the success rate of expensive FL detection. If FL has not recently contributed to backtracks, it is skipped to conserve time.

Experimental Evaluation

The researchers evaluated the incmaxsatz and incmaxsatz+fl solvers using benchmarks from the Max-SAT Evaluations 2006 and 2007. These included:

  • Random Max-2-SAT: Instances with 100 and 140 variables.
  • Random Max-3-SAT: Instances with 70 and 80 variables.
  • Structured Benchmarks: Classic instances such as brock (clique), c-fat, hamming, johnson, and keller.

Results and Discussion

The performance of incmaxsatz was compared against state-of-the-art solvers, including the original maxsatz, Toolbar3.0, and MiniMaxSat.

Efficiency and Pruning Power

On 100-variable Max-2-SAT instances, incmaxsatz demonstrated significant speedups over maxsatz. As the number of clauses increased, the performance gap widened, highlighting the scalability of the learning approach.

Solving time comparison between maxsatz and incmaxsatz on Max-2-SAT with 100 variables.

The improved efficiency is directly attributable to the increased pruning power of the inherited lower bounds. The incmaxsatz solver consistently explored fewer branches than maxsatz, confirming that the learned inconsistencies lead to a more compact search tree.

Search tree size (number of branches) comparison on Max-2-SAT with 100 variables.

Performance on Structured Benchmarks

In structured problem domains, incmaxsatz+fl emerged as the superior solver. It outperformed Toolbar3.0 and MiniMaxSat on nearly all benchmarks, often solving instances multiple times faster. For example, on the san benchmark, it achieved a 3x speedup over the next best competitor.

Conclusion and Future Work

Within-problem learning transforms static lower bound calculation into a dynamic learning process. By treating inconsistent subformulas as reusable assets, the incmaxsatz solver achieves state-of-the-art performance.

Future research will focus on extending these techniques to weighted and partial Max-SAT variants, which are highly relevant for industrial applications. Additionally, further investigation into parameter sensitivity and memory management for extremely large problem instances is warranted.

Summary updated

BibTeX
@inproceedings{lin2008within,
  author = {Han Lin and Kaile Su and Chu Min Li},
  title = {{Within-problem Learning for Efficient Lower Bound Computation in Max-SAT Solving}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2008},
}
Figure