# Differentiation of Blackbox Combinatorial Solvers

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

## Key facts

- Cited by 226 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Dec 2019.

## Built on by (most cited first, 30 of 226)

- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [End-to-End Constrained Optimization Learning: A Survey](https://mlsanity.com/paper/2103.16378/) (2021)
- [The Diffusion Duality](https://mlsanity.com/paper/2506.10892/) (2025)
- [Decision-Focused Learning: Foundations, State of the Art, Benchmark and Future Opportunities](https://mlsanity.com/paper/2307.13565/) (2023)
- [Semantic Probabilistic Layers for Neuro-Symbolic Learning](https://mlsanity.com/paper/2206.00426/) (2022)
- [Implicit MLE: Backpropagating Through Discrete Exponential Family Distributions](https://mlsanity.com/paper/2106.01798/) (2021)
- [A Survey of Contextual Optimization Methods for Decision Making under Uncertainty](https://mlsanity.com/paper/2306.10374/) (2023)
- [On Training Implicit Models](https://mlsanity.com/paper/2111.05177/) (2021)
- [RL4CO: an Extensive Reinforcement Learning for Combinatorial Optimization Benchmark](https://mlsanity.com/paper/2306.17100/) (2023)
- [GrooMeD-NMS: Grouped Mathematically Differentiable NMS for Monocular 3D Object Detection](https://mlsanity.com/paper/2103.17202/) (2021)
- [Theseus: A Library for Differentiable Nonlinear Optimization](https://mlsanity.com/paper/2207.09442/) (2022)
- [Decision-Focused Learning: Through the Lens of Learning to Rank](https://mlsanity.com/paper/2112.03609/) (2021)
- [LVM-Med: Learning Large-Scale Self-Supervised Vision Models for Medical Imaging via Second-order Graph Matching](https://mlsanity.com/paper/2306.11925/) (2023)
- [RankSim: Ranking Similarity Regularization for Deep Imbalanced Regression](https://mlsanity.com/paper/2205.15236/) (2022)
- [A-NeSI: A Scalable Approximate Method for Probabilistic Neurosymbolic Inference](https://mlsanity.com/paper/2212.12393/) (2022)
- [CombOptNet: Fit the Right NP-Hard Problem by Learning Integer Programming Constraints](https://mlsanity.com/paper/2105.02343/) (2021)
- [Enhancing Self-Consistency and Performance of Pre-Trained Language Models through Natural Language Inference](https://mlsanity.com/paper/2211.11875/) (2022)
- [PyEPO: A PyTorch-based End-to-End Predict-then-Optimize Library for Linear and Integer Programming](https://mlsanity.com/paper/2206.14234/) (2022)
- [Unsupervised Learning for Combinatorial Optimization with Principled Objective Relaxation](https://mlsanity.com/paper/2207.05984/) (2022)
- [Logically Consistent Language Models via Neuro-Symbolic Integration](https://mlsanity.com/paper/2409.13724/) (2024)
- [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)
- [A Unified Framework for Implicit Sinkhorn Differentiation](https://mlsanity.com/paper/2205.06688/) (2022)
- [Neuro-Symbolic Entropy Regularization](https://mlsanity.com/paper/2201.11250/) (2022)
- [Link Scheduling using Graph Neural Networks](https://mlsanity.com/paper/2109.05536/) (2021)
- [Beyond backpropagation: bilevel optimization through implicit differentiation and equilibrium propagation](https://mlsanity.com/paper/2205.03076/) (2022)
- [Integrated Conditional Estimation-Optimization](https://mlsanity.com/paper/2110.12351/) (2021)
- [Techniques for Symbol Grounding with SATNet](https://mlsanity.com/paper/2106.11072/) (2021)
- [An Overview and Experimental Study of Learning-based Optimization Algorithms for Vehicle Routing Problem](https://mlsanity.com/paper/2107.07076/) (2021)
- [A Pseudo-Semantic Loss for Autoregressive Models with Logical Constraints](https://mlsanity.com/paper/2312.03905/) (2023)

## Abstract (arXiv)

Achieving fusion of deep learning with combinatorial algorithms promises transformative changes to artificial intelligence. One possible approach is to introduce combinatorial building blocks into neural networks. Such end-to-end architectures have the potential to tackle combinatorial problems on raw input data such as ensuring global consistency in multi-object tracking or route planning on maps in robotics. In this work, we present a method that implements an efficient backward pass through blackbox implementations of combinatorial solvers with linear objective functions. We provide both theoretical and experimental backing. In particular, we incorporate the Gurobi MIP solver, Blossom V algorithm, and Dijkstra's algorithm into architectures that extract suitable features from raw inputs for the traveling salesman problem, the min-cost perfect matching problem and the shortest path problem. The code is available at https://github.com/martius-lab/blackbox-backprop.