M. Abseher, N. Musliu, S. Woltran:
"Improving the Efficiency of Dynamic Programming on Tree Decompositions via Machine Learning";
Report No. DBAI-TR-2016-94,
Dynamic Programming (DP) over tree decompositions is a well-established method to solve problems - that are in general NP-hard - efficiently for instances of small treewidth. Experience shows that (i) heuristically computing a tree decomposition has negligible runtime compared to the DP step; (ii) DP algorithms exhibit a high variance in runtime when using different tree decompositions; in fact, given an instance of the problem at hand, even decompositions of the same width might yield extremely diverging runtimes. We thus propose here a novel and general method that is based on selection of the best decomposition from an available pool of heuristically generated ones. For this purpose, we require machine learning techniques that provide automated selection based on features of the decomposition rather than on the actual problem instance. As the good characterization of a tree decomposition is crucial in this process, we propose new original features. We report on extensive experiments in different problem domains which show a significant speedup when choosing the tree decomposition according to this concept over simply using an arbitrary one of the same width.
Project Head Stefan Woltran:
Created from the Publication Database of the Vienna University of Technology.