Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon

By Yoshua Bengio, Andrea Lodi, Antoine Prouvost. 2018

1,843 citations recorded by the source corpus.

This paper surveys the recent attempts, both from the machine learning and operations research communities, at leveraging machine learning to solve combinatorial optimization problems. Given the hard nature of these problems, state-of-the-art algorithms rely on handcrafted heuristics for making decisions that are otherwise too expensive to compute or mathematically not well defined. Thus, machine learning looks like a natural candidate to make such decisions in a more principled and optimized way. We advocate for pushing further the integration of machine learning and combinatorial optimization and detail a methodology to do so. A main point of the paper is seeing generic optimization problems as data points and inquiring what is the relevant distribution of problems to use for learning on a given task.

Subfields: Artificial Intelligence, Computer Networks and Communications, Reinforcement Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Reinforcement Learning

Citations in the corpus

Structured Convolutional Kernel Networks for Airline Crew Scheduling (2021, neutral): “For an extensive literature review on using machine learning for combinatorial optimization, see Bengio et al. (2020).”
Predicting Tactical Solutions to Operational Planning Problems under Imperfect Information (2018, background): “The interested reader is referred to Bengio et al. (2018) for a very recent survey on all aspects of ML for discrete optimization.”
Learning Improvement Heuristics for Solving Routing Problems (2019, background): “…structures, and differ only in data which follows a distribution; 2) through supervised or reinforcement learning (RL), DL models can discover the underlying patterns of a given problem class, which could be used to generate alternative algorithms that are better than the human designed ones [11].”
Edge Artificial Intelligence for 6G: Vision, Enabling Technologies, and Applications (2021, background): “To address these challenges, “learning to optimize” provides a data-driven design paradigm to improve the computation efﬁciency and system performance for resource allocation [114], [259].”
Graph Neural Networks for Scalable Radio Resource Management: Architecture Design and Theoretical Analysis (2020, background): “There are two common paradigms on this topic [16], [17].”
Model-based reinforcement learning for biological sequence design (2020, neutral): “lems (Bello et al., 2016; Bengio et al., 2018; Dai et al., 2017; Kool et al., 2018).”
Flight-connection Prediction for Airline Crew Scheduling to Construct Initial Clusters for OR Optimizer (2019, methodology): “, in transportation, supply chain, energy, finance, and scheduling) [2].”
Combinatorial optimization and reasoning with graph neural networks (2021, background): “Hence, data-dependent algorithms or machine learning approaches, which may exploit these patterns, have recently gained traction in the CO ﬁeld [Bengio et al. , 2021; Kotary et al. , 2021].”
Exact Combinatorial Optimization with Graph Convolutional Neural Networks (2019, methodology): “A recent survey is provided by Bengio et al. [10].”
Solving Mixed Integer Programs Using Neural Networks (2020, background): “A survey of the topic is available by Bengio et al. (2018).”
Reinforcement Learning for Combinatorial Optimization: A Survey (2020, result): “While there are other surveys [Bengio et al. , 2018, Lombardi and Milano, 2018] that mention this particular topic, in this work we aim to deep-dive into RL methods that have demonstrated superior quality for popular CO problems.”
ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution (2024, positive): “Recent advances of NCO show promise in learning end-to-end solutions for COPs (Bengio et al., 2021; Yang & Whinston, 2023).”
Benchmarking Graph Neural Networks (2023, background): “Leveraging machine learning for solving NP-hard combinatorial optimization problems (COPs) has been the focus of intense research in recent years (Vinyals et al., 2015; Bengio et al., 2018).”
Rapid Task-Solving in Novel Environments (2020, background): “Learning to plan can be seen as a specific case of learning to solve combinatorial optimization problems, a notion that has been taken up by recent work (for review see Bengio et al., 2018).”
Graph Neural Networks with Learnable Structural and Positional Representations (2021, background): “, 2020), combinatorial optimization (Bengio et al., 2021; Cappart et al., 2021) and medical diagnosis (Li et al.”
POMO: Policy Optimization with Multiple Optima for Reinforcement Learning (2020, background): “Recent approaches in deep reinforcement learning (RL) have been promising [6], finding close-tooptimal solutions to the abstracted NP-hard CO problems such as traveling salesman (TSP) [7, 8, 9, 10,”