# CombOptNet: Fit the Right NP-Hard Problem by Learning Integer Programming Constraints

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

## Key facts

- Cited by 49 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 52 references that are in the map.
- First posted on arXiv 5 May 2021.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Relational inductive biases, deep learning, and graph networks](https://mlsanity.com/paper/1806.01261/) (2018)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [CVXPY: A Python-Embedded Modeling Language for Convex Optimization](https://mlsanity.com/paper/1603.00943/) (2016)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [OptNet: Differentiable Optimization as a Layer in Neural Networks](https://mlsanity.com/paper/1703.00443/) (2017)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Differentiable Convex Optimization Layers](https://mlsanity.com/paper/1910.12430/) (2019)
- [Meta-Learning with Differentiable Convex Optimization](https://mlsanity.com/paper/1904.03758/) (2019)
- [Supervised Learning of Universal Sentence Representations from Natural Language Inference Data](https://mlsanity.com/paper/1705.02364/) (2017)
- [Meta-learning with differentiable closed-form solvers](https://mlsanity.com/paper/1805.08136/) (2018)
- [Reinforcement Learning for Solving the Vehicle Routing Problem](https://mlsanity.com/paper/1802.04240/) (2018)
- [Safe Exploration in Continuous Action Spaces](https://mlsanity.com/paper/1801.08757/) (2018)
- [Differentiation of Blackbox Combinatorial Solvers](https://mlsanity.com/paper/1912.02175/) (2019)
- [Solving Mixed Integer Programs Using Neural Networks](https://mlsanity.com/paper/2012.13349/) (2020)
- [SATNet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver](https://mlsanity.com/paper/1905.12149/) (2019)
- [Do NLP Models Know Numbers? Probing Numeracy in Embeddings](https://mlsanity.com/paper/1909.07940/) (2019)
- [SPair-71k: A Large-scale Benchmark for Semantic Correspondence](https://mlsanity.com/paper/1908.10543/) (2019)
- [Neural Execution of Graph Algorithms](https://mlsanity.com/paper/1910.10593/) (2019)
- [On Differentiating Parameterized Argmin and Argmax Problems with Application to Bi-level Optimization](https://mlsanity.com/paper/1607.05447/) (2016)
- [MIPaaL: Mixed Integer Program as a Layer](https://mlsanity.com/paper/1907.05912/) (2019)
- [Deep Graph Matching Consensus](https://mlsanity.com/paper/2001.09621/) (2020)
- [Learning with Differentiable Perturbed Optimizers](https://mlsanity.com/paper/2002.08676/) (2020)
- [Deep Graph Matching via Blackbox Differentiation of Combinatorial Solvers](https://mlsanity.com/paper/2003.11657/) (2020)
- [Learning to Branch](https://mlsanity.com/paper/1803.10150/) (2018)
- [Differentiating Through a Cone Program](https://mlsanity.com/paper/1904.09043/) (2019)
- [SparseMAP: Differentiable Sparse Structured Inference](https://mlsanity.com/paper/1802.04223/) (2018)
- [Optimizing Rank-based Metrics with Blackbox Differentiation](https://mlsanity.com/paper/1912.03500/) (2019)
- [End to end learning and optimization on graphs](https://mlsanity.com/paper/1905.13732/) (2019)

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

- [Decision-Focused Learning: Foundations, State of the Art, Benchmark and Future Opportunities](https://mlsanity.com/paper/2307.13565/) (2023)
- [A Survey for Solving Mixed Integer Programming via Machine Learning](https://mlsanity.com/paper/2203.02878/) (2022)
- [GREED: A Neural Framework for Learning Graph Distance Functions](https://mlsanity.com/paper/2112.13143/) (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)
- [Optimization with Constraint Learning: A Framework and Survey](https://mlsanity.com/paper/2110.02121/) (2021)
- [Landscape Surrogate: Learning Decision Losses for Mathematical Optimization Under Partial Information](https://mlsanity.com/paper/2307.08964/) (2023)
- [Flexible Differentiable Optimization via Model Transformations](https://mlsanity.com/paper/2206.06135/) (2022)
- [LinSATNet: The Positive Linear Satisfiability Neural Networks](https://mlsanity.com/paper/2407.13917/) (2024)
- [Neural Set Function Extensions: Learning with Discrete Functions in High Dimensions](https://mlsanity.com/paper/2208.04055/) (2022)
- [On Learning Latent Models with Multi-Instance Weak Supervision](https://mlsanity.com/paper/2306.13796/) (2023)
- [Certifiable 3D Object Pose Estimation: Foundations, Learning Models, and Self-Training](https://mlsanity.com/paper/2206.11215/) (2022)
- [Predict+Optimize for Packing and Covering LPs with Unknown Parameters in Constraints](https://mlsanity.com/paper/2209.03668/) (2022)
- [Score Function Gradient Estimation to Widen the Applicability of Decision-Focused Learning](https://mlsanity.com/paper/2307.05213/) (2023)
- [End-to-End Cost-Effective Incentive Recommendation under Budget Constraint with Uplift Modeling](https://mlsanity.com/paper/2408.11623/) (2024)
- [Differentiation Through Black-Box Quadratic Programming Solvers](https://mlsanity.com/paper/2410.06324/) (2024)
- [Machine Learning with Requirements: a Manifesto](https://mlsanity.com/paper/2304.03674/) (2023)
- [Benchmarking PtO and PnO Methods in the Predictive Combinatorial Optimization Regime](https://mlsanity.com/paper/2311.07633/) (2023)
- [Diff-Explainer: Differentiable Convex Optimization for Explainable Multi-hop Inference](https://mlsanity.com/paper/2105.03417/) (2021)
- [Tackling Prevalent Conditions in Unsupervised Combinatorial Optimization: Cardinality, Minimum, Covering, and More](https://mlsanity.com/paper/2405.08424/) (2024)
- [GLinSAT: The General Linear Satisfiability Neural Network Layer By Accelerated Gradient Descent](https://mlsanity.com/paper/2409.17500/) (2024)
- [A Correct-and-Certify Approach to Self-Supervise Object Pose Estimators via Ensemble Self-Training](https://mlsanity.com/paper/2302.06019/) (2023)
- [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)
- [Confidence Threshold Neural Diving](https://mlsanity.com/paper/2202.07506/) (2022)
- [A Solver-Free Framework for Scalable Learning in Neural ILP Architectures](https://mlsanity.com/paper/2210.09082/) (2022)
- [TACOS: Topology-Aware Collective Algorithm Synthesizer for Distributed Machine Learning](https://mlsanity.com/paper/2304.05301/) (2023)
- [Geometric Algorithms for Neural Combinatorial Optimization with Constraints](https://mlsanity.com/paper/2510.24039/) (2025)
- [GenCO: Generating Diverse Designs with Combinatorial Constraints](https://mlsanity.com/paper/2310.02442/) (2023)
- [Efficient End-to-End Learning for Decision-Making: A Meta-Optimization Approach](https://mlsanity.com/paper/2505.11360/) (2025)

## Abstract (arXiv)

Bridging logical and algorithmic reasoning with modern machine learning techniques is a fundamental challenge with potentially transformative impact. On the algorithmic side, many NP-hard problems can be expressed as integer programs, in which the constraints play the role of their "combinatorial specification." In this work, we aim to integrate integer programming solvers into neural network architectures as layers capable of learning both the cost terms and the constraints. The resulting end-to-end trainable architectures jointly extract features from raw data and solve a suitable (learned) combinatorial problem with state-of-the-art integer programming solvers. We demonstrate the potential of such layers with an extensive performance analysis on synthetic data and with a demonstration on a competitive computer vision keypoint matching benchmark.