新论文提出NCP方法，用神经网络直接预测组合优化问题的对偶价格，比之前的方法更快更准，泛化也好，值得关注。
组合优化问题因可验证的离散结构导致指数级搜索空间。该研究提出神经证书定价（NCP），在无监督学习框架下训练神经网络预测证书级对偶价格，并通过结构恢复层构建原始边际。满足证书一致性条件时，恢复的边际全局可行，且一阶预测误差仅引起目标值的二阶损失。在三个组合优化问题类别上，NCP大幅超越或匹配现有最优神经基线，同时计算时间显著减少，且分布外泛化能力更强。
Neural Certificate Pricing for Combinatorial Optimization Problems
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.