Learning chordal extensions

Defeng Liu (), Andrea Lodi () and Mathieu Tanneau ()
Additional contact information
Defeng Liu: Polytechnique Montréal
Andrea Lodi: Polytechnique Montréal
Mathieu Tanneau: Polytechnique Montréal

Journal of Global Optimization, 2021, vol. 81, issue 1, No 2, 3-22

Abstract: 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 imitation learning scheme that mimics the elimination ordering provided by an expert rule. Results show that our imitation learning approach is effective in learning two classical elimination rules: the minimum degree and minimum fill-in heuristics, using simple Graph Neural Network models with only a handful of parameters. Moreover, the learned policies display remarkable generalization performance, across both graphs of larger size, and graphs from a different distribution.

Keywords: Chordal extensions; Machine learning; Combinatorial optimization; Numerical optimization (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-020-00973-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:81:y:2021:i:1:d:10.1007_s10898-020-00973-1

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-020-00973-1

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().