mlsanityData to 14 Oct 2026

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

arXiv 2105.02343 ↗First posted 5 May 2021cs.LGcited by 49

Not on the map. Why?

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.

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

33 of 52 references.

References · 33

  1. 2014Adam: A Method for Stochastic Optimizationcited by 37,240
  2. 2017Graph Attention Networkscited by 8,923
  3. 2018Relational inductive biases, deep learning, and graph networkscited by 1,360
  4. 2018Attention, Learn to Solve Routing Problems!cited by 656
  5. 2016CVXPY: A Python-Embedded Modeling Language for Convex Optimizationcited by 641
  6. 2016Neural Combinatorial Optimization with Reinforcement Learningcited by 608
  7. 2017OptNet: Differentiable Optimization as a Layer in Neural Networkscited by 599
  8. 2017Learning Combinatorial Optimization Algorithms over Graphscited by 561
  9. 2019Differentiable Convex Optimization Layerscited by 465
  10. 2019Meta-Learning with Differentiable Convex Optimizationcited by 461
  11. 2017Supervised Learning of Universal Sentence Representations from Natural Language Inference Datacited by 432
  12. 2018Meta-learning with differentiable closed-form solverscited by 397
21 more
  1. 2018Reinforcement Learning for Solving the Vehicle Routing Problemcited by 333
  2. 2018Safe Exploration in Continuous Action Spacescited by 247
  3. 2019Differentiation of Blackbox Combinatorial Solverscited by 226
  4. 2020Solving Mixed Integer Programs Using Neural Networkscited by 182
  5. 2019SATNet: Bridging deep learning and logical reasoning using a differentiable satisfiability solvercited by 173
  6. 2019Do NLP Models Know Numbers? Probing Numeracy in Embeddingscited by 159
  7. 2019SPair-71k: A Large-scale Benchmark for Semantic Correspondencecited by 146
  8. 2019Neural Execution of Graph Algorithmscited by 121
  9. 2016On Differentiating Parameterized Argmin and Argmax Problems with Application to Bi-level Optimizationcited by 112
  10. 2019MIPaaL: Mixed Integer Program as a Layercited by 94
  11. 2020Deep Graph Matching Consensuscited by 85
  12. 2020Learning with Differentiable Perturbed Optimizerscited by 81
  13. 2020Deep Graph Matching via Blackbox Differentiation of Combinatorial Solverscited by 81
  14. 2018Learning to Branchcited by 78
  15. 2019Differentiating Through a Cone Programcited by 73
  16. 2018SparseMAP: Differentiable Sparse Structured Inferencecited by 62
  17. 2019Optimizing Rank-based Metrics with Blackbox Differentiationcited by 58
  18. 2019End to end learning and optimization on graphscited by 44
  19. 2019The Differentiable Cross-Entropy Methodcited by 27
  20. 2018What game are we playing? End-to-end learning in normal and extensive form gamescited by 22
  21. 2020Learning Linear Programs from Optimal Decisionscited by 18

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 4; 2022: 15; 2023: 11; 2024: 7; 2025: 6; 2026: 6.

49 papers.

Sort:

By area:

  1. 2023Decision-Focused Learning: Foundations, State of the Art, Benchmark and Future Opportunitiescited by 130
  2. 2022A Survey for Solving Mixed Integer Programming via Machine Learningcited by 44
  3. 2021GREED: A Neural Framework for Learning Graph Distance Functionscited by 32
  4. 2022Backpropagation through Combinatorial Algorithms: Identity with Projection Workscited by 29
  5. 2022Learning with Combinatorial Optimization Layers: a Probabilistic Approachcited by 29
  6. 2021Optimization with Constraint Learning: A Framework and Surveycited by 28
  7. 2023Landscape Surrogate: Learning Decision Losses for Mathematical Optimization Under Partial Informationcited by 18
  8. 2022Flexible Differentiable Optimization via Model Transformationscited by 16
  9. 2024LinSATNet: The Positive Linear Satisfiability Neural Networkscited by 16
  10. 2022Neural Set Function Extensions: Learning with Discrete Functions in High Dimensionscited by 14
  11. 2023On Learning Latent Models with Multi-Instance Weak Supervisioncited by 13
  12. 2022Certifiable 3D Object Pose Estimation: Foundations, Learning Models, and Self-Trainingcited by 12
37 more
  1. 2022Predict+Optimize for Packing and Covering LPs with Unknown Parameters in Constraintscited by 11
  2. 2023Score Function Gradient Estimation to Widen the Applicability of Decision-Focused Learningcited by 11
  3. 2024End-to-End Cost-Effective Incentive Recommendation under Budget Constraint with Uplift Modelingcited by 10
  4. 2024Differentiation Through Black-Box Quadratic Programming Solverscited by 10
  5. 2023Machine Learning with Requirements: a Manifestocited by 8
  6. 2023Benchmarking PtO and PnO Methods in the Predictive Combinatorial Optimization Regimecited by 8
  7. 2021Diff-Explainer: Differentiable Convex Optimization for Explainable Multi-hop Inferencecited by 7
  8. 2024Tackling Prevalent Conditions in Unsupervised Combinatorial Optimization: Cardinality, Minimum, Covering, and Morecited by 7
  9. 2024GLinSAT: The General Linear Satisfiability Neural Network Layer By Accelerated Gradient Descentcited by 7
  10. 2023A Correct-and-Certify Approach to Self-Supervise Object Pose Estimators via Ensemble Self-Trainingcited by 6
  11. 2024LPGD: A General Framework for Backpropagation through Embedded Optimization Layerscited by 6
  12. 2025Feasibility-Aware Decision-Focused Learning for Predicting Parameters in the Constraintscited by 6
  13. 2022Confidence Threshold Neural Divingcited by 5
  14. 2022A Solver-Free Framework for Scalable Learning in Neural ILP Architecturescited by 5
  15. 2023TACOS: Topology-Aware Collective Algorithm Synthesizer for Distributed Machine Learningcited by 4
  16. 2025Geometric Algorithms for Neural Combinatorial Optimization with Constraintscited by 4
  17. 2023GenCO: Generating Diverse Designs with Combinatorial Constraintscited by 3
  18. 2025Efficient End-to-End Learning for Decision-Making: A Meta-Optimization Approachcited by 3
  19. 2025A Fully First-Order Layer for Differentiable Optimizationcited by 3
  20. 2022Beyond NaN: Resiliency of Optimization Layers in The Face of Infeasibilitycited by 1
  21. 2022Going Beyond Approximation: Encoding Constraints for Explainable Multi-hop Inference via Differentiable Combinatorial Solverscited by 1
  22. 2022Learning predictive checklists from continuous medical datacited by 1
  23. 2023Two-Stage Predict+Optimize for Mixed Integer Linear Programs with Unknown Parameters in Constraintscited by 1
  24. 2024A Differentiable Integer Linear Programming Solver for Explanation-Based Natural Language Inferencecited by 1
  25. 2021Structural Causal Models Reveal Confounder Bias in Linear Program Modellingcited by 0
  26. 2022Finding Structure and Causality in Linear Programscited by 0
  27. 2022Machines Explaining Linear Programscited by 0
  28. 2022Attributions Beyond Neural Networks: The Linear Program Casecited by 0
  29. 2023Accelerating L-shaped Two-stage Stochastic SCUC with Learning Integrated Benders Decompositioncited by 0
  30. 2025Neuro-symbolic Weak Supervision: Theory and Semanticscited by 0
  31. 2025Scalable Decision Focused Learning via Online Trainable Surrogatescited by 0
  32. 2026AAC: Admissible-by-Architecture Differentiable Landmark Compression for ALTcited by 0
  33. 2026GOAL: Graph-based Objective-Aligned Diffusion Solvers for Dynamic Multi-Objective Optimizationcited by 0
  34. 2026DisjunctiveNet: Neural Symbolic Learning via Differentiable Convexified Optimization Layerscited by 0
  35. 2026Diff2SP: Diffusion Models for Correlated Scenario Generation in Stochastic Programmingcited by 0
  36. 2026Hard Constraints, Smooth Gradients: Learning Feasible Inventory Policies via Differentiable Projectioncited by 0
  37. 2026PolyStepOR: Learning to Decide Without Optimal Decisionscited by 0