Neural Certificate Pricing for Combinatorial Optimization Problems
2026-07-01 • Machine Learning
Machine Learning
AI summaryⓘ
The authors propose Neural Certificate Pricing (NCP), a new method to solve hard combinatorial optimization problems, which involve searching many possible solutions. NCP uses a neural network to predict prices related to constraints, making it easier to find good solutions without checking every possibility. Their method ensures feasibility and reduces errors in the solution's quality. Tests show NCP is more efficient and generalizes better than previous neural network methods on various problem types.
Combinatorial optimizationDiscrete structureNeural networksDual pricesPrimal marginalUnsupervised learningSeparation oracleOut-of-distribution generalizationCertificate-consistencyStructured recovery layer
Authors
Jingyi Chen, Xinyuan Zhang, Xinwu Qian
Abstract
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.