Learning Elimination Ordering for Tree Decomposition Problem

Abstract

We propose a Reinforcement Learning-based approach to approximately solve the Tree Decomposition problem. Recently, it was shown that learned heuristics could successfully solve combinatorial problems. We establish that our approach successfully generalizes from small graphs, where an optimal Tree Decomposition can be found by exact algorithms, to large instances of practical interest, while still having very low time-to-solution. On the other hand, the agent-based approach surpasses all classical greedy heuristics by the quality of the solution.

PDF NeurIPSW OpenReview Semantic Scholar

Cite

Text

Khakhulin et al. "Learning Elimination Ordering for Tree Decomposition Problem." NeurIPS 2020 Workshops: LMCA, 2020.

Markdown

[Khakhulin et al. "Learning Elimination Ordering for Tree Decomposition Problem." NeurIPS 2020 Workshops: LMCA, 2020.](https://mlanthology.org/neuripsw/2020/khakhulin2020neuripsw-learning/)

BibTeX

@inproceedings{khakhulin2020neuripsw-learning,
  title     = {{Learning Elimination Ordering for Tree Decomposition Problem}},
  author    = {Khakhulin, Taras and Schutski, Roman and Oseledets, Ivan},
  booktitle = {NeurIPS 2020 Workshops: LMCA},
  year      = {2020},
  url       = {https://mlanthology.org/neuripsw/2020/khakhulin2020neuripsw-learning/}
}