Neural solvers for routing problems such as the Traveling Salesman Problem now transfer well from small to large instances. The strongest of them build a tour one city at a time and are trained by imitation, copying optimal tours on 100-city instances, and then run unchanged on 1,000 cities. That training recipe has a hidden cost: every training tour must come from an exact solver. Exact solving is cheap for 100-city tours but becomes the bottleneck for harder variants with capacities or time windows, and for any attempt to supervise at larger sizes. This note proposes replacing the single exact tour with something much cheaper and noisier: a handful of fast, imperfect heuristic tours of the same instance. At each construction step, the next cities chosen by any of these tours form a candidate set of plausible moves. Some candidates are good and some are mistakes.
Learning from candidate sets that contain false positives is a problem the multi-label learning community has already worked on. In that setting, "partial multi-label learning" means each example comes with a candidate label set known to contain some wrong labels, and the standard remedy is to separate good from bad labels using how labels depend on one another. Here the dependencies are concrete. Edges that keep appearing together across good tours support each other, and edges that compete for the same city exclude each other. The claim is that per-instance dependency modeling over heuristic-tour edges recovers supervision close to exact-solver quality at a fraction of the labeling cost. Because the dependency graph is rebuilt for every instance rather than learned as fixed global statistics, it should not inherit the brittleness under scale shift that fixed co-occurrence models show.
Core Claim
Scale-robust constructive solvers do not need optimal demonstrations. They need an accurate target distribution over acceptable next moves. Such a target can be built distantly from an ensemble of cheap heuristics. The noise in that ensemble is structured, so it can be removed by propagating confidence over a per-instance graph of edge co-occurrence and mutual exclusion. The observable consequence is specific. At a matched CPU budget for generating labels, a heavy-decoder or tail-subproblem policy trained on disambiguated heuristic candidate sets should approach the 1,000-city optimality gap of the same policy trained on exact tours. It should clearly beat two cheaper alternatives: imitating the single best cheap tour, and averaging the candidate set uniformly. A second consequence is that cheap labels make supervision at intermediate sizes (200 to 500 cities) affordable. If supervising there improves transfer to TSPLib and CVRPLib, the idea pays off beyond merely matching the exact-label baseline.
How This Relates to Prior Work
The architectures come from two zero-shot scale-transfer methods that both depend on exact small-scale solutions. LEHD pairs a light encoder with a heavy decoder that recomputes embeddings at every step, and trains it on sub-paths sampled from optimal 100-city tours. BQ-NCO redefines the decision state as the remaining unvisited subproblem and trains by imitating near-optimal demonstrations. We reuse both as policies unchanged and replace only their supervision. In that sense they supply the method, and their reliance on exact solvers motivates the work. That reliance is a modern version of the label-generation bottleneck first noted for Pointer Networks.
The disambiguation mechanism comes from PLAIN. PLAIN alternates between training a network and propagating pseudo-labels over two graphs, one linking similar instances and one capturing label correlations, and shows that this beats two-stage filter-then-train pipelines. We transplant its alternating loop. We change what the graph is built over: PLAIN builds one label graph over a fixed category set, whereas ours is an edge graph built fresh for each instance, so its size grows with the problem. Medical work such as FACT, which aligns image features to anchors placed on a fixed comorbidity graph, belongs to the same lineage and has the same fixed-vocabulary limitation.
Two lines of work constrain the design. Correlative and Discriminative Label Grouping warns that leaning on observed co-occurrence overfits when distributions shift. A scale-transfer setting is precisely such a shift, which is why our dependencies are computed per instance and never stored as model parameters. Probing Neural Combinatorial Optimization Models finds that LEHD's transfer rests on two embedding dimensions. It also shows that a sparsity penalty moves the TSPLib gap only from 5.26% to 4.94%. Supervision quality is therefore one of the few levers that remain largely unexplored.
The closest work on removing the label bottleneck in other ways does not address this setting. Unsupervised tour losses (Unsupervised Training for Neural TSP Solver) and duality-based instance synthesis (DIG-MILP) avoid labels altogether, or avoid solver calls when generating instances. Neither studies imitation targets for constructive policies that must transfer across scales.
Research Program
For each training instance we run $K$ cheap heuristics, roughly 8 to 16 tours. These are nearest-neighbor and insertion constructions followed by short, randomly restarted 2-opt local search. For CVRP the analogue is savings constructions with short local search, all kept far below the budget of a full exact or HGS run. Pooling the edges of all $K$ tours gives a candidate edge set $E$.
We then compute a confidence for each edge. Let $r^{(0)}_e$ be the length-weighted frequency of edge $e$ across the $K$ tours. Let $C$ be the matrix whose entry $C_{ee'}$ is the fraction of tours containing both $e$ and $e'$, normalized so that the confidence mass leaving each city is shared among that city's candidate edges; this sharing implements mutual exclusion. Let $p_\theta$ be the current policy's own edge probabilities. Following PLAIN's alternation, the edge confidences $r$ are refined each epoch:
$$ r \leftarrow (1-\alpha-\beta)\, r^{(0)} + \alpha\, C r + \beta\, p_\theta , $$
Here $\alpha$ weights support from co-occurring edges and $\beta$ weights the model's own belief. At a construction state with current city $u$ and unvisited set $U$, the imitation target is $q(v \mid s) \propto r_{(u,v)}$ for candidates $v \in U$, and the policy is trained with cross-entropy against $q$. We keep the sub-path sampling of LEHD and the tail-subproblem state of BQ-NCO intact, so the supervision change is the only difference from those methods. An optional instance-similarity term in the style of PLAIN, which links similar tail subproblems, is treated as an ablation rather than as a core component, because tuning burden is a known weakness of PLAIN.
Two analyses accompany training. The first is coverage: on held-out 100-city instances with Concorde tours, how often does the optimal next city appear in the candidate set at all? The second is precision: how often is the argmax of $q$ the optimal next city, measured before and after propagation? Coverage bounds what any disambiguation can achieve, so we measure it before building anything else.
Baselines
The naive reference point is a policy with identical architecture trained by imitating the single best cheap heuristic tour per instance. It gets the same label-generation budget and the same training steps, and it isolates whether candidate sets help at all. Pure reinforcement learning with POMO serves as the label-free reference. LEHD reports that POMO exceeds a 40% gap on TSP1000.
The strongest existing methods are LEHD trained on exact tours, which reports a 0.719% optimality gap on TSP1000, 0.921% on CVRP1000, and a 1.5% average gap on TSPLib, and BQ-NCO, which reports about 1.38% on TSP1000 with greedy rollout and about 4.8% on CVRPLib. We retrain both with our code so that architecture, optimizer, training steps and evaluation-time search budget are identical across label sources, and we also quote the published figures. For synthetic CVRP1000 under BQ-NCO, no reported result was found on Lacuna, so our retrained number becomes the reference. The exact-label arm is a ceiling under unlimited labeling, not a competitor at equal cost. "Beating" it means matching its TSP1000 gap to within 0.3 percentage points at no more than a quarter of its labeling CPU time. Alternatively, it means beating it outright when both arms are capped at the same labeling budget, a cap that forces the exact arm to use fewer instances.
Two ablations isolate the key ingredient. The first uses a uniform target over the candidate set. The second uses the length-weighted target $r^{(0)}$ with no propagation, which corresponds to $\alpha=\beta=0$. The full method must beat both by a margin larger than the spread across seeds. Otherwise the dependency modeling is not doing the work.
Why not just…?
Why not just imitate one good heuristic such as LKH or HGS? On 100-city TSP a strong heuristic is essentially optimal, and this is the most serious threat to the proposal. If labels are cheap enough to make with a strong heuristic, there is nothing to disambiguate. We therefore frame the contribution around a labeling budget. We sweep CPU time per instance from very cheap (short 2-opt) to strong-heuristic levels and plot the TSP1000 and CVRP1000 gaps against that budget for single-tour imitation and for our method. If the two curves meet at every budget, the idea has failed, and we will say so. We expect the gap between them to be largest on CVRP and at intermediate training sizes, where strong solvers are slow.
Why not just average the candidate tours uniformly? Uniform soft targets already pass along the ensemble's disagreement and cost nothing extra. They are the ablation above. The argument against them is that tours sharing a bad local-search basin vote together, and only co-occurrence structure can reveal that. The precision diagnostic tests this directly: propagation should raise optimal-move precision on held-out instances. If it does not, uniform averaging is the honest answer.
Why not skip labels and train with reinforcement learning or an unsupervised tour-length loss? Label-free training sidesteps the bottleneck entirely. Its documented record across scales is poor, though: POMO exceeds 40% on TSP1000 per LEHD. The file also notes that simple penalty losses fail in tightly constrained spaces, which led to primal-dual schemes (Van Hentenryck et al.). We include POMO and the unsupervised loss of Draguns et al. on the heavy-decoder architecture as baselines. This tells us whether architecture alone closes the gap.
Why not clean the candidate labels offline and then train normally? A two-stage filter is simpler. PLAIN, however, reports that such pipelines lock in early filtering mistakes. Running the update with $\beta=0$ and a single pass of propagation reproduces the offline variant, so the comparison comes almost for free.
Proposed Experiments
We train on 100-city uniform TSP and CVRP, and test zero-shot on 200, 500 and 1,000 cities, on TSPLib, and on CVRPLib, reporting optimality gap against Concorde or HGS under greedy and fixed-budget re-construction search.
The first decisive check precedes any training. If cheap-ensemble coverage of the optimal next move falls below roughly 90% on 100-city instances, the candidate-set premise fails and the project switches to stronger cheap heuristics before going further.
The second check is the matched-budget curve described under the first alternative. It is the main result.
The third check trains on cheap labels generated at 300 to 500 cities, which is affordable only because the labels are cheap. We then ask whether this improves TSPLib and CVRPLib gaps over 100-city exact supervision. This tests whether label cost, rather than architecture, limits real-world transfer.
The fourth check probes for the overfitting risk raised by label grouping work. We replace the per-instance matrix $C$ with a co-occurrence matrix averaged over training instances, indexed by rank of distance between cities. If this global version degrades more at 1,000 cities than the per-instance version, that supports the design choice to recompute dependencies for each instance.
References
- Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalization
- BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimization
- Pointer Networks
- Deep Partial Multi-Label Learning with Graph Disambiguation
- FACT: Fuzzy Alignment with Comorbidity Topology for Reliable Multi-Label Medical Image Diagnosis
- Correlative and Discriminative Label Grouping for Multi-Label Visual Prompt Tuning
- Probing Neural Combinatorial Optimization Models
- Unsupervised Training for Neural TSP Solver
- DIG-MILP: a Deep Instance Generator for Mixed-Integer Linear Programming with Feasibility Guarantee
- Self-Supervised Primal-Dual Learning for Constrained Optimization