mlsanityData to 7 Oct 2026

Differentiation of Blackbox Combinatorial Solvers

arXiv 1912.02175 ↗First posted 4 Dec 2019cs.LG stat.MLcited by 224

Not on the map. Why?

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.

Key facts. Cited by 224 papers in the map (data through 7 Oct 2026). First posted on arXiv 4 Dec 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 32; 2022: 35; 2023: 49; 2024: 47; 2025: 28; 2026: 33.

224 papers.

Sort:

By area:

  1. 2021Combinatorial optimization and reasoning with graph neural networkscited by 267
  2. 2021End-to-End Constrained Optimization Learning: A Surveycited by 154
  3. 2023Decision-Focused Learning: Foundations, State of the Art, Benchmark and Future Opportunitiescited by 129
  4. 2025The Diffusion Dualitycited by 124
  5. 2022Semantic Probabilistic Layers for Neuro-Symbolic Learningcited by 103
  6. 2021Implicit MLE: Backpropagating Through Discrete Exponential Family Distributionscited by 97
  7. 2023A Survey of Contextual Optimization Methods for Decision Making under Uncertaintycited by 81
  8. 2021On Training Implicit Modelscited by 73
  9. 2023RL4CO: an Extensive Reinforcement Learning for Combinatorial Optimization Benchmarkcited by 70
  10. 2021GrooMeD-NMS: Grouped Mathematically Differentiable NMS for Monocular 3D Object Detectioncited by 66
  11. 2022Theseus: A Library for Differentiable Nonlinear Optimizationcited by 64
  12. 2021Decision-Focused Learning: Through the Lens of Learning to Rankcited by 61
38 more
  1. 2023LVM-Med: Learning Large-Scale Self-Supervised Vision Models for Medical Imaging via Second-order Graph Matchingcited by 60
  2. 2022RankSim: Ranking Similarity Regularization for Deep Imbalanced Regressioncited by 52
  3. 2022A-NeSI: A Scalable Approximate Method for Probabilistic Neurosymbolic Inferencecited by 50
  4. 2021CombOptNet: Fit the Right NP-Hard Problem by Learning Integer Programming Constraintscited by 49
  5. 2022Enhancing Self-Consistency and Performance of Pre-Trained Language Models through Natural Language Inferencecited by 40
  6. 2022PyEPO: A PyTorch-based End-to-End Predict-then-Optimize Library for Linear and Integer Programmingcited by 32
  7. 2022Unsupervised Learning for Combinatorial Optimization with Principled Objective Relaxationcited by 32
  8. 2024Logically Consistent Language Models via Neuro-Symbolic Integrationcited by 30
  9. 2022Backpropagation through Combinatorial Algorithms: Identity with Projection Workscited by 29
  10. 2022A Unified Framework for Implicit Sinkhorn Differentiationcited by 28
  11. 2022Learning with Combinatorial Optimization Layers: a Probabilistic Approachcited by 28
  12. 2022Neuro-Symbolic Entropy Regularizationcited by 27
  13. 2021Link Scheduling using Graph Neural Networkscited by 26
  14. 2022Beyond backpropagation: bilevel optimization through implicit differentiation and equilibrium propagationcited by 26
  15. 2021Integrated Conditional Estimation-Optimizationcited by 25
  16. 2021Techniques for Symbol Grounding with SATNetcited by 24
  17. 2021An Overview and Experimental Study of Learning-based Optimization Algorithms for Vehicle Routing Problemcited by 22
  18. 2021Learning Hard Optimization Problems: A Data Generation Perspectivecited by 21
  19. 2021Learning with Algorithmic Supervision via Continuous Relaxationscited by 21
  20. 2022SurCo: Learning Linear Surrogates For Combinatorial Nonlinear Optimization Problemscited by 21
  21. 2023A Pseudo-Semantic Loss for Autoregressive Models with Logical Constraintscited by 21
  22. 2021Fast Approximations for Job Shop Scheduling: A Lagrangian Dual Deep Learning Methodcited by 20
  23. 2021Robust and Decomposable Average Precision for Image Retrievalcited by 19
  24. 2023Estimate-Then-Optimize versus Integrated-Estimation-Optimization versus Sample Average Approximation: A Stochastic Dominance Perspectivecited by 19
  25. 2022TorchOpt: An Efficient Library for Differentiable Optimizationcited by 17
  26. 2023Landscape Surrogate: Learning Decision Losses for Mathematical Optimization Under Partial Informationcited by 17
  27. 2023Unlocking Slot Attention by Changing Optimal Transport Costscited by 16
  28. 2023Behavior Alignment via Reward Function Optimizationcited by 16
  29. 2024Decision-Focused Learning with Directional Gradientscited by 16
  30. 2024LinSATNet: The Positive Linear Satisfiability Neural Networkscited by 16
  31. 2024KLay: Accelerating Arithmetic Circuits for Neurosymbolic AIcited by 16
  32. 2021Self-Supervised Learning of Audio Representations from Permutations with Differentiable Rankingcited by 14
  33. 2022Neural Set Function Extensions: Learning with Discrete Functions in High Dimensionscited by 14
  34. 2023Differentiable Clustering with Perturbed Spanning Forestscited by 14
  35. 2022TransPath: Learning Heuristics For Grid-Based Pathfinding via Transformerscited by 13
  36. 2023Backpropagation of Unrolled Solvers with Folded Optimizationcited by 13
  37. 2023On Learning Latent Models with Multi-Instance Weak Supervisioncited by 13
  38. 2022Certifiable 3D Object Pose Estimation: Foundations, Learning Models, and Self-Trainingcited by 12

50 most cited of 224 All 224 (JSON)