Learning chordal extensions

DOI10.1007/S10898-020-00973-1MaRDI QIDQ2046324zbMATH OpenOpenAlexFDO

Authors Defeng Liu, Andrea Lodi, Mathieu Tanneau

Publication date 17 August 2021

Published in Journal of Global Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1910.07600

zbMATH Keywords

chordal extensionscombinatorial optimizationmachine learningnumerical optimization

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Markov and semi-Markov decision processes (90C40)

Abstract: A highly influential ingredient of many techniques designed to exploit sparsity in numerical optimization is the so-called chordal extension of a graph representation of the optimization problem. The definitive relation between chordal extension and the performance of the optimization algorithm that uses the extension is not a mathematically understood task. For this reason, we follow the current research trend of looking at Combinatorial Optimization tasks by using a Machine Learning lens, and we devise a framework for learning elimination rules yielding high-quality chordal extensions. As a first building block of the learning framework, we propose an on-policy imitation learning scheme that mimics the elimination ordering provided by the (classical) minimum degree rule. The results show that our on-policy imitation learning approach is effective in learning the minimum degree policy and, consequently, produces graphs with desirable fill-in characteristics.

Recommendations

• On the minimum chordal completion polytope
• Towards using the chordal graph polytope in learning decomposable models
• A chordal preconditioner for large-scale optimization
• Learning chordal Markov networks via stochastic local search
• Chordal-TSSOS: a moment-SOS hierarchy that exploits term sparsity with chordal extension

Cites work

• Chordal decomposition in operator-splitting methods for sparse semidefinite programs
• Computing the Minimum Fill-In is NP-Complete
• Exploiting sparsity in semidefinite programming via matrix completion. I: General framework
• Exploiting sparsity in semidefinite programming via matrix completion. II: Implementation and numerical results
• scientific article; zbMATH DE number 3148886 (Why is no real title available?)
• scientific article; zbMATH DE number 1149166 (Why is no real title available?)
• scientific article; zbMATH DE number 3420184 (Why is no real title available?)
• scientific article; zbMATH DE number 964349 (Why is no real title available?)
• LOQO:an interior point code for quadratic programming
• Machine learning for combinatorial optimization: a methodological tour d'horizon
• Minimum fill-in of sparse graphs: kernelization and approximation
• Nested Dissection of a Regular Finite Element Mesh
• On the minimum chordal completion polytope
• Perceptual Interpretation for Autonomous Navigation through Dynamic Imitation Learning
• Positive semidefinite matrices with a given sparsity pattern
• Solving Real-World Linear Programs: A Decade and More of Progress
• The elimination form of the inverse and its application to linear programming
• The Evolution of the Minimum Degree Ordering Algorithm
• The Role of Elimination Trees in Sparse Factorization
• The University of Florida sparse matrix collection

Cited in

(2)

• Creating improvisations on chord progressions using suffix trees
• scientific article; zbMATH DE number 5038484 (Why is no real title available?)

Describes a project that uses

Uses Software

• LOQO
• SparseMatrix
• GNNExplainer

This page was built for publication: Learning chordal extensions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2046324)