[Back]


Talks and Poster Presentations (with Proceedings-Entry):

F. Dusberger, M. Abseher, N. Musliu, S. Woltran:
"Improving the Efficiency of Dynamic Programming on Tree Decompositions via Machine Learning";
Talk: Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015, Buenos Aires, Argentina; 07-25-2015 - 07-31-2015; in: "Proceedings of IJCAI 2015, the 24th International Joint Conference on Artificial Intelligence", Q. Yang, M. Wooldridge (ed.); AAAI Press, (2015), ISBN: 978-1-57735-738-4; 275 - 282.



English abstract:
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 a selection of the best decomposition from an available pool of heuristically generated ones. For this purpose, we require machine learning techniques based on features of the decomposition rather than on the actual problem instance. 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.

Keywords:
dynamic programming, tree decompositions, machine learning


Related Projects:
Project Head Nysret Musliu:
Künstliche Intelligenz in der Personalplanung

Project Head Stefan Woltran:
Answer-Set Programming Erweiterungen für Problemlösungen auf Zerlegungen

Project Head Stefan Woltran:
START


Created from the Publication Database of the Vienna University of Technology.