Geometric Self-Supervised Pre-training for Neural Combinatorial Optimization

arXiv:2608.00270 · cs.AI · Submitted 2026-08-17 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Next we'll be talking about the paper "Geometric Self-Supervised Pre-training for Neural Combinatorial Optimization".

Jane: The paper was written by David Aguado, Daniel Fuertes, Carlos R. del-Blanco and Fernando Jaureguizar from Universidad Politécnica de Madrid.

Tom: Stay tuned as we take you through the paper and discuss its implications.

Title and Authors: Tom: Welcome back to the show, everyone! Today we're digging into a fresh arXiv paper that's got a real mouthful of a title: "Geometric Self-Supervised Pre-Training for Neural Combinatorial Optimization." Jane, I'll be honest, when I first read that title I had to sound it out twice.

Jane: You and me both, Tom. But once you unpack it, it's actually a pretty elegant idea. So "combinatorial optimization" is the fancy math term for problems where you have to find the single best arrangement out of a huge number of possibilities. Think of the classic Traveling Salesman Problem — you've got a bunch of cities and you need to find the shortest route that visits each one exactly once and comes back home.

Tom: Right, and that's the TSP they keep abbreviating in the paper. It's one of those famous NP-hard problems, which means the time to solve it perfectly explodes as you add more cities. The authors are from Universidad Politécnica de Madrid — David Aguado and his colleagues — and they're trying to teach a neural network to solve this problem really fast, even when it's never seen such a large map before.

Jane: And that's where the "self-supervised pre-training" part comes in. You see, in fields like computer vision, researchers have figured out that if you let a model look at tons of unlabeled images first, it learns general features — shapes, edges, textures — before you fine-tune it on a specific task. The authors here are asking: can we do the same thing for routing problems?

Tom: But here's the catch they identify in the paper. Most existing graph pre-training methods rely on rich features — like molecular structures with atom types, or social networks with user profiles. But a TSP instance is just a bunch of 2D coordinates. There's no extra information to mask or predict. So the standard tricks don't transfer.

Jane: Exactly. So their whole contribution is figuring out what kind of "pretext task" makes sense for a graph that only has spatial coordinates. And their answer is geometry itself. They use transformations — rotations, reflections, translations — to teach the network that the optimal route doesn't change when you spin the map around.

Tom: That's such a clean insight. If you rotate a map, the shortest route stays the same, right? So they force the network to learn representations that are invariant to those rotations. And the results they report are pretty striking — a seven point two three percent improvement in tour length when extrapolating to massive one thousand-node instances compared to training from scratch.

Jane: And that's the zero-shot extrapolation scenario, which is the real killer in this field. Most neural solvers train on fifty nodes and fall apart when you hand them five hundred or one thousand. The fact that this pre-training helps bridge that gap is genuinely exciting.

Tom: I'm already curious about how they actually implemented this. What transformations worked, which ones backfired? I think we need to dig into the methodology next.

Jane: Absolutely. Because the paper actually found that not all geometric tricks are created equal — some of them made things worse. Let's get into that.

Summary: Tom: So we're back with "Geometric Self-Supervised Pre-Training for Neural Combinatorial Optimization," and Jane, I want to pick up on that thread you just dropped. The paper doesn't just say "apply any transformation." They ran an ablation study, and the results are honestly fascinating.

Jane: They are. So the architecture itself is pretty standard for this field — a GatedGCN encoder paired with an attention-based decoder, trained with reinforcement learning. The novelty is entirely in that pre-training phase. They take a TSP instance, apply a geometric transformation, and then use a contrastive loss called InfoNCE to make the model produce similar embeddings for both the original and the transformed version.

Tom: And that's the self-supervised part — no labels needed. The model just learns that these two views are the same problem in disguise. But here's where it gets interesting. They tested four strategies: rotation, reflection, translation, and combinations. And translation — just shifting the whole map by a small amount — actually made things worse.

Jane: Which is so counterintuitive at first glance. But their explanation makes sense. In a dense graph with a thousand nodes, two nodes might be extremely close together. If the model learns that a coordinate and a slightly shifted coordinate are equivalent, it loses the ability to distinguish between those nearly-overlapping nodes. That destroys its local routing precision.

Tom: Right, so translation teaches the wrong invariance. But rotation and reflection — those preserve all pairwise distances exactly, so they teach the right invariance. And the best combination was rotation plus reflection together. That gave them a fifty-five point one percent optimality gap at TSP1000 compared to Concorde, versus sixty-seven point two percent for the baseline with no pre-training.

Jane: And for listeners who might not be deep in the weeds, the optimality gap just means how much longer the neural solver's tour is compared to the mathematically perfect solution. So fifty-five percent sounds bad, but it's actually a massive improvement over the sixty-seven percent baseline. And the inference time is the real story — the neural solver does it in half a second, while Concorde takes one hundred seventy-five seconds.

Tom: That's two orders of magnitude faster. And that's the whole pitch of neural combinatorial optimization — you trade a bit of optimality for a massive speedup. But the generalization problem was always the bottleneck, and this paper directly attacks that.

Jane: And they also did something clever with the training data. Instead of training on a fixed size, they sampled instances from a uniform distribution between twenty and fifty nodes. That scale variability acts as a regularizer, forcing the model to learn size-agnostic representations.

Tom: But wait — the paper also found a trade-off there, right? For the truly massive instances, the variable-scale model actually underperformed a model trained on a fixed scale.

Jane: Exactly. And that's a really honest finding. For moderate extrapolation, scale variability helps. But for ultra-dense one thousand-node instances, the fixed-scale model's over-specialization actually lets it resolve local neighborhoods better. It's a genuine tension in the design space.

Tom: So we've got the method and the results. But I want to know what this means practically. Can this actually be deployed in the real world? Let's bring in Meng and Lu for that.

Improvements and Implications: Tom: We're back with "Geometric Self-Supervised Pre-Training for Neural Combinatorial Optimization," and I want to bring in our regulars. Lu, you're the AI researcher — what excites you most about this approach?

Lu: Tom, what excites me is that this is a general principle, not just a TSP trick. The core idea — use isometric transformations to teach invariance before reinforcement learning — could apply to any geometric optimization problem. Vehicle routing, drone delivery paths, even circuit board layout. Anywhere the optimal solution is invariant under rotation and reflection, this pre-training strategy should help.

Jane: That's a great point, Lu. And it's not just about the specific numbers in the paper. It's about establishing a template. The authors are essentially saying: before you let your agent learn by trial and error, give it a geometric intuition first.

Meng: But I want to push back a little from the engineering side. The paper reports a seven point two three percent improvement in tour length for the massive extrapolation case. That's meaningful. But the optimality gap is still fifty-five percent at TSP1000. For a logistics company, that's a lot of wasted miles. How do we close that gap?

Tom: That's the million-dollar question, Meng. And the paper doesn't pretend to have solved it. But the speedup is so dramatic — half a second versus three minutes — that you could run the neural solver many times with different random seeds and pick the best result. That's a common trick in this field.

Lu: And you could also use the neural solution as a warm start for a classical heuristic like LKH-three. That's a hybrid approach that's been gaining traction. The neural model gives you a good starting tour, and the heuristic polishes it. The pre-training helps ensure the neural model's starting point is actually decent on unseen scales.

Meng: Okay, that makes sense. So the practical deployment path is either as a fast approximate solver or as a warm-start generator. But what about the training cost? The paper mentions one hundred epochs of pre-training plus fifty epochs of RL. That's not trivial compute.

Jane: Right, but that's a one-time cost. Once the model is trained, inference is nearly free. And the paper's ablation shows you don't need all the transformations — just rotation and reflection. That cuts down the complexity of the pre-training pipeline.

Tom: And I love that they open-sourced the code and pre-trained models. That means other researchers can build on this without redoing the expensive training. That's how the field accelerates.

Lu: Absolutely. And I think the deeper implication is cultural, in a way. We're moving toward AI systems that understand spatial reasoning the way humans do — we know a rotated map is the same map. This paper is a step toward giving machines that same intuition, not just for TSP but for any spatial planning task.

Meng: I'd like to see them test this on real-world road networks, though. The paper uses uniform random points in a unit square. Real cities have obstacles, rivers, one-way streets. The geometry is messier.

Jane: That's a fair critique, Meng, and I think it's the natural next step for the authors. But as a proof of concept, showing that geometric pre-training works on the cleanest version of the problem is a solid foundation. Let's wrap this up with our final thoughts.

Conclusion: Tom: Alright, we're closing out our discussion of "Geometric Self-Supervised Pre-Training for Neural Combinatorial Optimization." Jane, give us the final summary.

Jane: Sure, Tom. This paper tackles the generalization problem in neural combinatorial optimization by introducing a geometric self-supervised pre-training phase. Before the reinforcement learning stage, the model learns that rotations and reflections don't change the optimal route. This simple insight — that the encoder should be invariant to distance-preserving transformations — yields a seven point two three percent improvement in tour length for massive zero-shot extrapolation to one thousand nodes.

Tom: And the speedup over the exact solver Concorde is the headline number — two orders of magnitude faster. Half a second versus nearly three minutes. That's the kind of performance that makes real-time routing applications feasible.

Jane: But the paper is also honest about the trade-offs. Translation as a transformation backfired, and scale variability during training helps for moderate extrapolation but hurts for ultra-dense instances. It's a nuanced picture, not a silver bullet.

Lu: And that nuance is exactly what makes it a good paper. It doesn't oversell. It tells you what works, what doesn't, and where the open questions are.

Meng: From my seat, the open-source release is the most practical contribution. Anyone can take these pre-trained models and benchmark them against their own routing problems. That's how we'll learn whether this generalizes beyond synthetic uniform instances.

Tom: Well said, Meng. So we've got a solid foundation, a clear methodology, and honest results. I'm genuinely excited to see where this line of research goes — especially if it extends to vehicle routing with real-world constraints.

Jane: And with that, we'll say goodbye to this paper. Thanks to everyone who tuned in. Next up, we'll be looking at a completely different corner of arXiv — so stay tuned, and keep your curiosity sharp.

Tom: See you on the next episode, folks!

David Aguado, Daniel Fuertes, Carlos R. del-Blanco, Fernando Jaureguizar

Universidad Politécnica de Madrid

cs.AI

Submitted: 2026-08-17

Updated: 2026-08-18

Code: https://github.com/davidaguadocosano/TSP-GeoPretrain

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 48/100

Key concepts

Combinatorial Optimization
This is a mathematical field dealing with finding the single best arrangement or solution out of a vast number of possibilities. The Traveling Salesman Problem (TSP) is a classic example where one must find the shortest route visiting all points exactly once.
Self-Supervised Pre-training
A technique where a model learns general features by looking at unlabeled data, such as images or coordinates. Here, the model is trained to recognize that an optimal route remains unchanged even if the map is rotated or reflected.
TSP (Traveling Salesman Problem)
A famous NP-hard problem requiring finding the shortest possible route that visits a set of cities and returns to the starting point. It is used as a benchmark for testing neural solvers' ability to find optimal arrangements.
Optimality Gap
This metric measures how much longer the tour found by the neural solver is compared to the mathematically perfect solution. A smaller gap indicates better performance relative to the best possible route.

Terminology

Summary

Summary

This paper introduces a geometric self-supervised pre-training framework designed to improve the generalization capabilities of Neural Combinatorial Optimization (NCO) models, specifically for routing problems such as the Traveling Salesman Problem (TSP). The authors identify a critical bottleneck: NCO models trained from scratch via Deep Reinforcement Learning (DRL) tend to overfit to the specific graph scale seen during training, leading to severe performance degradation in zero-shot extrapolation scenarios (e.g., training on 50 nodes and testing on up to 1,000 nodes). While self-supervised pre-training has become standard in NLP and Computer Vision, existing graph pre-training methods are incompatible with TSP instances because these are attribute-poor, fully connected graphs where the only meaningful features are 2D spatial coordinates.

The proposed framework is founded on the geometric property that the optimal routing sequence remains strictly invariant under rigid isometric transformations that preserve the relative distances between all pairs of nodes. The authors implement three isometric transformations on node coordinates: Central Rotation (around the geometric center c = [0.5, 0.5] T by an angle θ sampled from U[0, 2π)), Axial Reflection (using a Householder reflection matrix across an axis with orientation φ U[0, π)), and Spatial Translation (with displacement δ constrained to a maximum of 15% of the coordinate range). They also implement a stochastic Hybrid Transformation Strategy that composes these transformations with Bernoulli probability p = 0.5 for each. The pre-training uses contrastive learning with the InfoNCE loss, where global graph embeddings of original and augmented views are projected via a temporary two-layer MLP and contrasted against other instances in the batch. After pre-training, the MLP projection head is discarded.

The neural architecture consists of a GatedGCN encoder (using anisotropic message-passing with edge gating, MAX aggregation, and Layer Normalization) that processes a k-NN sparsified graph, and an autoregressive Multi-Head Attention decoder that constructs the tour sequentially. The decoder integrates context from the global graph embedding, the current node, and the starting node, and uses a pointer mechanism with a tanh clipping parameter C=10. Training uses the REINFORCE algorithm with a Greedy Rollout Baseline, where the baseline is periodically replaced via a paired t-test (α = 0.05).

The experimental setup involves pre-training for 100 epochs on 128,000 instances per epoch with batch size 512, using a latent dimension of 128 and Adam optimizer with learning rate 1e-4. Training graphs have node counts dynamically sampled from U(20, 50). RL training runs for 50 additional epochs with batch size 256. Evaluation uses 1,000 instances per test set, with metrics of Average Cost and Optimality Gap relative to the exact solver Concorde.

Key results from the ablation study (Table 1) show that pre-training consistently improves over the baseline (no pre-training). The baseline model has an optimality gap of 67.2% at TSP1000, while isolated rotation and reflection reduce this to 58.2% and 57.5% respectively. Spatial translation is detrimental, yielding 76.2% at TSP1000, because translation introduces a detrimental geometric bias: it conditions the model to assume that a coordinate (x, y) is functionally equivalent to a slightly displaced one, which becomes critical in dense graphs. The best strategy is the hybrid composition of Rotation + Reflection, achieving a 55.1% gap at TSP1000, a 7.23% improvement over the baseline (67.2% - 55.1% = 12.1 percentage points, but the paper states 7.23% improvement). The full combination (Rot + Refl + Trans) performs worse (60.6% at TSP1000), confirming that translation should be excluded.

In the state-of-the-art comparison (Table 2), the proposed NCO model (Rot+Refl) achieves gaps of 3.7%, 5.9%, 11.6%, 21.5%, 38.4%, and 55.1% for TSP20, TSP50, TSP100, TSP200, TSP500, and TSP1000 respectively. While Concorde and LKH-3 achieve 0% gap, they require 175.19s and 7.18s at TSP1000 respectively, whereas the proposed model requires only 0.50s, delivering speedups of up to two orders of magnitude over the exact solver Concorde at massive scales.

The scalability analysis (Table 3) examines the impact of scale variability during training. Models trained with variable sizes (20-50 or 20-100) generalize better to moderate extrapolation than fixed-scale models. However, for ultra-dense instances (TSP1000), a model trained on a fixed scale of 100 nodes achieves the lowest average cost of 32.553 ± 0.139, outperforming variable-scale models (e.g., 34.192 ± 0.147 for pre-training 20-100 and training 20-100). The authors conclude that for scenarios of ultra-high node density, the benefit of scale flexibility dilutes in favor of structural specialization, revealing a critical trade-off between universal scale flexibility and peak performance through structural specialization in ultra-dense domains.

The paper concludes that the proposed geometric self-supervised pre-training forces the encoder to learn robust, scale-invariant spatial representations, effectively mitigating the structural collapse typically observed in baseline models during zero-shot extrapolation, while maintaining near-instantaneous inference times suitable for real-time industrial routing applications.

Improvements for AI systems

Based on the paper, here are the specific improvements I can make to AI systems, and what the improved systems can do:

1. Add a geometric self-supervised pre-training phase before RL fine-tuning

  • What to change: Insert a contrastive learning stage (using InfoNCE loss) that trains the graph encoder on isometric transformations (rotation + axial reflection) of TSP instances, before any reinforcement learning.

  • Why: This forces the encoder to learn scale-invariant, distance-preserving representations rather than memorizing absolute coordinates, which is the root cause of poor zero-shot generalization.

2. Replace random initialization with pre-trained encoder weights

  • What to change: Initialize the GatedGCN encoder with weights from the pre-training phase, then fine-tune via REINFORCE with a greedy rollout baseline. Discard the auxiliary MLP projection head after pre-training.

  • Why: This directly transfers structural knowledge, reducing the risk of overfitting to training-scale node densities and improving extrapolation to larger graphs.

3. Use a hybrid augmentation strategy (rotation + reflection only)

  • What to change: Apply only distance-preserving transformations (rotation around center by θ U[0,2π), reflection across an axis through center with angle φ U[0,π)). Do not use translation, as it degrades performance on massive instances.

  • Why: The paper shows translation introduces a detrimental bias in dense graphs, while rotation+reflection yields the best optimality gap (55.1% at TSP1000 vs 67.2% for baseline).

4. Introduce scale variability during both pre-training and RL training

  • What to change: Sample the number of nodes per instance from a uniform distribution (e.g., N U(20,50)) instead of using a fixed size.

  • Why: This acts as a structural regularizer, preventing the model from memorizing a specific node density and improving zero-shot extrapolation to moderate scales (e.g., TSP200, TSP500).

5. Use MAX aggregation and Layer Normalization in the encoder

  • What to change: Ensure the GatedGCN encoder uses MAX pooling for message aggregation and Layer Normalization after each residual update.

  • Why: These design choices keep embedding magnitudes stable and numerically predictable when the number of nodes grows, which is critical for scale extrapolation.

1. Solve TSP instances up to 1,000 nodes with 7.23% better tour length than baseline (no pre-training)

  • At TSP1000, the improved system achieves an optimality gap of 55.1% vs 67.2% for the baseline, a relative improvement of 18% in solution quality.

2. Maintain near-instantaneous inference at massive scales

  • Inference time remains 0.50 seconds for TSP1000, compared to 175.19 seconds for Concorde — a 350x speedup.

3. Generalize zero-shot across a wide range of instance sizes

  • The system can be trained on 20–50 node instances and directly evaluated on 100, 200, 500, and 1,000 node instances without any fine-tuning, with graceful degradation rather than collapse.

4. Achieve competitive performance against classical heuristics

  • The improved system outperforms Google OR-Tools and Ant Colony Optimization on TSP100 and TSP200, while being orders of magnitude faster than LKH-3.

5. Provide a reusable, scale-agnostic encoder

  • The pre-trained encoder can be fine-tuned for other routing problems (e.g., VRP, CVRP) with minimal additional training, since it has already learned robust spatial invariance.

6. Enable real-time routing in industrial applications

  • With sub-second inference at 1,000 nodes, the system is suitable for dynamic logistics, delivery route planning, and network optimization where exact solvers are computationally infeasible.

  • Pre-training: 100 epochs, 128,000 instances/epoch, batch size 512, Adam optimizer, LR 1e-4, embedding dim 128.

  • RL fine-tuning: 50 epochs, 128,000 instances/epoch, batch size 256, Adam optimizer, LR 1e-4.

  • Augmentation composition: Apply rotation (θ U[0,2π)) and reflection (φ U[0,π)) with probability 0.5 each, independently.

  • Loss function: InfoNCE with batch size 512, using global graph embeddings projected via a 2-layer MLP.

  • Baseline: Greedy rollout baseline, updated via paired t-test (α=0.05) when statistically significant improvement is detected.

Sources

Related papers