# Combinatorial Optimization Augmented Machine Learning

arXiv: https://arxiv.org/abs/2601.10583 · HTML: https://mlsanity.com/paper/2601.10583/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Placed in RL for games and combinatorial optimization, one of 15 directions in Deep reinforcement learning methods.
- Builds on 38 of its 57 references that are in the map.
- First posted on arXiv 15 Jan 2026.

## Placed in

- Deep reinforcement learning methods / [RL for games and combinatorial optimization](https://mlsanity.com/deeprl/rl-for-games-and-combinatorial-optimization/)

## Builds on (most cited first, 30 of 38)

- [QT-Opt: Scalable Deep Reinforcement Learning for Vision-Based Robotic Manipulation](https://mlsanity.com/paper/1806.10293/) (2018)
- [OptNet: Differentiable Optimization as a Layer in Neural Networks](https://mlsanity.com/paper/1703.00443/) (2017)
- [Differentiable Convex Optimization Layers](https://mlsanity.com/paper/1910.12430/) (2019)
- [Smart "Predict, then Optimize"](https://mlsanity.com/paper/1710.08005/) (2017)
- [A Lyapunov-based Approach to Safe Reinforcement Learning](https://mlsanity.com/paper/1805.07708/) (2018)
- [Differentiation of Blackbox Combinatorial Solvers](https://mlsanity.com/paper/1912.02175/) (2019)
- [Deep Reinforcement Learning in Large Discrete Action Spaces](https://mlsanity.com/paper/1512.07679/) (2015)
- [End-to-End Constrained Optimization Learning: A Survey](https://mlsanity.com/paper/2103.16378/) (2021)
- [Decision-Focused Learning: Foundations, State of the Art, Benchmark and Future Opportunities](https://mlsanity.com/paper/2307.13565/) (2023)
- [Learning with Fenchel-Young Losses](https://mlsanity.com/paper/1901.02324/) (2019)
- [A Survey of Contextual Optimization Methods for Decision Making under Uncertainty](https://mlsanity.com/paper/2306.10374/) (2023)
- [Learning with Differentiable Perturbed Optimizers](https://mlsanity.com/paper/2002.08676/) (2020)
- [Reinforcement Learning with Combinatorial Actions: An Application to Vehicle Routing](https://mlsanity.com/paper/2010.12001/) (2020)
- [Differentiable Dynamic Programming for Structured Prediction and Attention](https://mlsanity.com/paper/1802.03676/) (2018)
- [End to end learning and optimization on graphs](https://mlsanity.com/paper/1905.13732/) (2019)
- [The Elements of Differentiable Programming](https://mlsanity.com/paper/2403.14606/) (2024)
- [Learning with Combinatorial Optimization Layers: a Probabilistic Approach](https://mlsanity.com/paper/2207.13513/) (2022)
- [Learning Permutations with Sinkhorn Policy Gradient](https://mlsanity.com/paper/1805.07010/) (2018)
- [CAQL: Continuous Action Q-Learning](https://mlsanity.com/paper/1909.12397/) (2019)
- [End-to-End Stochastic Optimization with Energy-Based Model](https://mlsanity.com/paper/2211.13837/) (2022)
- [Hybrid Multi-agent Deep Reinforcement Learning for Autonomous Mobility on Demand Systems](https://mlsanity.com/paper/2212.07313/) (2022)
- [Learning-based Online Optimization for Autonomous Mobility-on-Demand Fleet Control](https://mlsanity.com/paper/2302.03963/) (2023)
- [A learning-based algorithm to quickly compute good primal solutions for Stochastic Integer Programs](https://mlsanity.com/paper/1912.08112/) (2019)
- [Reinforcement Learning Driven Heuristic Optimization](https://mlsanity.com/paper/1906.06639/) (2019)
- [Combinatorial Optimization enriched Machine Learning to solve the Dynamic Vehicle Routing Problem with Time Windows](https://mlsanity.com/paper/2304.00789/) (2023)
- [Global Rewards in Multi-Agent Deep Reinforcement Learning for Autonomous Mobility on Demand Systems](https://mlsanity.com/paper/2312.08884/) (2023)
- [Structured Reinforcement Learning for Combinatorial Decision-Making](https://mlsanity.com/paper/2505.19053/) (2025)
- [Learning structured approximations of combinatorial optimization problems](https://mlsanity.com/paper/2107.04323/) (2021)
- [Learning to Handle Parameter Perturbations in Combinatorial Optimization: an Application to Facility Location](https://mlsanity.com/paper/1907.05765/) (2019)
- [Combinatorial Optimization and Machine Learning for Dynamic Inventory Routing](https://mlsanity.com/paper/2402.04463/) (2024)

## Built on by (most cited first, 3 of 3)

- [Latent Spherical Flow Policy for Reinforcement Learning with Combinatorial Actions](https://mlsanity.com/paper/2601.22211/) (2026)
- [Regularized Large Neighborhood Search](https://mlsanity.com/paper/2606.02294/) (2026)
- [Neural Certificate Pricing for Combinatorial Optimization Problems](https://mlsanity.com/paper/2607.01185/) (2026)

## Abstract (arXiv)

Combinatorial optimization augmented machine learning (COAML) has recently emerged as a powerful paradigm for integrating predictive models with combinatorial decision-making. By embedding combinatorial optimization oracles into learning pipelines, COAML enables the construction of policies that are both data-driven and feasibility-preserving, bridging the traditions of machine learning, operations research, and stochastic optimization. This paper provides a comprehensive overview of the state of the art in COAML. We introduce a unifying framework for COAML pipelines, describe their methodological building blocks, and formalize their connection to empirical cost minimization. We then develop a taxonomy of problem settings based on the form of uncertainty and decision structure. Using this taxonomy, we review algorithmic approaches for static and dynamic problems, survey applications across domains such as scheduling, vehicle routing, stochastic programming, and reinforcement learning, and synthesize methodological contributions in terms of empirical cost minimization, imitation learning, and reinforcement learning. Finally, we identify key research frontiers. This survey aims to serve both as a tutorial introduction to the field and as a roadmap for future research at the interface of combinatorial optimization and machine learning.