Learning Elimination Ordering for Tree Decomposition Problem
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.
Code (0)
등록된 구현이 없습니다.
Tasks
reinforcement-learningReinforcement LearningReinforcement Learning (RL)Tree DecompositionSimilar Papers 제목 키워드 기반
Alpha Elimination: Using Deep Reinforcement Learning to Reduce Fill-In during Sparse Matrix Decomposition
A large number of computational and scientific methods commonly require decomposing a sparse matrix into triangular factors as LU decomposition. A common problem faced during this decomposition is that even though the gi…
Decision MakingDeep Reinforcement LearningApplying machine learning to the problem of choosing a heuristic to select the variable ordering for cylindrical algebraic decomposition
Cylindrical algebraic decomposition(CAD) is a key tool in computational algebraic geometry, particularly for quantifier elimination over real-closed fields. When using CAD, there is often a choice for the ordering placed…
BIG-bench Machine LearningRevisiting Variable Ordering for Real Quantifier Elimination using Machine Learning
Cylindrical Algebraic Decomposition (CAD) is a key proof technique for formal verification of cyber-physical systems. CAD is computationally expensive, with worst-case doubly-exponential complexity. Selecting an optimal …
Matrix and graph representations of vine copula structures
Vine copulas can efficiently model multivariate probability distributions. This paper focuses on a more thorough understanding of their structures, since in the literature, vine copula representations are often ambiguous…
Comparing machine learning models to choose the variable ordering for cylindrical algebraic decomposition
There has been recent interest in the use of machine learning (ML) approaches within mathematical software to make choices that impact on the computing performance without affecting the mathematical correctness of the re…
BIG-bench Machine Learning