Machine learning for combinatorial optimization: A methodological tour d’horizon

2020/08/08 by Yoshua Bengio, Andrea Lodi, Antoine Prouvost · 84 citations
Computer Science · Engineering · #AI-based Problem Solving and Planning #Constraint Satisfaction and Optimization #Machine Learning and Algorithms #Metaheuristic Optimization Algorithms Research #Scheduling and Optimization Algorithms

paper · doi:10.1016/j.ejor.2020.07.063

openalex publication_date 2020/08/08 · openalex created_date 2022/08/02 · openalex updated_date 2026/07/28

Abstract

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.

Citations

• Computability of global solutions to factorable nonconvex programs: Part I — Convex underestimating problems
• Learning to Optimize Neural Nets
• Generative Adversarial Networks: An Overview
• Learning a SAT Solver from Single-Bit Supervision
• Deterministic Implementations for Reproducibility in Deep Reinforcement\n Learning
• Inverse Optimization
• Exact Combinatorial Optimization with Graph Convolutional Neural Networks

Cited by

• Recycling computational processes of dynamic programming for combinatorial optimization problems: a reservoir computing approach
• TSP with Predictions: Heatmap to Tour with Provable Guarantees
• Learning to Optimize at Scale: A Benders Decomposition-TransfORmers Framework for Stochastic Combinatorial Optimization
• HeatACO: A Heatmap-Guided Max--Min Ant System for Large-Scale Travelling Salesman Problems
• A Survey of Freshness-Aware Wireless Networking with Reinforcement Learning
• ARC: Leveraging Compositional Representations for Cross-Problem Learning on VRPs
• Descent-Net: Learning Descent Directions for Constrained Optimization
• A Fast Anti-Jamming Cognitive Radar Deployment Algorithm Based on Reinforcement Learning
• Learning-Based Hierarchical Approach for Fast Mixed-Integer Optimization
• Comparative algorithm performance evaluation and prediction for the maximum clique problem using instance space analysis
• End-to-end Deep Reinforcement Learning for Stochastic Multi-objective Optimization in C-VRPTW
• Neuro-Symbolic Constrained Optimization for Cloud Application Deployment via Graph Neural Networks and Satisfiability Modulo Theory
• A Fair OR-ML Framework for Resource Substitution in Large-Scale Networks
• When Words Change the Model: Sensitivity of LLMs for Constraint Programming Modelling
• Empirical Quantum Advantage in Constrained Optimization from Encoded Unitary Designs
• Graph-Based Imitation and Reinforcement Learning for Efficient Benders Decomposition
• Verification of Sequential Convex Programming for Parametric Non-convex Optimization
• Bridging Synthetic and Real Routing Problems via LLM-Guided Instance Generation and Progressive Adaptation
• An End-to-End Deep Reinforcement Learning Approach for Solving the Traveling Salesman Problem with Drones
• Finding Probably Approximate Optimal Solutions by Training to Estimate the Optimal Values of Subproblems
• An In-depth Study of LLM Contributions to the Bin Packing Problem
• Matrix Encoding Networks for Neural Combinatorial Optimization
• LLMs for Cold-Start Cutting Plane Separator Configuration
• A new perspective on classification: Optimally allocating limited resources to uncertain tasks
• Symbol-Equivariant Recurrent Reasoning Models
• Accelerated Discovery of Set Cover Solutions via Graph Neural Networks
• Probing Neural Combinatorial Optimization Models
• Demonstrating Real Advantage of Machine-Learning-Enhanced Monte Carlo for Combinatorial Optimization
• Solving Mixed Integer Programs Using Neural Networks
• A Markov Decision Process for Variable Selection in Branch & Bound
• Machine Learning on Graphs: A Model and Comprehensive Taxonomy
• Multi-Action Self-Improvement for Neural Combinatorial Optimization
• Refining Hybrid Genetic Search for CVRP via Reinforcement Learning-Finetuned LLM
• NeuroLKH: Combining Deep Learning Model with Lin-Kernighan-Helsgaun Heuristic for Solving the Traveling Salesman Problem
• Enhancing the Cross-Size Generalization for Solving Vehicle Routing Problems via Continual Learning
• A literature review of Artificial Intelligence applications in railway systems
• VRPAgent: LLM-Driven Discovery of Heuristic Operators for Vehicle Routing Problems
• A Denoising Diffusion-Based Evolutionary Algorithm Framework: Application to the Maximum Independent Set Problem
• POMO: Policy Optimization with Multiple Optima for Reinforcement Learning
• Test-Time Search in Neural Graph Coarsening Procedures for the Capacitated Vehicle Routing Problem
• Neural Graph Matching Network: Learning Lawler's Quadratic Assignment Problem with Extension to Hypergraph and Multiple-graph Matching
• Hybrid Quantum-Classical Optimisation of Traveling Salesperson Problem
• Bundle Network: a Machine Learning-Based Bundle Method
• Graph Optimization Foundation Model: Tokenizing Graph via A Language-Model Paradigm
• URS: A Unified Neural Routing Solver for Cross-Problem Zero-Shot Generalization
• On Learning Combinatorial Patterns to Assist Large-Scale Airline Crew Pairing Optimization
• Lifelong Learning with Behavior Consolidation for Vehicle Routing
• AutoPref: Automatic Discovery of Task-Specific Preference Objectives for Neural Combinatorial Optimization
• Sample Complexity of Tree Search Configuration: Cutting Planes and Beyond
• Hybridizing Machine Learning and Optimization for Planning Satellite Observations
• Learning Large Neighborhood Search Policy for Integer Programming
• Tackling GNARLy Problems: Graph Neural Algorithmic Reasoning Reimagined through Reinforcement Learning
• NeuFACO: Neural Focused Ant Colony Optimization for Traveling Salesman Problem
• Conditional Policy Generator for Dynamic Constraint Satisfaction and Optimization
• SeaPearl: A Constraint Programming Solver guided by Reinforcement\n Learning
• HyP-ASO: A Hybrid Policy-based Adaptive Search Optimization Framework for Large-Scale Integer Linear Programs
• ReviBranch: Deep Reinforcement Learning for Branch-and-Bound with Revived Trajectories
• Data from Discrete Flow-Based Generative Models for Measurement Optimization in Quantum Computing
• VEGA: Electric Vehicle Navigation Agent via Physics-Informed Neural Operator and Proximal Policy Optimization
• A Unified Learning-based Optimization Framework for 0-1 Mixed Problems in Wireless Networks
• Solution space of optimal heat pump schedules
• A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs
• Provably data-driven projection method for quadratic programming
• An Efficient Hybridization of Graph Representation Learning and Metaheuristics for the Constrained Incremental Graph Drawing Problem
• GTA -- An ATSP Method: Shifting the Bottleneck from Algorithm to RAM
• FORGE: Foundational Optimization Representations from Graph Embeddings
• A Deep Reinforcement Learning Algorithm Using Dynamic Attention Model for Vehicle Routing Problems
• Constraint Matters: Multi-Modal Representation for Reducing Mixed-Integer Linear programming
• Minimizing the Weighted Number of Tardy Jobs: Data-Driven Heuristic for Single-Machine Scheduling
• Ecole: A Library for Learning Inside MILP Solvers
• Nonlocal Monte Carlo via Reinforcement Learning
• Pinet: Optimizing hard-constrained neural networks with orthogonal projection layers
• Procedural Generation and Games at the Dawn of Fault Tolerant Quantum Computing
• Subgoal Search For Complex Reasoning Tasks
• Hybrid Node-Destroyer Model with Large Neighborhood Search for Solving the Capacitated Vehicle Routing Problem
• Edge-Selector Model Applied for Local Search Neighborhood for Solving Vehicle Routing Problems
• From Natural Language to Solver-Ready Power System Optimization: An LLM-Assisted, Validation-in-the-Loop Framework
• ParBalans: Parallel Multi-Armed Bandits-based Adaptive Large Neighborhood Search
• Learning to control inexact Benders decomposition via reinforcement learning
• Lifelong Learner: Discovering Versatile Neural Solvers for Vehicle Routing Problems
• Study of Robust Features in Formulating Guidance for Heuristic Algorithms for Solving the Vehicle Routing Problem
• On Distributional Dependent Performance of Classical and Neural Routing Solvers
• Unsupervised Learning for the Elementary Shortest Path Problem
• No AI Without PI! Object-Centric Process Mining as the Enabler for Generative, Predictive, and Prescriptive Artificial Intelligence
• Parametrized Multi-Agent Routing via Deep Attention Models
• Efficient Neural Combinatorial Optimization Solver for the Min-max Heterogeneous Capacitated Vehicle Routing Problem
• Accelerating Quadratic Optimization with Reinforcement Learning
• Learning Hard Optimization Problems: A Data Generation Perspective

Related

• Machine Learning for Combinatorial Optimization: a Methodological Tour\n d'Horizon
• The Machine Learning for Combinatorial Optimization Competition (ML4CO):\n Results and Insights
• End-to-End Constrained Optimization Learning: A Survey
• Reinforcement Learning for Combinatorial Optimization: A Survey
• Melding the Data-Decisions Pipeline: Decision-Focused Learning for Combinatorial Optimization