Graph Neural Networks for Combinatorial Optimization and Reasoning

Combinatorial Optimization and Reasoning with Graph Neural Networks

Quentin Cappart, Didier Chételat, Elias B. Khalil, Andrea Lodi, Christopher Morris, Petar Velickovic; 24(130):1−61, 2023.

Abstract

Combinatorial optimization, a well-established field in operations research and computer science, has traditionally focused on solving individual problem instances without considering their relationship to related data distributions. However, there has been a recent surge of interest in utilizing machine learning, particularly graph neural networks (GNNs), as a fundamental tool for combinatorial tasks. GNNs, with their inductive bias, effectively capture the combinatorial and relational aspects of input data by being invariant to permutations and aware of input sparsity. This paper provides a comprehensive review of recent advancements in this emerging field, targeting optimization and machine learning researchers.

[abs]

[pdf][bib]