Fine-Grain GPU Parallelization of the Generalized Partition Crossover for Large-Scale Traveling Salesman Problems

• URL: http://arxiv.org/abs/2608.21233v1
• Date: Fri, 21 Aug 2026 15:42:05 GMT
• Title: Fine-Grain GPU Parallelization of the Generalized Partition Crossover for Large-Scale Traveling Salesman Problems
• Abstract summary: The Traveling Salesman Problem (TSP) is one of the most extensively studied NP-hard optimization problems.<n>The proposed approach reformulates GPX as a graph-parallel problem using coalesced memory layouts, ghost-node transformations, and connected-node analysis.<n>The proposed GPU achieves speedups between 48x and 625x while significantly reducing memory overhead.
• Score: 1.160208922584163
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Traveling Salesman Problem (TSP) is one of the most extensively studied NP-hard optimization problems. Genetic Algorithm (GA)-based solvers, such as the Edge Assembly Crossover (EAX), achieve state-of-the-art performance on many benchmark instances. However, the scalability of these approaches in massively parallel architectures remains limited because crossover operations involve irregular memory access patterns, graph traversals, and sequential dependencies. Existing GPU-based TSP solvers primarily exploit population-level parallelism and are limited to relatively small problem sizes. This work presents a fine-grain GPU implementation of the partition phase of the Generalized Partition Crossover (GPX) operator for large-scale TSP instances. The proposed approach reformulates GPX partitioning as a graph-parallel problem using coalesced memory layouts, ghost-node transformations, and connected-component analysis. The im- plementation parallelizes the union of parent tours, the splitting of degree- four vertices, the deletion of common edges, and the identification of recombining components using CUDA. Experimental results on instances ranging from 10,000 to 2 million cities demonstrate substantial acceleration over a naive sequential CPU imple- mentation. The proposed GPU partitioning achieves speedups between 48x and 625x while significantly reducing memory overhead. The re- sults demonstrate that operator-level parallelism can substantially im- prove the scalability of GA-based TSP solvers on modern many-core architectures.

Related papers

• From Sequential Nodes to GPU Batches: Parallel Branch and Bound for Optimal $k$-Sparse GLMs [6.381561491422844]
  We propose a generic, modular framework for processing heterogeneous nodes in branch and bound (BnB)<n>The framework is built around a small set of GPU-efficient routines and uses padding together with lightweight custom kernels to handle irregular node data structures.<n>Experiments show one to two orders of magnitude speedups and zero optimality gap on challenging instances.
  arXiv  Detail & Related papers  (2026-05-21T08:56:15Z)
• cuRegOT: A GPU-Accelerated Solver for Entropic-Regularized Optimal Transport [8.189956090077677]
  cuRegOT is a high-performance GPU solver tailored for entropic-regularized OT.<n>We introduce a suite of algorithmic and architectural optimizations, including an amortized symbolic analysis strategy to mitigate CPU bottlenecks.<n>CuRegOT achieves significant speedups over state-of-the-art GPU-based solvers across a variety of benchmark tasks.
  arXiv  Detail & Related papers  (2026-05-09T08:27:39Z)
• cuNNQS-SCI: A Fully GPU-Accelerated Framework for High-Performance Configuration Interaction Selection with Neural Network Quantum States [12.436495225801863]
  cuNNQS-SCI is a fully GPU-accelerated SCI framework designed to overcome these bottlenecks.<n>On an NVIDIA A100 cluster with 64 GPUs, cuNNQS-SCI achieves up to 2.32X end-to-end speedup.<n>It demonstrates excellent distributed performance, maintaining over 90% parallel efficiency in strong scaling tests.
  arXiv  Detail & Related papers  (2026-04-17T07:15:18Z)
• Parallel-in-Time Nonlinear Optimal Control via GPU-native Sequential Convex Programming [2.8852807790754618]
  We introduce a fully GPU-native trajectory optimization framework that combines sequential convex programming with a consensus-based alternating direction method of multipliers.<n>We validate the solver on a quadrotor agile flight task and a Mars powered descent problem using an on-board edge computing platform.<n> Benchmarks reveal a sustained 4x throughput speedup and a 51% reduction in energy consumption over a heavily optimized 12-core CPU baseline.
  arXiv  Detail & Related papers  (2026-03-11T12:39:14Z)
• Spava: Accelerating Long-Video Understanding via Sequence-Parallelism-aware Approximate Attention [63.69228529380251]
  Spava is a sequence-parallel framework with optimized attention for long-video inference.<n>Spava delivers speedups of 12.72x, 1.70x, and 1.18x over FlashAttn, ZigZagRing, and APB, without notable performance loss.
  arXiv  Detail & Related papers  (2026-01-29T09:23:13Z)
• Binary-Gaussian: Compact and Progressive Representation for 3D Gaussian Segmentation [83.90109373769614]
  3D Gaussian Splatting (3D-GS) has emerged as an efficient 3D representation and a promising foundation for semantic tasks like segmentation.<n>We propose a coarse-to-fine binary encoding scheme for per-Gaussian category representation, which compresses each feature into a single integer via the binary-to-decimal mapping.<n>We further design a progressive training strategy that decomposes panoptic segmentation into a series of independent sub-tasks, reducing inter-class conflicts and thereby enhancing fine-grained segmentation capability.
  arXiv  Detail & Related papers  (2025-11-30T15:51:30Z)
• GSPN-2: Efficient Parallel Sequence Modeling [101.33780567131716]
  Generalized Spatial Propagation Network (GSPN) addresses this by replacing quadratic self-attention with a line-scan propagation scheme.<n>GSPN-2 establishes a new efficiency frontier for modeling global spatial context in vision applications.
  arXiv  Detail & Related papers  (2025-11-28T07:26:45Z)
• Lighter-X: An Efficient and Plug-and-play Strategy for Graph-based Recommendation through Decoupled Propagation [49.865020394064096]
  We propose textbfLighter-X, an efficient and modular framework that can be seamlessly integrated with existing GNN-based recommender architectures.<n>Our approach substantially reduces both parameter size and computational complexity while preserving the theoretical guarantees and empirical performance of the base models.<n>Experiments demonstrate that Lighter-X achieves comparable performance to baseline models with significantly fewer parameters.
  arXiv  Detail & Related papers  (2025-10-11T08:33:08Z)
• Enabling Population-Level Parallelism in Tree-Based Genetic Programming for GPU Acceleration [9.421242935448722]
  Tree-based Genetic Programming (TGP) is a widely used evolutionary computation algorithm for tasks such as symbolic regression, classification, and robotic control.<n>EvoGP is a high-performance framework tailored for GPU acceleration of TGP via population-level parallel execution.
  arXiv  Detail & Related papers  (2025-01-21T07:42:54Z)
• Breaking the Memory Barrier: Near Infinite Batch Size Scaling for Contrastive Loss [59.835032408496545]
  We propose a tile-based strategy that partitions the contrastive loss calculation into arbitrary small blocks. We also introduce a multi-level tiling strategy to leverage the hierarchical structure of distributed systems. Compared to SOTA memory-efficient solutions, it achieves a two-order-of-magnitude reduction in memory while maintaining comparable speed.
  arXiv  Detail & Related papers  (2024-10-22T17:59:30Z)
• Rethinking and Accelerating Graph Condensation: A Training-Free Approach with Class Partition [49.41718583061147]
  Graph condensation is a data-centric solution to replace the large graph with a small yet informative condensed graph.<n>Existing GC methods suffer from intricate optimization processes, necessitating excessive computing resources and training time.<n>We propose a training-free GC framework termed Class-partitioned Graph Condensation (CGC)<n>CGC condenses the Ogbn-products graph within 30 seconds, achieving a speedup ranging from $102$X to $104$X and increasing accuracy by up to 4.2%.
  arXiv  Detail & Related papers  (2024-05-22T14:57:09Z)
• Learning to Solve Combinatorial Graph Partitioning Problems via Efficient Exploration [72.15369769265398]
  Experimentally, ECORD achieves a new SOTA for RL algorithms on the Maximum Cut problem. Compared to the nearest competitor, ECORD reduces the optimality gap by up to 73%.
  arXiv  Detail & Related papers  (2022-05-27T17:13:10Z)

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.