用神经网络预测组合优化的证明价格，加速求解并保证结果正确性。
Neural Certificate Pricing for Combinatorial Optimization Problems
- 训练神经网络预测证书级别的对偶价格，结合结构恢复层生成可行解
- 在三类组合优化问题上，性能优于或远快于现有神经基线方法
- 具备强分布外泛化能力，适合需要高效可靠解的工业场景
组合优化问题因可验证的离散结构导致搜索空间指数级增长：虽需遍历指数级候选解才能证明最优性，但一旦给出路径、打包或覆盖方案，其结构可行性可在多项式时间内验证。本文提出神经证书定价（NCP），在无监督学习框架下利用此不对称性。通过神经网络预测证书级别的对偶价格，再由结构恢复层构建对应的原始边际解。NCP可视为一种摊销分离机制：无需枚举违反不等式，而是通过学习残差价格来实现其整体影响的恢复。当证书一致性条件满足时，恢复出的边际解全局可行；局部理论表明，预测价格的一阶误差仅导致目标值的二阶损失。在三类组合优化问题中，NCP要么显著优于现有最先进神经基线，要么以极低计算开销达到相当性能，并展现出更强的分布外泛化能力。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。