Improving the Efficiency of Dynamic Programming on Tree Decompositions via Machine Learning

Abseher, Michael; Dusberger, Frederico; Musliu, Nysret; Woltran, Stefan

Improving the Efficiency of Dynamic Programming on Tree Decompositions via Machine Learning

Michael Abseher, Frederico Dusberger, Nysret Musliu, Stefan Woltran

Download BibTeX Cite

Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 275-281.

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.

Michael Abseher, Frederico Dusberger, Nysret Musliu, and Stefan Woltran. 2015. Improving the Efficiency of Dynamic Programming on Tree Decompositions via Machine Learning. In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15. IJCAI, 275–281. https://ijcai.org/proceedings/2015/45

@inproceedings{ijcai2015p45,
  title     = {Improving the Efficiency of Dynamic Programming on Tree Decompositions via Machine Learning},
  author    = {Abseher, Michael and Dusberger, Frederico and Musliu, Nysret and Woltran, Stefan},
  booktitle = {Proceedings of the Twenty-Fourth International Joint Conference on
               Artificial Intelligence, {IJCAI-15}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Qiang Yang and Michael Wooldridge},
  pages     = {275--281},
  year      = {2015},
  month     = {7},
  note      = {Main Track},
  url       = {https://ijcai.org/proceedings/2015/45},
}

TY  - CPAPER
TI  - Improving the Efficiency of Dynamic Programming on Tree Decompositions via Machine Learning
AU  - Abseher, Michael
AU  - Dusberger, Frederico
AU  - Musliu, Nysret
AU  - Woltran, Stefan
T2  - Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15
PB  - International Joint Conferences on Artificial Intelligence
PY  - 2015
SP  - 275
EP  - 281
UR  - https://ijcai.org/proceedings/2015/45
ER  -