---
title: "神经证书定价：组合优化问题的高效求解新方法"
source: "arXiv AI/CL/LG（论文）"
source_tier: "t2"
url: "https://arxiv.org/abs/2607.01185v1"
permalink: "https://feed.astralor.com/items/itm_aaf43bb058bc6d5565a555df"
published: "2026-07-01T17:17:55.000Z"
score: 55
channel: "ai"
tags: ["无监督学习","神经证书定价","组合优化"]
---

# 神经证书定价：组合优化问题的高效求解新方法

## 速览

组合优化问题因需指数级搜索而困难，但一旦提供可行解，其结构可行性可多项式验证。本文提出神经证书定价（NCP），利用这种不对称性，通过无监督学习训练神经网络预测证书级对偶价格，结构恢复层构建原始边际解。当证书一致性条件成立时，恢复的边际解全局可行，且一阶误差仅导致目标值二阶损失。在三大类组合优化问题中，NCP显著优于或媲美最先进神经网络基线，计算时间大幅减少，且具有更强的分布外泛化能力。

## 关键点

- 首次提出神经证书定价框架，利用组合优化中搜索与验证的不对称性
- 无监督学习训练，无需标注最优解标签
- 理论证明价格一阶误差仅导致目标值二阶损失
- 在三个组合优化问题集上超越或持平现有方法，计算时间大幅减少

## 全文

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.

---

引用前请核对原文;本文由星际流动整理:https://feed.astralor.com/items/itm_aaf43bb058bc6d5565a555df