Research map / Architectures and efficiency / Attention and transformers

LINC: Decoupling Local Consequence Scoring from Hidden Matching in Constructive Neural Routing

NeurIPS 2026 · Architectures and efficiency › Attention and transformers · approach: State space and recurrent sequence models · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes LINC, a decoder-side candidate scoring architecture that explicitly computes one-step routing consequences (travel, waiting, slack, timing) and scores them with a state-conditioned shared linear comparator, improving PolyNet/POMO on TSP, CVRP, and CVRPTW.

Problem

Constructive neural routing solvers must implicitly reconstruct deterministic one-step transition consequences (travel, waiting, timing slack, capacity) from a hidden decoder context, which hurts feasibility-sensitive routing and generalization under distribution and scale shift.

Approach

Compute explicit candidate-level local consequence features from the known transition and score them with a shared linear comparator whose weights are generated from the decoder context and a feasible-set summary, combined with standard context-key attention via a gate.

Key results

• On Solomon-100 CVRPTW, LINC unguided achieves 7.3% gap vs. 13.8% for PolyNet; on Homberger-200 it reaches 14.71% vs. 38.14%.
• No-retraining scale transfer at CVRPTW n=1000: LINC 42472.66 vs PolyNet 86869.17 (-51.11%); CVRP n=1000: -47.07% relative to PolyNet.
• TSP100 gap 0.000% for both PolyNet and LINC; CVRP100 gap reduced from 0.50% to 0.48%, so gains on TSP/CVRP in-distribution are small.

Surprising findings

• On TSP and CVRP in-distribution, gains over PolyNet are marginal (e.g., TSP100 0.000% for both), with the advantage concentrated on CVRPTW and larger scales.
• Removing GateAttn slightly improves the objective (-0.03%), indicating that component is neutral in the ablation.

Limitations

• Autoregressive single-route-prefix construction cannot coordinate multiple routes in parallel and may suffer early commitment or route imbalance.
• Consequence features must be hand-specified for each routing variant.
• Only one-step consequences are used; no multi-step lookahead.

Experimental setup

Datasets: TSPLIB50-200 CVRPXML100 Solomon-100 Homberger-200 synthetic TSP100/CVRP100 random instances procedural CVRPTW generator

Benchmarks: Synthetic-100 CVRPTW Solomon-100 Homberger-200 TSP100 TSP150 CVRP100 CVRP150 TSPLIB50-200 CVRPXML100 Homberger-400/600/1000 (scale transfer) TSP500/1000 and CVRP500/1000 (scale transfer)

Metrics: objective (mean travel distance) optimality gap wall-clock time

Baselines: POMO PolyNet Poppy SGBS DPDP MDAM DACT BQ-NCO Concorde LKH3 HGS PyVRP

Builds on: POMO PolyNet Attention Model SGBS BQ-NCO

Closest papers by meaning

• Memory-Enhanced Neural Solvers for Routing Problems (NeurIPS 2025 · similarity 0.88)
• Learning to Handle Complex Constraints for Vehicle Routing Problems (NeurIPS 2024 · similarity 0.87)
• Dynamic Latent Routing (NeurIPS 2026 · similarity 0.87)
• Rethinking Light Decoder-based Solvers for Vehicle Routing Problems (ICLR 2025 · similarity 0.87)
• Multi-Task Vehicle Routing Solver via Mixture of Specialized Experts under State-Decomposable MDP (NeurIPS 2025 · similarity 0.86)
• Improving Generalization of Neural Combinatorial Optimization for Vehicle Routing Problems via Test-Time Projection Learning (NeurIPS 2025 · similarity 0.86)