# The Differentiable Feasibility Pump

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 43 references that are in the map.
- First posted on arXiv 5 Nov 2024.

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

- [Estimating or Propagating Gradients Through Stochastic Neurons for Conditional Computation](https://mlsanity.com/paper/1308.3432/) (2013)
- [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)
- [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)
- [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)
- [Interior Point Solving for LP-based prediction+optimisation](https://mlsanity.com/paper/2010.13943/) (2020)
- [A Survey of Contextual Optimization Methods for Decision Making under Uncertainty](https://mlsanity.com/paper/2306.10374/) (2023)
- [SoftSort: A Continuous Relaxation for the argsort Operator](https://mlsanity.com/paper/2006.16038/) (2020)
- [PyEPO: A PyTorch-based End-to-End Predict-then-Optimize Library for Linear and Integer Programming](https://mlsanity.com/paper/2206.14234/) (2022)
- [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)
- [Continuous cutting plane algorithms in integer programming](https://mlsanity.com/paper/2204.09122/) (2022)
- [Differentiable Cutting-plane Layers for Mixed-integer Linear Optimization](https://mlsanity.com/paper/2311.03350/) (2023)
- [Penalty Alternating Direction Methods for Mixed-Integer Optimization: A New View on Feasibility Pumps](https://mlsanity.com/paper/1707.09891/) (2017)
- [Improving the Randomization Step in Feasibility Pump](https://mlsanity.com/paper/1609.08121/) (2016)

## Abstract (arXiv)

Although nearly 20 years have passed since its conception, the feasibility pump algorithm remains a widely used heuristic to find feasible primal solutions to mixed-integer linear problems. Many extensions of the initial algorithm have been proposed. Yet, its core algorithm remains centered around two key steps: solving the linear relaxation of the original problem to obtain a solution that respects the constraints, and rounding it to obtain an integer solution. This paper shows that the traditional feasibility pump and many of its follow-ups can be seen as gradient-descent algorithms with specific parameters. A central aspect of this reinterpretation is observing that the traditional algorithm differentiates the solution of the linear relaxation with respect to its cost. This reinterpretation opens many opportunities for improving the performance of the original algorithm. We study how to modify the gradient-update step as well as extending its loss function. We perform extensive experiments on MIPLIB instances and show that these modifications can substantially reduce the number of iterations needed to find a solution.