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.
Keywords
Computer scienceHeuristicsArtificial intelligenceMachine learningCombinatorial optimizationPoint (geometry)Task (project management)Optimization problemMathematical optimizationOnline machine learningActive learning (machine learning)MathematicsAlgorithm
Affiliated Institutions
Related Publications
An Analysis of Several Heuristics for the Traveling Salesman Problem
Several polynomial time algorithms finding “good,” but not necessarily optimal, tours for the traveling salesman problem are considered. We measure the closeness of a tour by th...
Analyzing bagging
Bagging is one of the most effective computationally intensive procedures to improve on unstable estimators or classifiers, useful especially for high dimensional data set probl...
APPLYING EVOLUTIONARY PROGRAMMING TO SELECTED TRAVELING SALESMAN PROBLEMS
Natural evolution provides a paradigm for the design of stochastic-search optimization algorithms. Various forms of simulated evolution, such as genetic algorithms and evolution...
Applications of Multi-Objective Evolutionary Algorithms
An Introduction to Multi-Objective Evolutionary Algorithms and Their Applications Optimal Design of Industrial Electromagnetic Devices: A Multiobjective Evolutionary Approach Us...
Online convex programming and generalized infinitesimal gradient ascent
Convex programming involves a convex set F ⊆ R n and a convex function c: F → R. The goal of convex programming is to find a point in F which minimizes c. In this paper, we intr...
Publication Info
- Year
- 2021
- Type
- article
- Citations
- 1184
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
1184
OpenAlex
Cite This
Yoshua Bengio,
Andrea Lodi,
Antoine Prouvost
(2021).
Machine learning for combinatorial optimization: A methodological tour d'horizon.
Archivio istituzionale della ricerca (Alma Mater Studiorum Università di Bologna)
.
https://doi.org/10.1016/j.ejor.2020.07.063
Identifiers
- DOI
- 10.1016/j.ejor.2020.07.063