SAT-Based Tree Decomposition with Iterative Cascading Policy Selection

Hai Xia, Stefan SzeiderAAAI 2024 · DOI

Introduction

Tree decomposition is a cornerstone of graph theory, providing a structural framework to solve complex combinatorial problems efficiently. The goal is to minimize the treewidth, a measure of how "tree-like" a graph is. While finding the optimal treewidth is NP-hard, the state-of-the-art TW-SLIM approach uses SAT solvers to iteratively improve existing decompositions. However, TW-SLIM's performance is highly dependent on its configuration parameters, which often need to change as the decomposition evolves.

The Problem: Evolving Instances

Standard algorithm configuration tools assume a static problem instance. In the context of local search for tree decomposition, the "instance" is the current decomposition itself. As the solver reduces the treewidth, the characteristics of the graph—and thus the optimal SAT solver settings—shift. A configuration that is effective at the start of the process may become inefficient or even counterproductive as the decomposition becomes "thinner."

The local improvement cycle in TW-SLIM: selecting a subgraph (A, B), solving via SAT (C), and reintegrating the improved structure (D).

Methods: From Clustering to Cascades

To address the "evolving instance" problem, the authors developed the Iterative Cascading Policy (ICP). This multi-stage approach bridges the gap between offline learning and real-time adaptation.

1. Clustering-Based Offline Configuration (CC)

The researchers first used SMAC (a Bayesian optimization tool) to identify high-performing configurations across a diverse training set of 2,664 graphs. Using constrained K-means clustering based on features like bag size and graph density, they grouped these instances into 30 distinct clusters to capture the variety of problem structures.

t-SNE visualization of the 30 clusters identified during the offline configuration phase.

2. The Iterative Cascading Policy (ICP)

The core innovation is the organization of these 30 cluster-optimized configurations into a cascade—a prioritized linear sequence.

  • Execution: The solver attempts configurations in the cascade one by one.
  • Reset: If a configuration successfully improves the decomposition, the "best-so-far" solution is updated, and the solver restarts the cascade from the beginning.
  • Dynamic Adaptation (ICP-dyn): In its most advanced form, the policy re-sorts the cascade order after every improvement based on the updated features of the new decomposition.

Key Results and Insights

The ICP approach was evaluated against a benchmark of over 3,000 graphs from sources like PACE challenges and road networks. The results demonstrate a significant leap in performance:

  • Performance Boost: At a 7,800-second timeout, the ICP-sta method achieved a total width reduction ($T\Sigma$) of 728, representing an 82.9% improvement over the hand-tuned defaults of TW-SLIM (398).
  • Efficiency: ICP variants outperformed standard portfolio selectors like AutoFolio by roughly 40%, highlighting the advantage of the iterative cascading structure over one-shot selection.
  • Robustness: The system proved effective even at short timeouts (100s), quickly identifying "low-hanging fruit" improvements.

Conclusion

The success of the Iterative Cascading Policy underscores the importance of accounting for evolving problem instances in local search. By combining structured trial-and-error with offline clustering, ICP provides a robust framework for optimizing complex, multi-parameter solvers. Future research may explore the application of ICP to other Large Neighborhood Search (LNS) frameworks to determine if these benefits generalize across different combinatorial domains.

Summary updated

BibTeX
@inproceedings{xia2024sat,
  author = {Hai Xia and Stefan Szeider},
  title = {{SAT-Based Tree Decomposition with Iterative Cascading Policy Selection}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i8.28659},
}
Figure