DualCert通过约束耦合学习，高效求解大规模旅行商问题并保证结果正确。
DualCert: A Solver for the Traveling Salesman Problem with Constraint-Coupled Learning
- 引入约束耦合学习，让每步学习都满足动态生成的约束条件。
- 在1000个测试实例上平均误差仅0.0573%，比NeuroLKH降低67.1%。
- 适用于需要高可靠性输出的工业优化场景，如物流路径规划。
大规模旅行商问题（TSP）实例要求求解器在有限计算资源下分配算力，同时保证输出有效性。现有神经-运筹学混合方法预测引导信息时，无需学习过程满足搜索中发现的约束。DualCert提出约束耦合学习，使当前度方程与动态分离的子环消除约束（SECs）共同定义每个学习转移。每次精化过程中，度方程与选定的严格满足的SEC方程（含正松弛）构成依赖于迭代点的对偶松弛卡鲁什-库恩-塔克（KKT）流形。修复后的对偶变量与违反的SEC行定义局部成本场。精确约束镜面下降步骤将每个有限状态映射到同一流形上的正值状态。当选定行与确定性绑定保持不变时，隐式微分将参数扰动映射至流形切空间，并复用前向约束算子计算局部成本场梯度。最终边状态在固定预算下分配算力于Held-Karp上升、候选图边测试与路径构建。确定性验证重新计算原始代价，仅接受经验证的候选图下界与边决策。在1000个独立测试的TSP1000实例上，DualCert以每例9.55秒的批量均摊时间，达到相对于Lin–Kernighan–Helsgaun版本3（LKH-3）参考路径的平均路径成本差距为0.0573%。它对所有实例返回验证的候选图下界，边决策覆盖率达81.46%。该平均差距比报告的NeuroLKH均值小67.1%。因此，优化约束驱动学习过程，而确定性验证确保输出有效性。
原文摘要 · Abstract (English)
Large traveling salesman problem (TSP) instances require a solver to allocate limited computation while preserving the validity of its outputs. Existing neural--operations-research (OR) hybrids predict guidance without requiring learned transitions to satisfy constraints discovered during search. DualCert introduces \emph{constraint-coupled learning}, in which current degree equations and dynamically separated subtour-elimination constraints (SECs) define each learned transition. At each refinement, the degree equations and selected, strictly satisfied SEC equations, with positive slacks, define an iterate-dependent primal-slack Karush--Kuhn--Tucker (KKT) manifold. Repaired dual variables and violated SEC rows define a local cost field. An exact constrained mirror-descent step maps each finite state to a positive state on the same manifold. Where selected rows and deterministic ties remain fixed, implicit differentiation maps parameter perturbations into the manifold tangent space and reuses the forward constraint operator for the local-cost-field derivative. The terminal edge state allocates computation across Held--Karp ascent, candidate-graph edge tests, and tour construction under a fixed budget. Deterministic verification recomputes original costs and accepts only verified candidate-graph lower bounds and edge decisions. On 1,000 held-out TSP1000 instances, DualCert attains a mean tour-cost gap of \(0.0573\%\) from Lin--Kernighan--Helsgaun version 3 (LKH-3) reference tours in \(9.55\) batch-amortized seconds per instance. It returns a verified candidate-graph lower bound for every instance and achieves \(81.46\%\) edge-decision coverage. The mean gap is \(67.1\%\) smaller than the reported NeuroLKH mean gap. Thus, optimization constraints govern learning, while deterministic verification preserves output validity.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。