DualCert: A Solver for the Traveling Salesman Problem with Constraint-Coupled Learning

• URL: http://arxiv.org/abs/2608.09042v1
• Date: Mon, 10 Aug 2026 02:48:16 GMT
• Title: DualCert: A Solver for the Traveling Salesman Problem with Constraint-Coupled Learning
• Abstract summary: Large traveling salesman problem (TSP) instances require a solver to allocate limited computation while preserving the validity of its outputs.<n> DualCert introduces emphconstraint-coupled learning, in which current degree equations and dynamically separated subtour-elimination constraints define each learned transition.<n>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
• Score: 4.941039246565574
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Statistical Symmetry Release for Equivariant Quantum Learning [12.042012916861829]
  Hard symmetry constraints reduce model complexity, but can also erase label information.<n> Statistical symmetry release determines when finite data and quantum measurements justify relaxing such a constraint.
  arXiv  Detail & Related papers  (2026-09-10T12:38:27Z)
• Constrained Online Learning with Noisy Constraint Values [55.29259818039367]
  Under common feasibility, our LEDGER algorithm attains $O(sqrt T)$ expected regret and $O(sqrtTlog(eT))$ expected budget violation.<n>Neither a Slater condition, independence between feedback channels, nor an absolute constraint-value bound is needed.
  arXiv  Detail & Related papers  (2026-09-07T01:38:41Z)
• The Cost of Adaptivity: Matching Lower Bounds Across Learning Problems [1.0742675209112622]
  We formalize nuisance adaptation via a slice-normalized minimax ratio.<n>We also define the cost of expanding from one preannounced Gaussian query to arbitrary post-hoc inspection.
  arXiv  Detail & Related papers  (2026-08-09T17:19:11Z)
• PAC-Bayesian Certificates for Quadratic Closed-Loop Control [0.0]
  PAC-Bayesian bounds provide finite-sample guarantees for data-dependent predictors.<n>Applying them to learning-based control is difficult because the natural objective is a quadratic trajectory cost.<n>We provide a set of PAC-Bayes-Chernoff certificates for posterior distributions over feasible closed-loop responses.
  arXiv  Detail & Related papers  (2026-06-26T17:24:21Z)
• A Barrier-Metric First-Order Method for Linearly Constrained Bilevel Optimization [1.4323566945483492]
  We study bilevel optimization with a fixed polyhedral lower feasible set.<n>Active-set changes can make the upper objective nonsmooth.<n>Existing hypergradient methods typically require lower-Hessian inversions or equivalent linear solves.
  arXiv  Detail & Related papers  (2026-05-12T03:44:08Z)
• The Extrapolation Cliff in On-Policy Distillation of Near-Deterministic Structured Outputs [52.709361620508595]
  ListOPD brings a student to in-domain with an 8B-SFT baseline at one-fifth the parameters.<n>On Amazon Fashion, three pre-registered tests--a fine-grid cliff interval test, and a small-clip cross-prediction--fall within their locked prediction windows--with the small-clip value matching the closed-form prediction below grid resolution.
  arXiv  Detail & Related papers  (2026-05-09T06:48:00Z)
• Adaptive Test-Time Compute Allocation for Reasoning LLMs via Constrained Policy Optimization [18.737087162461563]
  Test-time compute scaling has become a powerful lever for improving large language model performance.<n>Yet deploying these techniques under finite inference budgets requires a decision that current systems largely ignore.<n>We formalize this as a constrained optimization problem (maximize expected accuracy subject to an average compute budget) and solve it with a two-stage Solve-then-Learn pipeline.
  arXiv  Detail & Related papers  (2026-04-16T10:39:22Z)
• Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency [90.40062452292091]
  We present the first computationally efficient algorithm for linear bandits with heteroscedastic noise. Our algorithm is adaptive to the unknown variance of noise and achieves an $tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regret. We also propose a variance-adaptive algorithm for linear mixture Markov decision processes (MDPs) in reinforcement learning.
  arXiv  Detail & Related papers  (2023-02-21T00:17:24Z)
• Fully Stochastic Trust-Region Sequential Quadratic Programming for Equality-Constrained Optimization Problems [62.83783246648714]
  We propose a sequential quadratic programming algorithm (TR-StoSQP) to solve nonlinear optimization problems with objectives and deterministic equality constraints. The algorithm adaptively selects the trust-region radius and, compared to the existing line-search StoSQP schemes, allows us to utilize indefinite Hessian matrices.
  arXiv  Detail & Related papers  (2022-11-29T05:52:17Z)
• Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
  We use kernel Hilbert spaces for estimating the value function of an infinite-horizon discounted Markov reward process. We derive a non-asymptotic upper bound on the error with explicit dependence on the eigenvalues of the associated kernel operator. We prove minimax lower bounds over sub-classes of MRPs.
  arXiv  Detail & Related papers  (2021-09-24T14:48:20Z)
• Regret and Cumulative Constraint Violation Analysis for Online Convex Optimization with Long Term Constraints [24.97580261894342]
  This paper considers online convex optimization with long term constraints, where constraints can be violated in intermediate rounds, but need to be satisfied in the long run. A novel algorithm is first proposed and it achieves an $mathcalO(Tmaxc,1-c)$ bound for static regret and an $mathcalO(T(1-c)/2)$ bound for cumulative constraint violation.
  arXiv  Detail & Related papers  (2021-06-09T15:18:06Z)
• Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Loss [145.54544979467872]
  We consider online learning for episodically constrained Markov decision processes (CMDPs) We propose a new emphupper confidence primal-dual algorithm, which only requires the trajectories sampled from the transition model. Our analysis incorporates a new high-probability drift analysis of Lagrange multiplier processes into the celebrated regret analysis of upper confidence reinforcement learning.
  arXiv  Detail & Related papers  (2020-03-02T05:02:23Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.