Source-linked AI summary
End-to-End Constrained Optimization Learning: A Survey
James Kotary, Ferdinando Fioretto, Pascal Van Hentenryck, Bryan Wilder
TL;DR
Constrained optimization is difficult to apply in repeated, real-time, and empirically dependent settings, motivating machine-learning integration. The survey reviews end-to-end approaches that combine learning with optimization, covering approximate solution prediction and solver-based structured inference. It reports promising results across several challenging tasks, while identifying limited problem coverage and computational costs as important boundaries.
Problem
CO complexity can limit adoption in repeated, real-time, or empirically data-dependent settings, while modern end-to-end CO learning lacks cohesive critical analysis.
Method
The survey conceptually reviews end-to-end methods integrating combinatorial solvers or optimization layers into machine-learning architectures.
Results
End-to-end approaches show promise on challenging tasks, including knapsack, bipartite matching, portfolio optimization, and handwritten-image sudoku solving.
Takeaways & Limitations
The surveyed methods support hybrid systems that predict fast approximate solutions or perform structured logical inference from empirical data.
Takeaways & Limitations
Reported success covers a relatively limited set of optimization problems, with most experiments focused on linear programming and training costs from solving hard problems each iteration.
Abstract
from arXiv · showhide
This paper surveys the recent attempts at leveraging machine learning to solve constrained optimization problems. It focuses on surveying the work on integrating combinatorial solvers and optimization methods with machine learning architectures. These approaches hold the promise to develop new hybrid machine learning and optimization methods to predict fast, approximate, solutions to combinatorial problems and to enable structural logical inference. This paper presents a conceptual review of the recent advancements in this emerging area.
1 Introduction
Constrained optimization supports many industrial and societal applications, but computational complexity limits its use in repeated, real-time, and empirically dependent settings. This motivates machine learning, especially end-to-end approaches that integrate learning with optimization.
- Constrained optimization is used in transportation, supply chains, energy, scheduling, and critical-resource allocation.
- Despite strong algorithms, CO complexity can restrict adoption for repeated, real-time, or empirically dependent problem instances.
- Machine learning has emerged as a natural candidate for aiding constrained-optimization decisions.
- Research at the CO–ML intersection divides into ML-augmented CO and end-to-end CO learning.
- The survey addresses the lack of cohesive critical analysis of modern end-to-end CO learning and identifies open questions and directions.
2 Preliminaries: Constrained Optimization
Constrained optimization minimizes an objective subject to constraints, with feasible and optimal solutions defined by those constraints and objective values. Convex problems are tractable, whereas integrality makes mixed-integer problems generally NP-hard and requires search-based methods such as branch and bound.
- A constrained optimization problem minimizes an objective function over variables satisfying a constraint set.
- A feasible solution satisfies all constraints, while an optimal solution has no worse objective value than any feasible alternative.
- Convex problems combine a convex objective and constraint set and are efficiently solvable with strong guarantees on solution existence and uniqueness.
- Linear programs use affine objectives, quadratic programs use quadratic objectives, and mixed-integer programs require some variables to be integral.
- The survey primarily considers linear constraints with linear or quadratic objectives and continuous, integral, or mixed variables.
- Branch and bound solves MILPs by repeatedly solving LP relaxations in a search tree and using their objective values as lower bounds.
3 Preliminaries: Deep Learning
Deep learning approximates mappings from data using neural architectures, including recurrent, sequence-to-sequence, attention, pointer, and graph neural networks. These models support structured inputs and outputs but face limitations such as vanishing gradients and fixed-length sequence representations.
- Supervised deep learning approximates a nonlinear mapping from inputs to targets using layered neural networks.
- Feed-forward neural networks connect fully connected layers through learned weights, biases, and typically nonlinear activations such as ReLU.
- Sequence Models: Recurrent neural networks generate output sequences while each hidden state depends on the current input and previous hidden state.
- Sequence Models: Basic RNNs can suffer vanishing gradients, while gated recurrent architectures such as LSTMs better preserve information across layers.
- Sequence Models: Sequence-to-sequence models use encoder–decoder LSTMs to map variable-size input sequences into variable-size output sequences through a context vector.
- Attention and Pointer Networks: Attention improves expressivity by allowing each decoder step to use an adaptive combination of encoder states rather than one fixed context vector.
- Attention and Pointer Networks: Pointer networks use attention vectors directly as predictions when the output is a permutation of the input.
- Graph Neural Networks: Graph neural networks learn node embeddings from node, edge, and neighboring-node information for downstream prediction tasks.
4 Overview of ML and CO
The CO–ML field divides into ML-augmented solvers and end-to-end CO learning. This survey focuses on end-to-end methods that predict solutions from data, either approximately for predefined problems or through optimization layers for structured inference.
- ML-augmented CO uses machine learning to aid decisions within optimization solvers, whereas end-to-end CO learning integrates optimization methods into learning architectures.
- End-to-end CO learning targets data-driven prediction of constrained-optimization solutions.
- The survey groups end-to-end methods into fast approximate prediction for predefined CO problems and solver-based structured logical inference.
5 ML-augmented CO
ML-augmented constrained optimization uses machine learning to improve decisions within established solvers, including branch-and-bound guidance and continuous optimization controls.
- ML-augmented CO augments existing solvers with ML inference models for more efficient continuous and discrete combinatorial optimization.
- Combinatorial optimization: Branch-and-bound methods learn branching decisions or guide primal heuristics, including emulating expensive branching rules and selecting variable-scoring combinations.
- Continuous optimization: ML also improves continuous CO through learned restart strategies, variable omission, and active-constraint selection.
6 E2E-COL: Predicting CO Solutions
End-to-end CO learning predicts fast approximate solutions, either by incorporating constraints or by learning combinatorial structures on graphs. The survey reviews supervised and reinforcement-learning approaches, including pointer networks, graph models, and policy-gradient methods.
- End-to-end CO learning predicts fast approximate solutions without using CO solvers at inference, and divides methods into learning with constraints and learning CO solutions on graphs.
- Supervised learning: Supervised approaches require target solutions, which can be problematic because generating them typically entails solving NP-hard problems.
- Supervised learning: Pointer networks predict approximately optimal permutations for variable-sized inputs, including TSP, Delaunay triangulation, and convex hull variants.For Euclidean TSP, the permutation represents a tour and labels are precomputed minimum-length tours.
- Supervised learning: Pointer-network supervised learning applies only when solutions are single permutations and all permutations are feasible.
- Reinforcement learning: Reinforcement-learning methods optimize objectives directly using actor-critic or greedy graph policies, with REINFORCE gradients and critic-based baselines.The critic is trained to predict expected tour length from empirically observed tours generated by the current policy.
- Learning CO solutions: Graph-based architectures include RNN-free problem representations, graph neural networks, and graph attention networks for combinatorial solution learning.Kool et al. reported improved 2D Euclidean TSP accuracy over several earlier approaches.
- Learning with constraints: Hierarchical reinforcement learning can bias lower-level policies toward feasible solutions while higher levels optimize the objective.
- Predict-and-optimize: Predict-and-optimize frameworks differentiate solver outputs with respect to problem parameters to improve empirical model performance.
7 E2E-COL: Predict-and-Optimize
End-to-end constrained optimization integrates predictive models with optimization layers so predictions are trained for downstream decisions. The surveyed methods address differentiation through discrete or linear optimization and report promising results across several tasks.
- Framework: Integrated models combine machine learning with partially specified optimization problems whose parameters are predicted from empirical data.The resulting systems are trained around the quality of their optimization decisions rather than only parameter-prediction accuracy.
- Framework: Regret-based training evaluates the objective gap between decisions produced from predicted parameters and decisions produced from target parameters.Regret can sometimes be minimized without ground-truth solutions because the target objective term is constant with respect to the prediction.
- Linear Programming: Differentiable optimization layers obtain gradients through solver computations, including KKT differentiation for quadratic programs and regularized approximations for linear programs.Regularization gives linear-program approximations unique solutions that vary smoothly with their parameters, enabling backpropagation.
- Linear Programming: Wilder et al.'s integrated model minimized expected optimal objective value without target data and outperformed two-stage models on knapsack and bipartite matching tasks.The reported tasks predicted cost vectors from empirical data while keeping constraints fixed across samples.
- Combinatorial Optimization: SPO-relax used continuous relaxations or other weaker oracles for NP-hard combinatorial problems, achieving competitive accuracy with shorter training times on several discrete tasks.Its comparison with Wilder et al.'s formulation on equivalent relaxations produced no clear winner.
- Combinatorial Optimization: Black-box differentiation approximated discrete solver outputs using two solver calls, while semidefinite-program relaxations enabled differentiable MAXSAT integration for handwritten-image sudoku.Reported applications included shortest path, TSP, min-cost perfect matching, and sudoku.
8 Challenges and Research Directions
The surveyed integration of combinatorial optimization and machine learning shows promise, but remains limited in breadth, runtime, and architectural generality. The authors identify constraint parametrization and solver-in-the-loop costs as central barriers to broader use.
- Scope: Reported success covers a relatively limited set of optimization problems, with most experiments focusing on linear-programming formulations.The survey identifies constraint parametrization as an unresolved obstacle to broader applications.
- Efficiency: Runtime costs of combinatorial solvers inside training loops can still make potential applications impractical.This concern is especially relevant when hard optimization problems must be solved repeatedly during training.
- Architecture: The role of the in-loop optimization model has not yet been generalized successfully beyond its use as the final layer of a deep model.The authors note that additional layers beyond the solver remain an open direction.
- Outlook: Although the approaches are at an early developmental stage and mainly academic, the authors regard their integration as a promising direction for new tools.The paper frames this promise as applying to both combinatorial optimization and learning.