# Learning with Combinatorial Optimization Layers: a Probabilistic Approach

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

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 52 references that are in the map.
- First posted on arXiv 27 Jul 2022.

## Builds on (most cited first, 29 of 29)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Automatic differentiation in machine learning: a survey](https://mlsanity.com/paper/1502.05767/) (2015)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (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)
- [From Softmax to Sparsemax: A Sparse Model of Attention and Multi-Label Classification](https://mlsanity.com/paper/1602.02068/) (2016)
- [Smart "Predict, then Optimize"](https://mlsanity.com/paper/1710.08005/) (2017)
- [Melding the Data-Decisions Pipeline: Decision-Focused Learning for Combinatorial Optimization](https://mlsanity.com/paper/1809.05504/) (2018)
- [Differentiation of Blackbox Combinatorial Solvers](https://mlsanity.com/paper/1912.02175/) (2019)
- [Fast Differentiable Sorting and Ranking](https://mlsanity.com/paper/2002.08871/) (2020)
- [End-to-End Constrained Optimization Learning: A Survey](https://mlsanity.com/paper/2103.16378/) (2021)
- [Learning with Fenchel-Young Losses](https://mlsanity.com/paper/1901.02324/) (2019)
- [Implicit MLE: Backpropagating Through Discrete Exponential Family Distributions](https://mlsanity.com/paper/2106.01798/) (2021)
- [MIPaaL: Mixed Integer Program as a Layer](https://mlsanity.com/paper/1907.05912/) (2019)
- [Smart Predict-and-Optimize for Hard Combinatorial Optimization Problems](https://mlsanity.com/paper/1911.10092/) (2019)
- [Interior Point Solving for LP-based prediction+optimisation](https://mlsanity.com/paper/2010.13943/) (2020)
- [Learning with Differentiable Perturbed Optimizers](https://mlsanity.com/paper/2002.08676/) (2020)
- [Theseus: A Library for Differentiable Nonlinear Optimization](https://mlsanity.com/paper/2207.09442/) (2022)
- [SparseMAP: Differentiable Sparse Structured Inference](https://mlsanity.com/paper/1802.04223/) (2018)
- [Decision-Focused Learning: Through the Lens of Learning to Rank](https://mlsanity.com/paper/2112.03609/) (2021)
- [Contrastive Losses and Solution Caching for Predict-and-Optimize](https://mlsanity.com/paper/2011.05354/) (2020)
- [CombOptNet: Fit the Right NP-Hard Problem by Learning Integer Programming Constraints](https://mlsanity.com/paper/2105.02343/) (2021)
- [PyEPO: A PyTorch-based End-to-End Predict-then-Optimize Library for Linear and Integer Programming](https://mlsanity.com/paper/2206.14234/) (2022)
- [Flexible Differentiable Optimization via Model Transformations](https://mlsanity.com/paper/2206.06135/) (2022)
- [FrankWolfe.jl: a high-performance and flexible toolbox for Frank-Wolfe algorithms and Conditional Gradients](https://mlsanity.com/paper/2104.06675/) (2021)
- [Learning to solve the single machine scheduling problem with release times and sum of completion times](https://mlsanity.com/paper/2101.01082/) (2021)
- [Algorithms for Non-Linear and Stochastic Resource Constrained Shortest Paths](https://mlsanity.com/paper/1504.07880/) (2015)

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

- [Decision-Focused Learning: Foundations, State of the Art, Benchmark and Future Opportunities](https://mlsanity.com/paper/2307.13565/) (2023)
- [A Survey of Contextual Optimization Methods for Decision Making under Uncertainty](https://mlsanity.com/paper/2306.10374/) (2023)
- [Learning-based Online Optimization for Autonomous Mobility-on-Demand Fleet Control](https://mlsanity.com/paper/2302.03963/) (2023)
- [Differentiating Through Integer Linear Programs with Quadratic Regularization and Davis-Yin Splitting](https://mlsanity.com/paper/2301.13395/) (2023)
- [Combinatorial Optimization enriched Machine Learning to solve the Dynamic Vehicle Routing Problem with Time Windows](https://mlsanity.com/paper/2304.00789/) (2023)
- [CaVE: A Cone-Aligned Approach for Fast Predict-then-optimize with Binary Linear Programs](https://mlsanity.com/paper/2312.07718/) (2023)
- [Differentiable Distributionally Robust Optimization Layers](https://mlsanity.com/paper/2406.16571/) (2024)
- [Explainable Data-Driven Optimization: From Context to Decision and Back Again](https://mlsanity.com/paper/2301.10074/) (2023)
- [Structured Reinforcement Learning for Combinatorial Decision-Making](https://mlsanity.com/paper/2505.19053/) (2025)
- [LPGD: A General Framework for Backpropagation through Embedded Optimization Layers](https://mlsanity.com/paper/2407.05920/) (2024)
- [Feasibility-Aware Decision-Focused Learning for Predicting Parameters in the Constraints](https://mlsanity.com/paper/2510.04951/) (2025)
- [Primal-dual algorithm for contextual stochastic combinatorial optimization](https://mlsanity.com/paper/2505.04757/) (2025)
- [Differentiable Cutting-plane Layers for Mixed-integer Linear Optimization](https://mlsanity.com/paper/2311.03350/) (2023)
- [Generalization Bounds of Surrogate Policies for Combinatorial Optimization Problems](https://mlsanity.com/paper/2407.17200/) (2024)
- [WardropNet: Traffic Flow Predictions via Equilibrium-Augmented Learning](https://mlsanity.com/paper/2410.06656/) (2024)
- [Combinatorial Optimization Augmented Machine Learning](https://mlsanity.com/paper/2601.10583/) (2026)
- [DFWLayer: Differentiable Frank-Wolfe Optimization Layer](https://mlsanity.com/paper/2308.10806/) (2023)
- [Everybody Needs a Little HELP: Explaining Graphs via Hierarchical Concepts](https://mlsanity.com/paper/2311.15112/) (2023)
- [Learning predictive checklists from continuous medical data](https://mlsanity.com/paper/2211.07076/) (2022)
- [DistrictNet: Decision-aware learning for geographical districting](https://mlsanity.com/paper/2412.08287/) (2024)
- [DFF: Decision-Focused Fine-tuning for Smarter Predict-then-Optimize with Limited Data](https://mlsanity.com/paper/2501.01874/) (2025)
- [Optimization-Augmented Machine Learning for Vehicle Operations in Emergency Medical Services](https://mlsanity.com/paper/2503.11848/) (2025)
- [Predicting Accurate Lagrangian Multipliers for Mixed Integer Linear Programs](https://mlsanity.com/paper/2310.14659/) (2023)
- [CF-OPT: Counterfactual Explanations for Structured Prediction](https://mlsanity.com/paper/2405.18293/) (2024)
- [The Differentiable Feasibility Pump](https://mlsanity.com/paper/2411.03535/) (2024)
- [Going from a Representative Agent to Counterfactuals in Combinatorial Choice](https://mlsanity.com/paper/2505.23546/) (2025)
- [Managing Solution Stability in Decision-Focused Learning with Cost Regularization](https://mlsanity.com/paper/2601.21883/) (2026)
- [Regularized Large Neighborhood Search](https://mlsanity.com/paper/2606.02294/) (2026)
- [FedRSPO+: A Heterogeneity-aware Algorithm for Decision-focused Federated Learning](https://mlsanity.com/paper/2610.09091/) (2026)

## Abstract (arXiv)

Combinatorial optimization (CO) layers in machine learning (ML) pipelines are a powerful tool to tackle data-driven decision tasks, but they come with two main challenges. First, the solution of a CO problem often behaves as a piecewise constant function of its objective parameters. Given that ML pipelines are typically trained using stochastic gradient descent, the absence of slope information is very detrimental. Second, standard ML losses do not work well in combinatorial settings. A growing body of research addresses these challenges through diverse methods. Unfortunately, the lack of well-maintained implementations slows down the adoption of CO layers. In this paper, building upon previous works, we introduce a probabilistic perspective on CO layers, which lends itself naturally to approximate differentiation and the construction of structured losses. We recover many approaches from the literature as special cases, and we also derive new ones. Based on this unifying perspective, we present InferOpt.jl, an open-source Julia package that 1) allows turning any CO oracle with a linear objective into a differentiable layer, and 2) defines adequate losses to train pipelines containing such layers. Our library works with arbitrary optimization algorithms, and it is fully compatible with Julia's ML ecosystem. We demonstrate its abilities using a pathfinding problem on video game maps as guiding example, as well as three other applications from operations research.