Stefan Woltran
Viena University of Technology, Austria
Title: Dynamic Programming on Tree Decomposition in Practice. Some Lessons Learned.
Abstract:
Many prominent NP-hard problems have been shown tractable for
bounded treewidth. To put these results to practice, dynamic
programming (DP) via a traversal of the nodes of a tree
decomposition is the standard technique. However, the concrete
implementation of suitable efficient algorithms is often
tedious. To this end, we have developed the D-FLAT system
which allows the user to specify the DP algorithm in a
declarative fashion and where the computation of intermediate
solutions is delegated to a logic-programming system.
In this talk, we first give a brief introduction to the
D-FLAT system and demonstrate its usage on some standard DP
algorithms. In the second part of the talk, we reflect on some
of our experiences. In particular, we address the following
issues:
(i) The actual structure of the tree decomposition heavily
influences the performance of DP algorithms in practice; we
discuss some solutions how to overcome this problem.
(ii) DP algorithms for AI problems typically show recurring
patterns that call for tasks like subset-minimization. We
introduce a new method for obtaining DP algorithms from simpler
principles, which is also supported by D-FLAT.
(iii) We present ongoing work on an alternative version of our
approach. Hereby, BDDs are employed as internal datastructures.
This not only leads to better performance but also gives a handle
for defining alternative DP algorithms which delay the
materialization of partial solutions.