ASP for Anytime Dynamic Programming on Tree Decompositions

Bernhard Bliem, Benjamin Kaufmann, Torsten Schaub, Stefan WoltranIJCAI 2016

Introduction

Dynamic Programming (DP) on tree decompositions is a powerful technique for solving NP-hard graph problems by exploiting low treewidth. However, traditional "eager" implementations often suffer from memory exhaustion and a lack of "anytime" capabilities—meaning they provide no results until the entire computation is complete. This paper, presented at IJCAI-16, introduces a novel "lazy" evaluation strategy implemented using multi-shot Answer Set Programming (ASP). By computing partial solutions only when needed, this approach enables anytime solving, allowing systems to return initial solutions quickly and improve them over time.

The Challenge of Traditional Tree Decompositions

Many complex graph problems become computationally manageable if the graph exhibits a specific structure characterized by a small treewidth. The standard algorithmic approach involves constructing a tree decomposition (TD), where nodes of the original graph are grouped into "bags" arranged in a tree structure.

A sample graph and its corresponding tree decomposition into bags $n_1$ through $n_5$.

In traditional "eager" DP, algorithms compute exhaustive tables of partial solutions for every node in the TD, starting from the leaves and moving toward the root. This method faces three significant hurdles:

  1. No Anytime Results: No global solution is available until the root node's table is fully populated. If the problem is too large, the system may time out and return nothing.
  2. Computational Waste: The system often generates thousands of partial solutions that never contribute to a valid global solution.
  3. Memory Bottlenecks: For optimization problems, table sizes can grow exponentially, leading to "out of memory" errors before a solution is reached.

Methodology: Lazy Evaluation and Multi-shot ASP

The authors propose a Lazy DP framework that fundamentally changes how these tables are built. Instead of an exhaustive bottom-up pass, the system only computes a new row for a node's table when its parent node specifically requests one. This effectively transforms the problem into a search for a valid path from the leaves to the root.

Technical Innovations

  • Multi-shot ASP with Clingo: The implementation leverages the multi-shot capabilities of the clingo solver. Rather than restarting the solver for every request, a persistent solver instance is maintained at each node of the TD. "External atoms" are used to inject new information (such as a new row from a child node) into the running solver without the overhead of re-grounding the entire program.
  • Anytime Optimization: For optimization tasks, the system tracks the lowestCost found. As soon as a complete solution reaches the root, it is reported. The solver then continues to search for rows that could potentially yield a lower cost, providing better solutions as time progresses.
  • Fairness via Round-Robin: To prevent the search from getting trapped in a single branch, the algorithm employs a round-robin strategy to request partial solutions from different child nodes.

Experimental Evaluation and Key Results

The researchers tested the framework on 11 real-world public transport networks (e.g., Beijing, London, Tokyo) with treewidths ranging from 5 to 8. They evaluated performance on search problems (3-Coloring, Independent Dominating Set) and optimization problems (Vertex Cover, Dominating Set, Steiner Tree).

Experimental results comparing lazy DP, eager DP, and standard ASP solvers across various optimization problems.

Key Findings

  • Steiner Tree Breakthrough: The Steiner Tree problem is notoriously difficult for standard ASP solvers. As shown in the results table, the lazy approach was often the only method capable of returning a solution within a 10-minute timeout for complex networks like Beijing and Timisoara. It consistently found initial solutions (bolded in the table) much faster than eager methods could find an optimum.
  • Search Efficiency: For search problems like 3-Coloring, the lazy approach was 72% faster than the eager method because it could stop as soon as the first valid solution reached the root.
  • Memory and Scalability: By avoiding the materialization of full tables, the lazy approach successfully bypassed the memory bottlenecks that caused eager DP to fail on larger optimization instances.

Conclusion

By transitioning from eager to lazy evaluation, the authors have demonstrated that tree decomposition-based DP can be made both more efficient and more practical for real-world applications. The use of multi-shot ASP provides the necessary technical foundation to maintain solver state and enable anytime performance. Future work aims to optimize "join nodes" and explore more sophisticated heuristics for partial solution selection, potentially expanding the reach of this technique to even more complex logic classes.

Summary updated

BibTeX
@inproceedings{bliem2016asp,
  author = {Bernhard Bliem and Benjamin Kaufmann and Torsten Schaub and Stefan Woltran},
  title = {{ASP for Anytime Dynamic Programming on Tree Decompositions}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure