Source-linked AI summary
Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon
Yoshua Bengio, Andrea Lodi, Antoine Prouvost
TL;DR
Combinatorial optimization uses difficult algorithmic decisions, often handled by expensive or handcrafted heuristics. This paper surveys how machine learning can approximate or learn those decisions and proposes viewing optimization problems as data points from relevant task distributions. Its synthesis argues that learned policies can augment combinatorial-optimization algorithms, with reward-based training potentially outperforming current policies given sufficient training and supervised initialization, while generalization remains challenging.
Problem
Combinatorial-optimization algorithms must make expensive or inadequately defined decisions, motivating machine-learning methods that can learn useful policies over relevant instance distributions.
Method
The paper surveys recent machine-learning and operations-research approaches and frames algorithmic decisions as policies in a state/action Markov decision process.
Results
Reward-based policies have the potential to outperform current policies given enough training and a supervised initialization, whereas imitation learning is valuable when its policy is significantly faster to compute than the expert’s.
Takeaways & Limitations
Learning should occur on a distribution small enough for the policy to fully exploit the problem structure and give better results.
Takeaways & Limitations
Learned policies may generalize poorly to unseen examples and task variations, and repeated decisions can become unstable because training data follow the expert policy.
Abstract
from arXiv · showhide
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.
1 Introduction
Combinatorial optimization problems are difficult, yet practical solvers exploit problem structure and expert-crafted algorithmic decisions. The paper surveys machine-learning approaches for augmenting such algorithms and emphasizes learning over relevant distributions of problem instances.
- Motivation: Combinatorial optimization problems are NP-hard, although practical algorithms can solve very large instances by exploiting problem structure.The paper focuses on discrete optimization with integral or binary decision variables.
- Motivation: Machine learning can replace expensive expert computations or learn algorithmic policies when existing decisions are unsatisfactory.The two roles are approximation of expert methods and exploration of better-performing decisions.
- Problem distributions: A target task is defined by the distribution of problem instances on which the algorithm should perform well, even when that distribution cannot be explicitly characterized.Historical instances provide a finite sample from the desired but unknown distribution.
- Motivation: Machine learning is presented as complementary to explicit operations-research expertise for exploiting structured combinatorial problems.The paper particularly highlights deep learning for addressing high-dimensional problem representations.
- Paper scope: The paper surveys recent approaches and presents a methodological overview aimed at automation and augmentation rather than mature algorithms.The surveyed literature is characterized as exploratory and intended to highlight promising research directions.
2 Preliminaries
The preliminaries introduce combinatorial optimization, mixed-integer linear programming, and the machine-learning concepts needed for the survey. They connect exact optimization mechanisms with supervised, reinforcement, and structured deep-learning methods, while emphasizing generalization and training limitations.
- Combinatorial optimization: Combinatorial optimization is formulated as constrained minimization, where variables encode decisions, constraints define feasibility, and the objective measures solution quality.The formulation covers linear programs and mixed-integer linear programs when some variables are restricted to integer values.
- Combinatorial optimization: MILP is NP-hard because integrality makes the feasible region nonconvex, while dropping integrality yields a polynomially solvable LP relaxation.LP and MILP are emphasized because they model many problems and have reliable algorithms and software tools.
- Combinatorial optimization: Branch-and-bound repeatedly solves LP relaxations, compares node bounds with the incumbent, and prunes subtrees that cannot improve the current solution.The figure depicts open nodes as blank and shows only part of the relaxation computations.
- Machine learning: Supervised learning fits functions from feature-target pairs, but evaluation on unseen data is required because performance on training examples alone does not establish generalization.Validation data supports model selection, while a separate test set estimates the selected model’s generalization error.
- Machine learning: Reinforcement learning trains an agent to maximize expected future rewards through state-dependent actions and transitions in a Markov decision process.Reward design can be difficult, and sparse rewards may provide no learning signal until the task is solved.
3 Recent approaches
The survey organizes machine learning for combinatorial optimization around learning decisions by imitation or experience, then combining learned policies with traditional optimization algorithms. It presents these approaches as exploratory templates spanning direct solution prediction, algorithm configuration, and repeated ML assistance during optimization.
- 3.1 Learning methods: The survey distinguishes approximation of expert decisions from discovery of new policies through trial-and-error learning.Imitation learning uses expert demonstrations, whereas reinforcement learning uses reward signals without an expert.
- 3.1 Learning methods: Both motivations are framed as policies mapping the optimization algorithm’s internal state to an action in a state/action MDP.The formulation also covers the bandit setting when the trajectory length is one.
- 3.1.1 Demonstration: Demonstration-based methods approximate computationally expensive expert decisions, including cutting-plane selection and strong branching in MILP.Examples use supervised learning to approximate SDP-based cut evaluation or strong branching, including graph neural networks on exhaustive MILP representations.
- 3.1.2 Experience: Demonstration and experience can be combined or treated as alternatives, including imitation of strong branching, reinforcement-learning discovery of branching policies, and dynamic switching among predefined policies.The survey emphasizes that these learning settings are not mutually exclusive.
- 3.2 Algorithmic structure: The surveyed integration templates treat machine learning and explicit optimization algorithms as building blocks arranged in three broad patterns.These include direct ML solution prediction, ML augmentation or configuration of an optimization algorithm, and repeated ML queries for lower-level decisions.
- 3.2.3 Machine learning alongside optimization algorithms: Repeated ML assistance can preserve exactness when approximate predictions select valid cutting planes that are then embedded in an exact algorithm.The learned model selects promising cuts, while every added cut remains guaranteed valid.
4 Learning objective
The paper formulates ML for combinatorial optimization as learning algorithm policies that minimize expected performance over a distribution of problem instances. It contrasts direct performance optimization with surrogate objectives and emphasizes generalization from finite training sets to unseen instances.
- 4.1 Multi-instance formulation: The learning objective treats optimization instances as samples from a probability distribution and seeks an algorithm minimizing expected performance over that distribution.The instance distribution reflects that some problems are more likely than others, but it is usually inaccessible and must be estimated empirically.
- 4.1 Multi-instance formulation: The algorithm space can be parameterized by ML models, such as neural-network weights defining a branching policy for branch-and-bound.This extends comparison from two fixed algorithms to learning over a potentially uncountable algorithm space.
- 4.1 Multi-instance formulation: The objective becomes difficult because performance measures are often nondifferentiable or lack closed forms, while expected performance is intractable to compute.Finite datasets provide empirical estimates but introduce generalization considerations.
- 4.1 Multi-instance formulation: Randomness from external factors or algorithm trajectories is incorporated by taking an inner expectation over a randomness source before averaging across instances.For repeated decisions, environmental dynamics can express this randomness along the trajectory.
- 4.2 Surrogate objectives: Imitation learning optimizes agreement with an expert policy rather than the original performance measure, so improved predictive accuracy does not necessarily imply improved optimization performance.The paper therefore stresses reporting the task performance metric, not only the surrogate or classification metric.
- 4.2 Surrogate objectives: Reinforcement learning directly optimizes the performance objective through experience, but sparse rewards may require surrogate signals that can induce unintended behavior.For branch-and-bound variable selection, rewards can discourage increases in opened nodes; when decomposition is unavailable, a delayed final reward is challenging.
- 4.3 On generalization: Generalization depends on the target instance distribution, ranging from a restricted application-specific set to broad real-world MILP instances.Broader distributions are harder to model and require more advanced and expensive learning algorithms.
- 4.3 On generalization: When policies generalize across instances, training can be performed offline, allowing computationally expensive learning to be decoupled from later solving.The resulting policy can be used out of the box for similar instances.
5 Methodology
The methodology distinguishes learning from demonstrations from learning through experience and examines how state representation and observability affect ML policies embedded in combinatorial optimization algorithms. It also highlights different constraints on exact and heuristic integration.
- 5.1 Demonstration and experience: Demonstration learning uses expert or oracle behavior, whereas experience learning uses trial and error with a reward signal.Expert demonstrations can be computationally costly, while experience directly optimizes a chosen reward.
- 5.1 Demonstration and experience: Imitation learning is bounded by the expert when the expert is not optimal and is useful mainly when the learned policy is significantly faster to compute.Its performance may also fail to generalize to unseen examples or small task variations because repeated decisions shift the state distribution.
- 5.1 Demonstration and experience: Reward-based learning can potentially outperform experts and handle multiple nearly equivalent decisions, but it requires substantially longer training.Approximate policies may converge to poor or poorly generalizing solutions when exploration is insufficient.
- 5.2 State representation and observability: Partial observability is common in real applications, but combinatorial optimization algorithms expose exact states whose representations can be exponentially large.This creates computational and generalization challenges even when the algorithmic state is mathematically available.
- 5.3 Exact and heuristic integration: ML components can be used in exact or heuristic frameworks, but exact algorithms must place learning at decisions that preserve advanced constraints.Examples include branching, node selection, heuristic scheduling, and cutting-plane selection within branch-and-bound.
6 Challenges
The paper identifies feasibility, generalization, data collection, representation, and architecture as central challenges in applying ML to combinatorial optimization. These challenges arise because optimization structure and guarantees must be preserved while policies learn from finite data.
- 6.1 Feasibility and guarantees: Directly learned heuristics provide no guarantee of optimality, and feasibility is not guaranteed either.The paper notes that the output may be far from optimal or may not satisfy the problem constraints.
- 6.1 Feasibility and guarantees: Neural architectures require careful design to output feasible structures such as permutations while maintaining differentiability for gradient-based training.Pointer networks and Sinkhorn layers are cited as complex mechanisms for producing permutations.
- 6.2 Architectures: Architectures effective for natural signals may not transfer directly to combinatorial optimization, whose policies must exploit different problem structure.The paper suggests that CO-specific architectures may differ from current deep-learning designs.
- 6.2 Architectures: Parameter sharing, recurrent networks, and graph neural networks provide tools for variable-length and graph-structured optimization data.Graph processing is especially relevant because many combinatorial optimization problems are represented on graphs.
- 6.3 Scaling and generalization: ML performance degrades when models trained on smaller TSPs are evaluated on substantially larger instances.The surveyed TSP studies report worsening generalization as test size increases beyond training sizes.
- 6.3 Data collection: Historical instances can support application-specific generalization, but proactively generating representative instances for unknown applications is difficult.The target family must first be defined, and generated problems must capture the essence of real instances.
- 6.4 Representation: Representations must be expressive enough for learning while remaining concise enough for frequent use without excessive computation.The paper gives branch-and-bound nodes and entire search trees as examples of difficult representation choices.
7 Conclusions
The paper concludes that ML can partially learn combinatorial optimization algorithms, with the appropriate strategy depending on computation, rewards, and the target instance distribution. It favors combining ML with existing optimization methods while recognizing that deployment remains exploratory.
- 7 Conclusions: Imitation learning is valuable when the learned policy computes substantially faster than the expert, while reward-trained policies may outperform existing policies given sufficient training and supervised initialization.The conclusion contrasts imitation’s efficiency requirement with experience-based learning’s greater upside.
- 7 Conclusions: The authors recommend learning on a distribution small enough for policies to exploit problem structure and improve results on that target scope.Generalization to unseen problems remains a challenge.
- 7 Conclusions: Combining ML with current combinatorial optimization algorithms can retain their theoretical guarantees and state-of-the-art algorithms.The paper presents this hybrid direction as an improvement over purely end-to-end ML approaches.
- 7 Conclusions: ML can also serve as a modeling tool for discrete optimization and as a means of extracting algorithmic intuition and knowledge.These uses extend beyond improving computational performance.
- 7 Conclusions: Most surveyed approaches remain exploratory in general-purpose commercial solvers, although the authors view the field as being at the beginning of a new era.The deployment qualification applies specifically to their use in general-purpose commercial solvers.