# Differentiating Through Integer Linear Programs with Quadratic Regularization and Davis-Yin Splitting

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 58 references that are in the map.
- First posted on arXiv 31 Jan 2023.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Deep Equilibrium Models](https://mlsanity.com/paper/1909.01377/) (2019)
- [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)
- [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)
- [Learning to Optimize: A Primer and A Benchmark](https://mlsanity.com/paper/2103.12828/) (2021)
- [Efficient and Modular Implicit Differentiation](https://mlsanity.com/paper/2105.15183/) (2021)
- [Learning to Optimize](https://mlsanity.com/paper/1606.01885/) (2016)
- [End-to-End Constrained Optimization Learning: A Survey](https://mlsanity.com/paper/2103.16378/) (2021)
- [Deep Equilibrium Architectures for Inverse Problems in Imaging](https://mlsanity.com/paper/2102.07944/) (2021)
- [Implicit Deep Learning](https://mlsanity.com/paper/1908.06315/) (2019)
- [MIPaaL: Mixed Integer Program as a Layer](https://mlsanity.com/paper/1907.05912/) (2019)
- [JFB: Jacobian-Free Backpropagation for Implicit Networks](https://mlsanity.com/paper/2103.12803/) (2021)
- [Theoretical Linear Convergence of Unfolded ISTA and its Practical Weights and Thresholds](https://mlsanity.com/paper/1808.10038/) (2018)
- [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)
- [On Training Implicit Models](https://mlsanity.com/paper/2111.05177/) (2021)
- [Differentiating Through a Cone Program](https://mlsanity.com/paper/1904.09043/) (2019)
- [Reviving and Improving Recurrent Back-Propagation](https://mlsanity.com/paper/1803.06396/) (2018)
- [Nonsmooth Implicit Differentiation for Machine Learning and Optimization](https://mlsanity.com/paper/2106.04350/) (2021)
- [A Three-Operator Splitting Scheme and its Optimization Applications](https://mlsanity.com/paper/1504.01032/) (2015)
- [Enforcing Policy Feasibility Constraints through Differentiable Projection for Energy Optimization](https://mlsanity.com/paper/2105.08881/) (2021)
- [Backpropagation through Combinatorial Algorithms: Identity with Projection Works](https://mlsanity.com/paper/2205.15213/) (2022)
- [Learning with Combinatorial Optimization Layers: a Probabilistic Approach](https://mlsanity.com/paper/2207.13513/) (2022)
- [Online Deep Equilibrium Learning for Regularization by Denoising](https://mlsanity.com/paper/2205.13051/) (2022)
- [Explainable AI via Learning to Optimize](https://mlsanity.com/paper/2204.14174/) (2022)
- [From the simplex to the sphere: Faster constrained optimization using the Hadamard parametrization](https://mlsanity.com/paper/2112.05273/) (2021)

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

- [On Logical Extrapolation for Mazes with Recurrent and Implicit Networks](https://mlsanity.com/paper/2410.03020/) (2024)
- [A Generalization Bound for a Family of Implicit Networks](https://mlsanity.com/paper/2410.07427/) (2024)
- [End-to-End Training of High-Dimensional Optimal Control with Implicit Hamiltonians via Jacobian-Free Backpropagation](https://mlsanity.com/paper/2510.00359/) (2025)
- [Learning with Local Search MCMC Layers](https://mlsanity.com/paper/2505.14240/) (2025)
- [Minimizing Surrogate Losses for Decision-Focused Learning using Differentiable Optimization](https://mlsanity.com/paper/2508.11365/) (2025)
- [On the Convergence of Jacobian-Free Backpropagation for Optimal Control Problems with Implicit Hamiltonians](https://mlsanity.com/paper/2602.00921/) (2026)
- [Scalable Decision-Focused Learning through Cost-Sensitive Regression](https://mlsanity.com/paper/2605.18005/) (2026)
- [DisjunctiveNet: Neural Symbolic Learning via Differentiable Convexified Optimization Layers](https://mlsanity.com/paper/2605.30456/) (2026)
- [Regularized Large Neighborhood Search](https://mlsanity.com/paper/2606.02294/) (2026)
- [End-to-End Learning of Safe Optimal Feedback Control in High Dimensions with Control Barrier Function Layers](https://mlsanity.com/paper/2607.20674/) (2026)
- [Decision-Driven Regularization: A Blended Model for Learning and Optimization](https://mlsanity.com/paper/2608.15124/) (2026)

## Abstract (arXiv)

In many applications, a combinatorial problem must be repeatedly solved with similar, but distinct parameters. Yet, the parameters w are not directly observed; only contextual data d that correlates with w is available. It is tempting to use a neural network to predict w given d. However, training such a model requires reconciling the discrete nature of combinatorial optimization with the gradient-based frameworks used to train neural networks. We study the case where the problem in question is an Integer Linear Program (ILP). We propose applying a three-operator splitting technique, also known as Davis-Yin splitting (DYS), to the quadratically regularized continuous relaxation of the ILP. We prove that the resulting scheme is compatible with the recently introduced Jacobian-free backpropagation (JFB). Our experiments on two representative ILPs: the shortest path problem and the knapsack problem, demonstrate that this combination-DYS on the forward pass, JFB on the backward pass-yields a scheme which scales more effectively to high-dimensional problems than existing schemes. All code associated with this paper is available at github.com/mines-opt-ml/fpo-dys.