LocalEscaper: A Weakly-supervised Framework with Regional Reconstruction for Scalable Neural TSP Solvers

• URL: http://arxiv.org/abs/2502.12484v1
• Date: Tue, 18 Feb 2025 03:10:27 GMT
• Title: LocalEscaper: A Weakly-supervised Framework with Regional Reconstruction for Scalable Neural TSP Solvers
• Authors: Junrui Wen, Yifei Li, Bart Selman, Kun He,
• Abstract summary: LocalEscaper is a weakly-supervised learning framework for large-scale Traveling Salesman Problem (TSP)<n>It effectively combines the advantages of both SL and RL, enabling effective training on datasets with low-quality labels.<n>It sets a new benchmark for scalability and efficiency, solving TSP instances with up to 50,000 cities.
• Score: 14.238953745477193
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Neural solvers have shown significant potential in solving the Traveling Salesman Problem (TSP), yet current approaches face significant challenges. Supervised learning (SL)-based solvers require large amounts of high-quality labeled data, while reinforcement learning (RL)-based solvers, though less dependent on such data, often suffer from inefficiencies. To address these limitations, we propose LocalEscaper, a novel weakly-supervised learning framework for large-scale TSP. LocalEscaper effectively combines the advantages of both SL and RL, enabling effective training on datasets with low-quality labels. To further enhance solution quality, we introduce a regional reconstruction strategy, which mitigates the problem of local optima, a common issue in existing local reconstruction methods. Additionally, we propose a linear-complexity attention mechanism that reduces computational overhead, enabling the efficient solution of large-scale TSPs without sacrificing performance. Experimental results on both synthetic and real-world datasets demonstrate that LocalEscaper outperforms existing neural solvers, achieving state-of-the-art results. Notably, it sets a new benchmark for scalability and efficiency, solving TSP instances with up to 50,000 cities.

Related papers

• ThinkFL: Self-Refining Failure Localization for Microservice Systems via Reinforcement Fine-Tuning [31.89194823470957]
  Traditional failure localization approaches based on small models lack the flexibility to adapt to diverse failure scenarios. We propose a progressive multi-stage GRPO fine-tuning framework, which integrates a multi-factor failure localization and a recursion-of-thought actor module. The resulting model, ThinkFL, outperforms existing state-of-the-art LLMs and baseline methods in localization accuracy but also reduces end-to-end localization latency from minutes to seconds.
  arXiv  Detail & Related papers  (2025-04-26T03:08:30Z)
• Learning for Cross-Layer Resource Allocation in MEC-Aided Cell-Free Networks [71.30914500714262]
  Cross-layer resource allocation over mobile edge computing (MEC)-aided cell-free networks can sufficiently exploit the transmitting and computing resources to promote the data rate.<n>Joint subcarrier allocation and beamforming optimization are investigated for the MEC-aided cell-free network from the perspective of deep learning.
  arXiv  Detail & Related papers  (2024-12-21T10:18:55Z)
• Heterogeneity-Aware Resource Allocation and Topology Design for Hierarchical Federated Edge Learning [9.900317349372383]
  Federated Learning (FL) provides a privacy-preserving framework for training machine learning models on mobile edge devices. Traditional FL algorithms, e.g., FedAvg, impose a heavy communication workload on these devices. We propose a two-tier HFEL system, where edge devices are connected to edge servers and edge servers are interconnected through peer-to-peer (P2P) edge backhauls. Our goal is to enhance the training efficiency of the HFEL system through strategic resource allocation and topology design.
  arXiv  Detail & Related papers  (2024-09-29T01:48:04Z)
• Offline Reinforcement Learning for Learning to Dispatch for Job Shop Scheduling [0.9831489366502301]
  Job Shop Scheduling Problem (JSSP) is a complex optimization problem.<n>Online Reinforcement Learning (RL) has shown promise by quickly finding acceptable solutions for JSSP.<n>We introduce Offline Reinforcement Learning for Learning to Dispatch (Offline-LD)
  arXiv  Detail & Related papers  (2024-09-16T15:18:10Z)
• Decision Transformer for Enhancing Neural Local Search on the Job Shop Scheduling Problem [10.316443594063173]
  Job shop scheduling problem (JSSP) and its solution algorithms have been of enduring interest in both academia and industry for decades.<n>In recent years, machine learning (ML) is playing an increasingly important role in advancing existing and building new solutions for the JSSP, aiming to find better solutions in shorter times.<n>We build on top of a state-of-the-art deep reinforcement learning (DRL) agent, called Neural Local Search (NLS), which can efficiently and effectively control a large local neighborhood search on the JSSP.
  arXiv  Detail & Related papers  (2024-09-04T13:33:38Z)
• Locally Estimated Global Perturbations are Better than Local Perturbations for Federated Sharpness-aware Minimization [81.32266996009575]
  In federated learning (FL), the multi-step update and data heterogeneity among clients often lead to a loss landscape with sharper minima. We propose FedLESAM, a novel algorithm that locally estimates the direction of global perturbation on client side.
  arXiv  Detail & Related papers  (2024-05-29T08:46:21Z)
• Pointerformer: Deep Reinforced Multi-Pointer Transformer for the Traveling Salesman Problem [67.32731657297377]
  Traveling Salesman Problem (TSP) is a classic routing optimization problem originally arising in the domain of transportation and logistics. Recently, Deep Reinforcement Learning has been increasingly employed to solve TSP due to its high inference efficiency. We propose a novel end-to-end DRL approach, referred to as Pointerformer, based on multi-pointer Transformer.
  arXiv  Detail & Related papers  (2023-04-19T03:48:32Z)
• Efficient Parallel Split Learning over Resource-constrained Wireless Edge Networks [44.37047471448793]
  In this paper, we advocate the integration of edge computing paradigm and parallel split learning (PSL) We propose an innovative PSL framework, namely, efficient parallel split learning (EPSL) to accelerate model training. We show that the proposed EPSL framework significantly decreases the training latency needed to achieve a target accuracy.
  arXiv  Detail & Related papers  (2023-03-26T16:09:48Z)
• 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)
• Effective Self-supervised Pre-training on Low-compute Networks without Distillation [6.530011859253459]
  Reported performance of self-supervised learning has trailed behind standard supervised pre-training by a large margin. Most prior works attribute this poor performance to the capacity bottleneck of the low-compute networks. We take a closer at what are the detrimental factors causing the practical limitations, and whether they are intrinsic to the self-supervised low-compute setting.
  arXiv  Detail & Related papers  (2022-10-06T10:38:07Z)
• Deep Adaptive Inference Networks for Single Image Super-Resolution [72.7304455761067]
  Single image super-resolution (SISR) has witnessed tremendous progress in recent years owing to the deployment of deep convolutional neural networks (CNNs) In this paper, we take a step forward to address this issue by leveraging the adaptive inference networks for deep SISR (AdaDSR) Our AdaDSR involves an SISR model as backbone and a lightweight adapter module which takes image features and resource constraint as input and predicts a map of local network depth.
  arXiv  Detail & Related papers  (2020-04-08T10:08:20Z)
• Large-Scale Gradient-Free Deep Learning with Recursive Local Representation Alignment [84.57874289554839]
  Training deep neural networks on large-scale datasets requires significant hardware resources. Backpropagation, the workhorse for training these networks, is an inherently sequential process that is difficult to parallelize. We propose a neuro-biologically-plausible alternative to backprop that can be used to train deep networks.
  arXiv  Detail & Related papers  (2020-02-10T16:20:02Z)

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.