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

DualCert introduces constraint-coupled learning, under which current degree equations and dynamically separated subtour-elimination constraints (SECs) define the geometry of each learned transition. At each refinement, the degree equations and selected, strictly satisfied SEC equations, represented with positive slacks, define an iterate-dependent primal-slack Karush–Kuhn–Tucker (KKT) manifold. Repaired dual variables provide the reduced-cost component of a local cost field, and violated SEC rows provide its penalty component. An exact constrained mirror-descent step maps each finite input state to a positive output on the same primal-slack KKT manifold. On each region where the selected rows and deterministic ties remain fixed, implicit differentiation maps parameter perturbations into the manifold tangent space, while the local-cost-field derivative reuses the forward constraint operator. The terminal edge state determines learned allocation across Held–Karp ascent, candidate-graph edge tests, and tour construction under a fixed computation budget. Deterministic verification uses original-cost recomputation to accept only verified candidate-graph lower bounds and verified 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. Overall, optimization constraints define the edge state and learning geometry, while deterministic verification preserves the stated validity of reported lower bounds and edge decisions.

The paper states: "DualCert follows one design principle: OR constraints govern learned transitions and derivatives, learning allocates computation, and deterministic routines determine reportable outputs. We call this principle constraint-coupled learning. The computational sequence begins with a constraint-defined state: The edge state assigns positive preferences to candidate arcs, directed copies of candidate edges, rather than a discrete tour. Degree equations and selected, strictly satisfied SECs with positive slacks define the primal-slack Karush–Kuhn–Tucker (KKT) manifold. The manifold contains positive states satisfying the selected equations; it is not the set of complete KKT optima."

The exact constrained mirror-descent step is defined as: z t+1,− = arg min ηt ⟨atϕ, z⟩ + Dω (z, z t), z∈Mt with the exponential form z t+1,− = z t ⊙ exp −ηt atϕ − Jt⊤ ρt and the dual residual Ft (ρ) = Jt z t ⊙ exp −ηt atϕ − Jt⊤ ρ − qt, Ft (ρt) = 0. Theorem 1 establishes Finite-step manifold invariance: "For z t ∈ Mt, finite atϕ, and 0 < ηt < ∞, Equation (8) has a unique positive solution z t+1,− ∈ Mt and a unique multiplier ρt. Moreover, the Jacobian of Ft with respect to ρ satisfies −Dρ Ft (ρt) = Jt Diag(z t+1,−)Jt⊤. The displayed matrix is positive definite."

Theorem 2 establishes Shared forward–backward constraint operator: "For every local-cost-field perturbation v ∈ Rm+St, the finite-update derivative satisfies Da z + [v] = −ηt Pt+ (v), Jt Da z + [v] = 0. For any scalar downstream loss L, the corresponding vector–Jacobian product is ∇a L = −ηt Pt+ ∇z+ L. On every omegasel t, the full parameter-to-state Jacobian satisfies range(Dϕ z t+1,−) ⊆ Tzt+1,− Mt = ker Jt."

The finite-budget decoder uses the terminal state xT to allocate computation: "The allocation Aϕ (xT, B) = K, Ntest, π 0, αk K−1 k=0, ≺test, ≺con contains the two trace lengths, the initial Held–Karp potential π 0 ∈ Rn, positive ascent steps αk > 0, test order ≺test, and construction order ≺con. Held–Karp ascent converts the allocated initial potential and step sizes into lower-bound records through deterministic candidate-graph one-tree minimization. Construction accepts a candidate edge only when endpoint degrees remain at most two and the edge joins distinct components," producing a path forest that is closed into a Hamiltonian cycle and improved by LKH-3.

Deterministic verification converts records into reportable outputs: Construction first sets the common tour-cost threshold U = c(τ). For each Hk ∈ H, the verifier rebuilds Equation (12) from the original costs and reruns the deterministic minimum-one-tree calculation. The verified candidate-graph lower bound is Lmax c = max Lc (π k) over verified records. The verified edge-decision sets are defined as: "F out = eR: R ∈ Rver, δR = force, QR > U + tol(U) and F in = eR: R ∈ Rver, δR = forbid, QR > U + tol(U). A passing forced-edge record proves that every candidate-graph tour of cost at most U omits eR, so eR is safely removable, while a passing forbidden-edge record proves that every candidate-graph tour of cost at most U contains eR, so eR is required."

Theorem 3 states Output validity under arbitrary allocations: "Fix Gc, the original costs c, and a finite budget B, and assume Hver ̸= ∅. Suppose every reported one-tree record, edge-test record, and returned tour passes deterministic verification. Then every allocation satisfies Lmax c ≤ OPTEc, OPTE ≤ U. Every edge in F out is absent from all candidate-graph tours of cost at most U, and every edge in F in is present in all candidate-graph tours of cost at most U. Under the scope condition, Lmax c ≤ OPTEc = OPTE ≤ U."

The main comparison results show: "DualCert reaches a 0.0573% mean gap, which is 67.1% below NeuroLKH’s 0.1742% mean gap under the shared reference protocol. DualCert also reduces the NeuroLKH p90 and maximum gaps from 0.2525% and 0.3727% to 0.1243% and 0.1841%. The measured DualCert runtime is 9.55 batch-amortized seconds per instance. Verification accepts a candidate-graph lower bound on all 1,000 instances, and the aggregate edge-decision coverage is 81.46%."

Ablation results show: "No manifold and Degree only increase the mean gap by 0.1990 and 0.1809 percentage points, supporting the joint contribution of degree and SEC constraint geometry. Forward only and First-order update increase the gap by 0.1414 and 0.1325 points, supporting backward coupling and exact finite-step preservation. Alpha-only and Untrained allocation increase the gap by 0.0940 and 0.1132 points, supporting learned finite-budget allocation."

Scale and distribution shifts show: From TSP500 to TSP2000, runtime increases from 8.53 to 13.65 seconds, while the mean gap remains below 0.09% and the cross-scope residual remains below 0.94%. Coverage decreases from 86.77% to 70.67%. For Clustered-1000, DualCert attains a −0.0994% mean gap but only 30.95% coverage.

The paper concludes: "DualCert uses the current degree and manifold SEC equations to define the primal-slack state transition and its fixed-selection derivative. Repaired dual variables and violated SEC rows define the local cost field. The exact constrained mirror-descent step preserves manifold feasibility at finite step size. Its fixed-selection parameter derivative remains tangent to the manifold, while its local-cost-field derivative reuses the forward constraint operator. The terminal state allocates computation across Held–Karp ascent, candidate-graph edge tests, and tour construction. Deterministic verification accepts only recomputed outputs that satisfy the stated conditions."

Improvements to AI Systems:

1. Constraint-Coupled Learning Architecture: Implement a learning framework where optimization constraints (equality and inequality equations) directly define the geometry of the learned state space, rather than being soft penalties or post-hoc projections. The system maintains a primal-slack KKT manifold at every training step, ensuring all intermediate states satisfy the current active constraints exactly.

2. Exact Finite-Step Constrained Updates: Replace approximate gradient descent with an exact constrained mirror-descent step that preserves manifold feasibility at finite step sizes. This eliminates drift from constraint violations during training and inference, using a dual-residual solver (Newton-type) to find unique multipliers that keep the state on the manifold.

3. Shared Forward–Backward Constraint Operator: Reuse the same constraint Jacobian for both forward state transitions and backward gradient propagation (vector–Jacobian products). This reduces memory and compute overhead while ensuring that parameter gradients remain tangent to the constraint manifold, preventing invalid gradient directions.

4. Deterministic Verification Layer: Add a post-hoc verification module that recomputes all learned outputs (e.g., lower bounds, edge decisions) using original problem costs and deterministic algorithms. Only outputs passing this verification are reported, guaranteeing validity regardless of learned allocation or model errors.

5. Learned Computation Allocation via Terminal State: Train a policy that, given a fixed computational budget, allocates resources (e.g., number of ascent steps, edge tests, construction order) based on the terminal state of the learned process. This optimizes the trade-off between solution quality and runtime, adapting per instance.

6. Dual-Variable Repair for Cost Fields: Use repaired dual variables (from the KKT system) to construct a local cost field, combining reduced-cost components (from duals) with penalty components (from violated constraints). This provides a principled, constraint-aware gradient signal for learning.

7. Finite-Budget Decoder with Deterministic Fallbacks: Implement a decoder that uses learned preferences to guide a deterministic combinatorial solver (e.g., Held–Karp ascent, LKH-3) but always falls back to exact verification of lower bounds and edge decisions, ensuring no invalid outputs are produced.

What the Improved AI System Can Do:

• Solve large-scale combinatorial optimization problems (e.g., TSP with 1000+ nodes) with near-optimal gaps (0.057% from LKH-3) while providing provably valid lower bounds and verified edge decisions for every instance.

• Operate under strict computational budgets, automatically allocating time between search, refinement, and verification to maximize quality per second.

• Guarantee that all reported outputs (tour costs, lower bounds, edge inclusions/exclusions) are mathematically correct, even if the learned model makes errors, due to the deterministic verification layer.

• Maintain constraint feasibility at every step of learning and inference, avoiding common issues like constraint drift or invalid intermediate states.

• Generalize across problem sizes (500–2000 nodes) and distributions (uniform, clustered) with graceful degradation in coverage but maintained validity.

• Provide interpretable, verifiable certificates (e.g., this edge is required in all tours under cost U) that can be used for safe decision-making in logistics, network design, or resource allocation.