Geometric Self-Supervised Pre-training for Neural Combinatorial Optimization

• URL: http://arxiv.org/abs/2608.00270v1
• Date: Fri, 31 Jul 2026 20:23:21 GMT
• Title: Geometric Self-Supervised Pre-training for Neural Combinatorial Optimization
• Abstract summary: We propose a geometric self-supervised pre-training framework for routing graphs.<n>The framework learns robust structural representations prior to the policy optimization phase.<n>The proposed model exhibits remarkable computational efficiency, delivering speedups of up to two orders of magnitude over the exact solver Concorde.
• Score: 40.74618635552097
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Neural Combinatorial Optimization (NCO) techniques have emerged as a highly efficient alternative to traditional exact algorithms for solving routing problems such as the Traveling Salesman Problem (TSP). However, the generalization capabilities of these Reinforcement Learning-based models are severely hindered when scaling to high-dimensional instances. This issue has been mitigated in other domains, like computer vision and natural language processing, by adopting a self-supervised pre-training strategy. Nevertheless, its application to routing graphs, which lack complex topological attributes beyond 2D spatial coordinates, remains a challenge. In this paper, we propose a geometric self-supervised pre-training framework specifically designed to capture spatial invariance and global relative distance distributions. By applying isometric transformations, such as rotations and axial reflections, the model learns robust structural representations prior to the policy optimization phase. Empirical results demonstrate that this strategy consistently outperforms models trained from scratch (baselines), achieving a 7.23\% improvement in tour length for massive zero-shot extrapolation scenarios (TSP1,000). Furthermore, the proposed model exhibits remarkable computational efficiency, delivering speedups of up to two orders of magnitude over the exact solver Concorde at massive scales. The source code and pre-trained models are publicly available at https://github.com/davidaguadocosano/TSP-GeoPretrain.git.

Related papers

• On the Effectiveness of Pretraining for Graph Combinatorial Optimization [40.74618635552097]
  This paper introduces a self-supervised pretraining framework for graph optimization.<n>It is designed to address the nature of routing problems like the Traveling Salesman Problem.<n>Results demonstrate that this pretraining strategy outperforms non-pretrained models across various problem scales.
  arXiv  Detail & Related papers  (2026-07-21T13:04:13Z)
• An Efficient and Effective Architecture for Large-Scale Traffic Prediction via Geometry-Adaptive Square Partitioning [21.25554012711633]
  Square Partition is a geometry algorithm that partitions massive traffic sensors into balanced, non-overlapping spatial regions.<n>HLI is a module that abandons the costly attention mechanisms commonly used in Transformer-based deployment,temporal-temporal models.
  arXiv  Detail & Related papers  (2026-06-19T03:41:12Z)
• Neural Network Optimization Reimagined: Decoupled Techniques for Scratch and Fine-Tuning [49.751529745537546]
  We propose DualOpt, a novel approach that decouples optimization techniques specifically tailored for training from scratch.<n>For training from scratch, we introduce real-time layer-wise weight decay, designed to enhance both convergence and generalization.<n>We extend the layer-wise weight decay to dynamically adjust the rollback levels across layers, adapting to the varying demands of different downstream tasks.
  arXiv  Detail & Related papers  (2026-04-21T06:27:18Z)
• Evolution of Optimization Methods: Algorithms, Scenarios, and Evaluations [98.44542103979735]
  First-order gradient descent methods, epitomized by gradient descent (SGD) and Adam, serve as the cornerstone of modern training pipelines.<n>Large-scale model training, stringent privacy requirements, and distributed learning paradigms expose critical limitations in these conventional approaches regarding privacy protection and memory efficiency.<n>We retrospectively analyze the evolutionary trajectory of deep learning optimization algorithms and present a comprehensive empirical evaluation of mainstreams across diverse model architectures and training scenarios.<n>We distill key emerging trends and fundamental design trade-offs, pinpointing promising directions for future research.
  arXiv  Detail & Related papers  (2026-04-14T17:01:36Z)
• Dimer-Enhanced Optimization: A First-Order Approach to Escaping Saddle Points in Neural Network Training [5.9408311406202285]
  Dimer method is a first-order technique that constructs two closely spaced points to probe the local geometry of a potential energy surface.<n>Inspired by its use in molecular dynamics simulations for locating saddle points, we propose Dimer-Enhanced Optimization.<n>DEO guides the away from saddle points and flat regions, enhancing training efficiency with non-stepwise updates.
  arXiv  Detail & Related papers  (2025-07-26T14:57:32Z)
• Towards a Better Theoretical Understanding of Independent Subnetwork Training [56.24689348875711]
  We take a closer theoretical look at Independent Subnetwork Training (IST) IST is a recently proposed and highly effective technique for solving the aforementioned problems. We identify fundamental differences between IST and alternative approaches, such as distributed methods with compressed communication.
  arXiv  Detail & Related papers  (2023-06-28T18:14:22Z)
• Iterative Soft Shrinkage Learning for Efficient Image Super-Resolution [91.3781512926942]
  Image super-resolution (SR) has witnessed extensive neural network designs from CNN to transformer architectures. This work investigates the potential of network pruning for super-resolution iteration to take advantage of off-the-shelf network designs and reduce the underlying computational overhead. We propose a novel Iterative Soft Shrinkage-Percentage (ISS-P) method by optimizing the sparse structure of a randomly network at each and tweaking unimportant weights with a small amount proportional to the magnitude scale on-the-fly.
  arXiv  Detail & Related papers  (2023-03-16T21:06:13Z)
• An Adaptive and Scalable ANN-based Model-Order-Reduction Method for Large-Scale TO Designs [22.35243726859667]
  Topology Optimization (TO) provides a systematic approach for obtaining structure design with optimum performance of interest. Deep learning-based models have been developed to accelerate the process. MapNet is a neural network which maps the field of interest from coarse-scale to fine-scale.
  arXiv  Detail & Related papers  (2022-03-20T10:12:24Z)
• Joint inference and input optimization in equilibrium networks [68.63726855991052]
  deep equilibrium model is a class of models that foregoes traditional network depth and instead computes the output of a network by finding the fixed point of a single nonlinear layer. We show that there is a natural synergy between these two settings. We demonstrate this strategy on various tasks such as training generative models while optimizing over latent codes, training models for inverse problems like denoising and inpainting, adversarial training and gradient based meta-learning.
  arXiv  Detail & Related papers  (2021-11-25T19:59:33Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.