PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning the Travelling Salesperson Problem Requires Rethinking Generalization

Chaitanya K. Joshi, Quentin Cappart, Louis-Martin Rousseau, Thomas Laurent

arXiv:2006.07054v6cs.LGstat.ML

TL;DR

Large-scale TSP remains difficult for neural solvers, whose performance degrades beyond training sizes and can lag simple heuristics. This paper unifies architectures, inductive biases, learning paradigms, and evaluation protocols to study zero-shot generalization, finding that extrapolation requires redesigning the pipeline.

  • Problem

    Neural TSP solvers remain inefficient beyond graphs with a few hundred nodes, while their generalization to larger practical instances is still an open question.

  • Method

    The paper builds a unified end-to-end neural combinatorial optimization pipeline to compare inductive biases, architectures, learning algorithms, and evaluation protocols for zero-shot transfer.

  • Results

    The experiments find that GNN layers, normalization, graph construction, learning paradigms, and evaluation protocols require explicit redesign for out-of-distribution generalization; autoregressive decoding generalizes better but costs more inference time.

  • Takeaways & Limitations

    Learning efficiently on small TSP instances and transferring policies to larger graphs is a practical alternative to expensive large-scale training, while model design must account for distribution shifts.

  • Takeaways & Limitations

    Training on TSP200 was intractable within the computational budget, so the study mainly used variable TSP20-50 for rapid experimentation.

Abstract

from arXiv · show

End-to-end training of neural network solvers for graph combinatorial optimization problems such as the Travelling Salesperson Problem (TSP) have seen a surge of interest recently, but remain intractable and inefficient beyond graphs with few hundreds of nodes. While state-of-the-art learning-driven approaches for TSP perform closely to classical solvers when trained on trivially small sizes, they are unable to generalize the learnt policy to larger instances at practical scales. This work presents an end-to-end neural combinatorial optimization pipeline that unifies several recent papers in order to identify the inductive biases, model architectures and learning algorithms that promote generalization to instances larger than those seen in training. Our controlled experiments provide the first principled investigation into such zero-shot generalization, revealing that extrapolating beyond training data requires rethinking the neural combinatorial optimization pipeline, from network layers and learning paradigms to evaluation protocols. Additionally, we analyze recent advances in deep learning for routing problems through the lens of our pipeline and provide new directions to stimulate future research.

1 Introduction

TSP is difficult to solve and learn at practical scales, exposing weak out-of-distribution generalization in neural solvers. The paper unifies architectures and learning paradigms to study how small-instance training, model design, and evaluation affect scalability.

  • Motivation: TSP is NP-hard and becomes intractable to solve optimally at large scales, despite major practical applications.Concorde combines linear programming with handcrafted heuristics to solve instances up to tens of thousands of nodes, but at prohibitive cost.
  • Motivation: End-to-end neural solvers perform competitively on trivially small instances but have not established practical generalization to larger graphs.For graphs beyond a few hundred nodes, the gap between GNN-based solvers and simple non-learnt heuristics is especially evident for TSP.
  • Motivation: 12.8 Million TSP200 training samples over 500 hours still failed to reliably outperform a simple insertion heuristic.This illustrates both the sample-efficiency and wall-clock challenges of directly learning on large graphs.
  • Proposed direction: Learning efficiently on TSP20-TSP50 and transferring the policy offers a cheaper route to zero-shot generalization or rapid finetuning on larger graphs.The paper frames inductive biases, architectures, and learning paradigms as central design choices for practical solvers.
  • Contributions: The unified pipeline provides a principled investigation of zero-shot generalization and indicates that neural combinatorial optimization must explicitly account for it.The framework also characterizes recent routing advances and supplies datasets and code online.
  • Findings: Generalization improves with redesigned aggregation and normalization, autoregressive decoding, and suitable learning paradigms, but autoregressive inference is costlier.Expert supervision supports post-hoc search, whereas reinforcement learning scales better with additional computation and needs no labelled data.

2 Related Work

Prior work applies machine learning to combinatorial optimization through several relationships with optimization, including end-to-end neural approximation. TSP remains a particularly difficult testbed because strong size generalization is not consistently demonstrated, motivating unified architectural analysis.

  • Neural Combinatorial Optimization: Machine learning for combinatorial optimization spans learning alongside optimization, configuring optimization algorithms, and end-to-end approximate solving.The paper places its work in the neural combinatorial optimization category.
  • Neural Combinatorial Optimization: End-to-end TSP solvers commonly combine GNNs with sequence-to-sequence learning and decode tours autoregressively or non-autoregressively.Autoregressive models construct solutions step by step, while non-autoregressive models produce them in one shot.
  • Related problems: Related architectures have also been applied to Vehicle Routing, Maximum Cut, Minimum Vertex Cover, Boolean Satisfiability, and Graph Coloring.The paper uses TSP as an illustration for characterizing neural combinatorial optimization architectures.
  • Generalization: Unlike some non-sequential problems such as SAT, MaxCut, and MVC, TSP architectures do not show strong generalization to larger or more complex instances.This contrast establishes TSP as a challenging benchmark for neural combinatorial optimization.
  • Combinatorial Optimization and GNNs: GNN research on combinatorial problems examines expressive power, learned graph algorithms, and how expressiveness relates to generalization capability.This line of work includes provably more expressive GNNs and improved understanding of their generalization.
  • Novel Applications: Combinatorial learning methods have also supported novel optimization applications where exact solvers are expensive or intractable.Examples include physical sciences and computer architecture, with autoregressive and non-autoregressive models providing different inductive biases.

3 Neural Combinatorial Optimization Pipeline

The pipeline unifies graph formulation, embedding, decoding, and policy learning for end-to-end TSP solvers. It supports sparse or fully connected graphs, autoregressive or non-autoregressive decoding, and supervised or reinforcement learning.

  • 3.1 Problem Definition: TSP instances are represented as fully connected city graphs that may be sparsified with k-nearest-neighbor heuristics.Sparsification reduces pairwise computation and can reduce the search space for large instances.
  • 3.3 Solution Decoding: Predicted edge probabilities become discrete tour decisions through greedy search, beam search, or sampling.Broader search or more samples trade increased runtime for improved solution quality.
  • 3.5 Policy Learning: The unified pipeline trains models either by imitating optimal solver tours with supervised learning or by minimizing tour length with reinforcement learning.The reinforcement-learning formulation uses policy gradients and a baseline to reduce gradient variance.
  • 3.2 Graph Embedding: GNN encoders compute node representations by recursively aggregating neighbor features across stacked message-passing layers.The encoder uses node coordinates and edge distances as projected input features, with aggregation, normalization, and edge gating choices.
  • 3.3 Solution Decoding: Non-autoregressive decoders independently predict whether edges belong to the TSP solution, whereas autoregressive decoders construct tours through step-by-step graph traversal.The two decoding paradigms encode different inductive biases: NAR predictions are independent, while AR decoding explicitly models sequential ordering.

4 Experimental Setup

The experiments study zero-shot generalization by training primarily on small TSP instances and evaluating across sizes through a held-out optimality-gap benchmark. They compare pipeline components and learning settings against a non-learnt insertion heuristic.

  • Training Setup: Controlled experiments train on variable TSP20-50 graphs and measure generalization across larger sizes, including TSP200.The study also compares training on fixed graph sizes up to TSP100.
  • Training Setup: The supervised-learning dataset contains 1,280,000 samples with Concorde-generated optimal tours, while reinforcement learning uses 128,000 newly generated samples per epoch without optimal solutions.Both paradigms use Adam with batch size 128 and learning rate 1e−4; supervised training runs for 10 epochs and reinforcement learning for 100.
  • Model Configuration: The best-model configuration uses autoregressive decoding with a Graph ConvNet encoder and approximately 350,000 trainable parameters per model.Autoregressive models use three GNN layers, while non-autoregressive models use four, with hidden dimension d = 128.
  • Evaluation: Evaluation uses a held-out set of 25,600 TSPs spanning TSP10 through TSP200 and measures the optimality gap relative to Concorde.Models are compared with beam search of width 128 and 99%-ile confidence intervals, including against a furthest-insertion heuristic.

5 Results

Across controlled experiments, generalization beyond training sizes depends on evaluation protocol, graph construction, encoder design, decoder choice, normalization, and learning paradigm. The strongest patterns favor distribution-aware representations and sequential decoding, while faster alternatives often trade away generalization.

  • 5.1 Does learning from variable sizes help generalization?: Variable-size training preserves performance across seen sizes but does not reliably improve generalization to larger graphs.TSP20 models fail on large sizes, while TSP100 models generalize poorly to trivially easy sizes.
  • 5.2 What is the best graph sparsification heuristic?: Constant graph diameter through sparsification generalizes better to larger problems than full graphs, whereas fixed node degree does not.The study therefore uses sparse 20%-nearest-neighbor graphs in subsequent experiments.
  • 5.3 What is the relationship between GNN aggregation functions and normalization layers?: MEAN and MAX aggregation outperform more expressive alternatives on larger graphs because they better tolerate shifts in node degree and neighborhood statistics.SUM can generalize worse than structure-agnostic MLPs, producing unstable or exploding node embeddings under distribution shift.
  • 5.3 What is the relationship between GNN aggregation functions and normalization layers?: BatchNorm with batch statistics and LayerNorm generalize better across graph sizes than standard BatchNorm, which can underperform having no normalization.These schemes account for changing graph statistics across sizes.
  • 5.4 Which decoder has a better inductive bias for TSP?: Autoregressive decoding generalizes significantly better than non-autoregressive decoding, while non-autoregressive decoding is substantially faster at inference.The speed advantage is especially pronounced when autoregressive decoding re-embeds the graph at every step.
  • 5.5 How do learning paradigms impact the search phase?: Reinforcement learning performs better with greedy decoding, whereas supervised-learning models improve with beam search or sampling.Teacher forcing produces less confident predictions and poorer greedy decoding but makes the probability distribution more amenable to beam search.

6 Recent Case Studies and Future Work

Recent routing research improves out-of-distribution generalization by redesigning neural components, search procedures, and learning paradigms, often coupling learned models with structural problem knowledge or classical search.

  • Future Work: The unified pipeline highlights that training and inference choices should be tightly coupled, including the choice between greedy, beam, and sampling-based search.The rollout baseline favors confident greedy behavior, while supervised learning produces distributions more amenable to beam search and sampling.
  • Recent Case Studies: Respecting routing symmetries and geometric structure may improve generalization by incorporating invariances and cyclical-route constraints into architectures or learning paradigms.Relevant symmetries include starting-city invariance, rotations, reflections, and translations.
  • Recent Case Studies: Replacing one-shot graph search with dynamic programming or Monte-Carlo Tree Search strengthens the symbolic component while retaining the learned encoder.The GNN-plus-MCTS framework generalizes to TSPs with up to 1000 nodes by representing large instances as same-sized subgraphs before merging predictions.
  • Recent Case Studies: Stronger coupling between neural and symbolic search components is essential for out-of-distribution generalization.This conclusion follows from methods that combine learned predictions with scale-robust search procedures.
  • Recent Case Studies: Local-search learning can generalize better to larger instances by using neural guidance within classical search algorithms designed to work across scales.This approach requires hand-designed local-search heuristics, whereas constructive methods are easier to adapt by enforcing constraints during decoding and search.
  • Future Work: Future work includes fine-tuning on a small number of larger instances, treating generalization as meta-learning, and pre-training across routing problems.Multi-task pre-training could transfer representations from established problems such as TSP and CVRP to understudied constrained routing problems.

7 Conclusion

The paper studies why end-to-end learning-driven TSP solvers struggle to scale and evaluates an alternative based on small-instance training followed by transfer to larger graphs. Its findings indicate that zero-shot generalization requires redesigning architectural, graph, learning, and evaluation choices.

  • Conclusion: End-to-end TSP solvers perform promisingly on small instances, but scaling them to real-world sizes remains open because large-graph training is costly and difficult.The paper frames this as a central challenge for learning-driven combinatorial optimization.
  • Conclusion: Training on trivially small TSP instances and transferring the learned policy offers an alternative to expensive large-scale training through zero-shot generalization or fast fine-tuning.The approach targets larger and more complex instances without requiring full training at those scales.
  • Conclusion: The unified pipeline provides a principled investigation showing that GNN layers, normalization, graph sparsification, learning paradigms, and evaluation protocols must account explicitly for distribution shifts.The study also characterizes recent routing advances and identifies directions for future research.

A Additional Context for Figure 1

The paper motivates its experiments by showing that large-scale TSP training is computationally difficult and that classical insertion heuristics remain strong baselines. Efficient training on small variable-size instances can nevertheless support transfer to larger graphs.

  • Additional Context for Figure 1: The experimental setup compares identical reinforcement-learning models trained on 12.8 million TSP instances, using autoregressive decoding and a Graph ConvNet encoder.The encoder uses MAX aggregation and LayerNorm, with the TSP20-50 model trained using a greedy rollout baseline.
  • Additional Context for Figure 1: Furthest insertion constructs a tour by inserting each node between tour nodes so that its distance to the nearest tour node is maximized.The heuristic serves as the paper’s reference for good generalization.
  • Additional Context for Figure 1: Training directly on TSP200 is intractable within the computational budget, while efficient TSP20-50 pre-training enables zero-shot transfer to TSP200.Within that budget, furthest insertion still outperforms the best learned models.
  • Additional Context for Figure 1: TSP is studied because it is a longstanding, practically relevant testbed for general-purpose techniques in applied mathematics and combinatorial optimization.Its applications include logistics, genetics, and scheduling.
  • Additional Context for Figure 1: Unlike some non-sequential problems, TSP has not shown strong generalization from training instances to larger and more complex instances.Classical graph reduction, tree search, and post-hoc local search have helped enable generalization in related settings.
  • Additional Context for Figure 1: Furthest insertion outperforms or matches state-of-the-art TSP approaches above tens of nodes despite those approaches using more computation and data.This comparison reinforces the difficulty of scaling learned TSP solvers beyond small graphs.

B Hardware and Timings

The paper reports approximate training and inference timings across TSP sizes and search settings, while noting that hardware, libraries, and implementation choices affect fair comparisons.

  • Hardware and Timings: Timing comparisons are implementation-dependent because libraries, hardware configurations, and programmer skill can affect research-code measurements.Experiments used PyTorch, an Intel Xeon CPU, and four Nvidia 1080Ti GPUs.
  • Hardware and Timings: Approximate timing measurements cover training on 12.8 million samples and inference on 1,280 samples across TSP sizes and search settings.The reported settings include greedy search, beam search with width 128, and sampling 128 solutions for supervised- and reinforcement-learning models.

C Learning Paradigms and Amenity to Search

Learning paradigms shape both greedy predictions and the usefulness of search over candidate tours. Rollout-trained models produce sharper greedy selections, whereas less sharp distributions can support more diverse and better tours under broader search.

  • Learning paradigms: Rollout-trained models make more confident greedy selections than supervised-learning models across TSP sizes.The comparison uses histograms of greedy-selection probabilities for identical models trained with SL and RL.
  • Solution search: Less sharp probability distributions yield more diverse tours as beam width or sampling effort increases.Repeated sampling or retaining the top-b solutions from sharper distributions tends to produce similar tours.
  • Solution search: More confident predictions do not automatically produce better solutions beyond the training sizes.The reported advantage of less sharp distributions concerns comparative optimality gaps, especially on larger unseen TSP instances.

D Visualizing Node and Graph Embedding Spaces

Embedding-space diagnostics compare how node and graph representations change as TSP size grows beyond training. Stable node statistics are associated with the strongest configuration, while graph embeddings converge and lose structural differentiation at larger sizes.

  • Node Embedding Space: Figures 13 and 14 plot node embedding norms and pair-wise distances across TSP sizes.These figures provide the distribution-based comparison used to assess node-space stability.
  • Embedding-space diagnostics: The analysis tracks embedding magnitudes with ℓ2 norms and separation with pair-wise distances across TSP sizes.Distribution plots summarize how these statistics vary as problem scale changes.
  • Node Embedding Space: GNN-Max maintains the most stable node embedding norms and intra-graph pair-wise distances across TSP sizes.GNN-Sum and GNN-Max + learnt BN instead show fluctuating or monotonically increasing node norms as size increases.
  • Graph Embedding Space: Figures 15 and 16 assess graph embedding norms and pair-wise distances, while Figure 17 visualizes graph embedding spaces with size-coded colors.The PCA comparison includes TSP10, TSP20, TSP50, and TSP200.
  • Graph Embedding Space: Graph embedding magnitudes shrink toward a single value and graph embeddings move closer together as graph size increases.Batch-statistics BatchNorm keeps graph magnitudes within the training-range behavior, unlike standard BatchNorm's monotonic increase beyond training sizes.
  • Graph Embedding Space: PCA shows that large-size graph embeddings have similar magnitudes and lie extremely close together, limiting graph differentiation.The authors interpret this as insufficient global structural context in current decoders.

E Extra Results

The extra results examine search settings, decoder architecture, aggregation, training baselines, scaling, and prediction visualization. They show that architecture and learning choices affect generalization and search performance, while larger models mainly improve fit to the training data.

  • NAR Decoders and Aggregation Functions: GNN encoders generalize better than Transformers and MLPs in non-autoregressive architectures.For autoregressive decoding, sequential inductive bias generalizes well with both GNN and structure-agnostic encoders.
  • Critic baseline: The rollout baseline outperforms the critic baseline under both greedy and beam search for identical models.The actor-critic setup was not separately tuned and generally requires more parameter tuning than the rollout baseline.
  • Scaling computation for AR and NAR architectures: Larger models up to 1.5 Million parameters fit the training dataset better, with the effect especially evident for NAR architectures.The authors suggest that heavily overparameterized NAR networks can memorize small TSP training patterns without generalizing beyond training sizes.
  • Prediction visualization: The paper provides visualization tools for model predictions and heatmaps on TSP20 and TSP50 instances.It also proposes visualizing reduced costs as a debugging aid and possible inexpensive supervision signal.
Loading 2006.07054v6…