Combinatorial optimization and reasoning with graph neural networks (2021-02-18T00:00:00.000000Z)

TL;DR

A conceptual review of recent key advancements in combinatorial optimization is presented, aiming at researchers in both optimization and machine learning.

Abstract

Combinatorial optimization is a well-established area in operations research and computer science. Until recently, its methods have mostly focused on solving problem instances in isolation, ignoring the fact that they often stem from related data distributions in practice. However, recent years have seen a surge of interest in using machine learning, especially graph neural networks, as a key building block for combinatorial tasks, either directly as solvers or by enhancing the former. This paper presents a conceptual review of recent key advancements in this emerging field, aiming at researchers in both optimization and machine learning.

Authors

Petar Velickovic

7 papers

Quentin Cappart

2 papers

D. Chételat

2 papers

TL;DR

Abstract

Authors

References275 items

Dual Algorithmic Reasoning

Learnable Commutative Monoids for Graph Neural Networks

Continuous Neural Algorithmic Planners

Learning to Compare Nodes in Branch and Bound with Graph Neural Networks

Learning to Configure Computer Networks with Neural Algorithmic Reasoning

A Generalist Neural Algorithmic Learner

Learning to Search in Local Branching

Learning To Cut By Looking Ahead: Cutting Plane Selection via Imitation Learning

A Deep Reinforcement Learning Framework For Column Generation

The CLRS Algorithmic Reasoning Benchmark

MIP-GNN: A Data-Driven Framework for Guiding Combinatorial Solvers

Learning to branch with Tree MDPs

Improving Variable Orderings of Approximate Decision Diagrams Using Reinforcement Learning

Graph Neural Networks are Dynamic Programmers

The Machine Learning for Combinatorial Optimization Competition (ML4CO): Results and Insights

Augment with Care: Contrastive Learning for Combinatorial Problems

End-to-end Algorithm Synthesis with Recurrent Networks: Logical Extrapolation Without Overthinking

What's Wrong with Deep Learning in Tree Search for Combinatorial Optimization

Advancing mathematics by guiding human intuition with AI

Towards combinatorial invariance for Kazhdan-Lusztig polynomials

How to transfer algorithmic reasoning knowledge to learn new algorithms?

Neural Algorithmic Reasoners are Implicit Planners

Foundations of Machine Learning

Approximation Algorithms

Reasoning-Modulated Representations

Algorithmic Concept-based Explainable Reasoning

Combinatorial optimization with physics-inspired graph neural networks

Goal-Aware Neural SAT Solver

Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Prediction

Can You Learn an Algorithm? Generalizing from Easy to Hard Problems with Recurrent Networks

Implicit MLE: Backpropagating Through Discrete Exponential Family Distributions

A graph placement methodology for fast chip design

The Power of the Weisfeiler-Leman Algorithm for Machine Learning with Graphs

End-to-End Constrained Optimization Learning: A Survey

Graph Neural Networks Inspired by Classical Iterative Algorithms

Size-Invariant Graph Representations for Graph Classification Extrapolations

Persistent Message Passing

SeaPearl: A Constraint Programming Solver guided by Reinforcement Learning

Conflict-Driven Clause Learning SAT Solvers

MIPLIB 2017: data-driven compilation of the 6th mixed-integer programming library

On the Unreasonable Effectiveness of SAT Solvers

Solving Mixed Integer Programs Using Neural Networks

Design Space for Graph Neural Networks

Ecole: A Gym-like Library for Machine Learning in Combinatorial Optimization Solvers

A step towards neural genome assembly

Interior Point Solving for LP-based prediction+optimisation

XLVIN: eXecuted Latent Value Iteration Nets

From Local Structures to Size Generalization in Graph Neural Networks

Learning Mesh-Based Simulation with Graph Networks

The Surprising Power of Graph Neural Networks with Random Node Initialization

Graph neural induction of value iteration

How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks

A Survey on Reinforcement Learning for Combinatorial Optimization

OR-Gym: A Reinforcement Learning Library for Operations Research Problem

Learning Branching Heuristics for Propositional Model Counting

Strong Generalization and Efficiency in Neural Programs

NeuroGIFT: Using a Machine Learning Based Sat Solver for Cryptanalysis

Hybrid Models for Learning to Branch

Learning What to Defer for Maximum Independent Sets

Learning the travelling salesperson problem requires rethinking generalization

Learning TSP Requires Rethinking Generalization

Pointer Graph Networks

On the Bottleneck of Graph Neural Networks and its Practical Implications

Learning to Solve Combinatorial Optimization Problems on Real-World Graphs in Linear Time

Combining Reinforcement Learning and Constraint Programming for Combinatorial Optimization

Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs

OpenGraphGym: A Parallel Reinforcement Learning Framework for Graph Optimization Problems

Learning Combinatorial Optimization on Graphs: A Survey With Applications to Networking

Neural Bipartite Matching

Normalized Attention Without Probability Cage

Machine Learning on Graphs: A Model and Comprehensive Taxonomy

Machine-Learning-Based Column Selection for Column Generation

Principal Neighbourhood Aggregation for Graph Nets

Residual Shuffle-Exchange Networks for Fast Processing of Long Sequences

Predicting Propositional Satisfiability via End-to-End Learning

The SCIP Optimization Suite 7.0