DualCert: A Solver for the Traveling Salesman Problem with Constraint-Coupled Learning
2026-08-10 • Artificial Intelligence
Artificial Intelligence
AI summaryⓘ
The authors present DualCert, a new method to solve large Traveling Salesman Problems (TSP) by combining neural networks with optimization constraints to guide the search more reliably. They use a technique called constraint-coupled learning, where problem constraints help shape each step of the solution process, ensuring outputs remain valid. Their approach also includes a verification step that double-checks results to guarantee correctness. On large test problems, DualCert produced solutions very close to a top classical solver but faster and with guaranteed validity. This means the authors effectively blend learning with rigorous mathematical rules to improve TSP solving.
Traveling Salesman Problemconstraint-coupled learningsubtour-elimination constraintsKarush–Kuhn–Tucker conditionsmirror descentHeld–Karp lower boundcandidate graphNeuroLKHdeterministic verificationLin-Kernighan-Helsgaun
Authors
Yancheng Song, Yongzhi Qi, Wei Qi, Zuo-Jun Max Shen
Abstract
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.