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

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

2020 | Yoshua Bengio, Andrea Lodi, Antoine Prouvost
This paper surveys recent efforts from both machine learning and operations research communities to apply machine learning to solve combinatorial optimization (CO) problems. CO problems are typically hard to solve, requiring handcrafted heuristics for decision-making due to computational and mathematical challenges. Machine learning is seen as a promising approach to make these decisions more principled and efficient. The paper advocates for integrating machine learning with CO and proposes a methodology for doing so. A key idea is treating generic optimization problems as data points and determining the relevant distribution of problems for learning on a specific task. The paper discusses the challenges of solving NP-hard problems like the Traveling Salesman Problem (TSP) in practice, highlighting how problem-specific structures can be leveraged for efficient solutions. It also notes that traditional CO algorithms may not perform consistently across all problem instances but are often adapted to specific structures, such as Euclidean TSPs. Machine learning can complement these approaches by automating and augmenting expert intuition, especially for highly structured problems. The paper outlines two main motivations for using machine learning in CO: (1) approximating decisions through imitation learning, where expert demonstrations are used to train models, and (2) discovering new policies through reinforcement learning, where algorithms learn from experience. It also discusses the integration of machine learning with traditional CO algorithms, showing how learned policies can be combined with existing methods. Examples include using neural networks to approximate cutting planes in MILP problems and learning branching strategies in B&B trees. The paper also explores different ways to apply machine learning in CO, such as end-to-end learning, where ML models directly output solutions, and algorithm configuration, where ML is used to optimize algorithm parameters. It highlights the importance of generalization in ML, noting that models trained on a finite set of problem instances may not perform well on unseen instances. The paper concludes that while ML can be approximate, it does not necessarily compromise theoretical guarantees and can significantly improve CO algorithms by leveraging their structured nature.This paper surveys recent efforts from both machine learning and operations research communities to apply machine learning to solve combinatorial optimization (CO) problems. CO problems are typically hard to solve, requiring handcrafted heuristics for decision-making due to computational and mathematical challenges. Machine learning is seen as a promising approach to make these decisions more principled and efficient. The paper advocates for integrating machine learning with CO and proposes a methodology for doing so. A key idea is treating generic optimization problems as data points and determining the relevant distribution of problems for learning on a specific task. The paper discusses the challenges of solving NP-hard problems like the Traveling Salesman Problem (TSP) in practice, highlighting how problem-specific structures can be leveraged for efficient solutions. It also notes that traditional CO algorithms may not perform consistently across all problem instances but are often adapted to specific structures, such as Euclidean TSPs. Machine learning can complement these approaches by automating and augmenting expert intuition, especially for highly structured problems. The paper outlines two main motivations for using machine learning in CO: (1) approximating decisions through imitation learning, where expert demonstrations are used to train models, and (2) discovering new policies through reinforcement learning, where algorithms learn from experience. It also discusses the integration of machine learning with traditional CO algorithms, showing how learned policies can be combined with existing methods. Examples include using neural networks to approximate cutting planes in MILP problems and learning branching strategies in B&B trees. The paper also explores different ways to apply machine learning in CO, such as end-to-end learning, where ML models directly output solutions, and algorithm configuration, where ML is used to optimize algorithm parameters. It highlights the importance of generalization in ML, noting that models trained on a finite set of problem instances may not perform well on unseen instances. The paper concludes that while ML can be approximate, it does not necessarily compromise theoretical guarantees and can significantly improve CO algorithms by leveraging their structured nature.
Reach us at info@study.space