# Neural Certificate Pricing for Combinatorial Optimization Problems

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 26 of its 54 references that are in the map.
- First posted on arXiv 1 Jul 2026.

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

- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Deep Equilibrium Models](https://mlsanity.com/paper/1909.01377/) (2019)
- [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)
- [POMO: Policy Optimization with Multiple Optima for Reinforcement Learning](https://mlsanity.com/paper/2010.16011/) (2020)
- [Exact Combinatorial Optimization with Graph Convolutional Neural Networks](https://mlsanity.com/paper/1906.01629/) (2019)
- [An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem](https://mlsanity.com/paper/1906.01227/) (2019)
- [DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization](https://mlsanity.com/paper/2302.08224/) (2023)
- [Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search](https://mlsanity.com/paper/1810.10659/) (2018)
- [SATNet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver](https://mlsanity.com/paper/1905.12149/) (2019)
- [Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs](https://mlsanity.com/paper/2006.10643/) (2020)
- [SparseMAP: Differentiable Sparse Structured Inference](https://mlsanity.com/paper/1802.04223/) (2018)
- [A Diffusion Model Framework for Unsupervised Neural Combinatorial Optimization](https://mlsanity.com/paper/2406.01661/) (2024)
- [Fast T2T: Optimization Consistency Speeds Up Diffusion-Based Training-to-Testing Solving for Combinatorial Optimization](https://mlsanity.com/paper/2502.02941/) (2025)
- [Finding Near-Optimal Independent Sets at Scale](https://mlsanity.com/paper/1509.00764/) (2015)
- [A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs](https://mlsanity.com/paper/2106.04927/) (2021)
- [Large Language Models for Combinatorial Optimization: A Systematic Review](https://mlsanity.com/paper/2507.03637/) (2025)
- [Graph Neural Networks for Job Shop Scheduling Problems: A Survey](https://mlsanity.com/paper/2406.14096/) (2024)
- [Primal-Dual Neural Algorithmic Reasoning](https://mlsanity.com/paper/2505.24067/) (2025)
- [Learning for routing: A guided review of recent developments and future directions](https://mlsanity.com/paper/2507.00218/) (2025)
- [Combinatorial Optimization Augmented Machine Learning](https://mlsanity.com/paper/2601.10583/) (2026)
- [Unsupervised Learning for the Elementary Shortest Path Problem](https://mlsanity.com/paper/2508.01557/) (2025)

## Abstract (arXiv)

Combinatorial optimization (CO) problems are difficult because certifiable discrete structure induces exponential search. One needs to search over the set exponentially many candidates to certify optimality, however, the structural feasibility of a path, packing, or cover can be verified in polynomial time once supplied. In this study, we introduce Neural Certificate Pricing (NCP) that exploits this asymmetry under an unsupervised learning framework. A neural network is trained to predict certificate-level dual prices, while a structured recovery layer constructs the induced primal marginal. NCP can be viewed as amortized separation: instead of enumerating violated inequalities, it learns the residual prices through which their aggregate effect enters recovery. When the certificate-consistency condition holds, the recovered marginal is globally feasible, and a local theory shows that first-order errors in the predicted price induce only second-order loss in objective value. Across three classes of CO problems, NCP either outperforms state-of-the-art neural baselines by large margins or matches them at a fraction of the computation time, and shows stronger out-of-distribution generalization.