Leveraging Structural Constraints for Diffusion-based Neural TSP Solvers

• URL: http://arxiv.org/abs/2606.09343v1
• Date: Mon, 08 Jun 2026 11:08:36 GMT
• Title: Leveraging Structural Constraints for Diffusion-based Neural TSP Solvers
• Abstract summary: State-ofthe-art approaches like FT2T combine fast consistency-based prediction with gradient-based inference time refinement.<n>We introduce Projected Consistency Inference ( PCI), a plug-and-play, retraining-free alternative that replaces gradient refinement with structure-aware projections.<n> PCI achieves an average optimality gap (OG) of 0.17% on the Euclidean Traveling Salesman Problem with 500 cities, and 0.31% on the Euclidean Traveling Salesman Problem with 1000 cities, outperforming FT2T best settings.
• Score: 3.588053519843615
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Neural combinatorial optimization has recently achieved strong results on the Euclidean Traveling Salesman Problem (TSP) using generative models such as diffusion and consistency models. State-ofthe-art approaches like FT2T combine fast consistency-based prediction with gradient-based inference time refinement. However, gradient search often incurs significant computational overhead and may not align with the discrete structure of feasible solutions. We introduce Projected Consistency Inference (PCI), a plug-and-play, retraining-free alternative that replaces gradient refinement with structure-aware projections: PCI decodes valid Hamiltonian tours from the consistency model output and applies a lightweight local search (e.g., 2-opt). PCI achieves an average optimality gap (OG) of 0.17% on TSP with 500 cities, and 0.31% on TSP with 1000 cities, outperforming FT2T best settings (OG 0.22% and 0.36%, respectively) while reducing the inference time up to 30 to 40%. PCI also exhibits lower variance and memory usage, and can surpass classical heuristics such as LKH3 in rapid solution generation. Our results demonstrate that structure-aware inference time operations provide a practical and principled path for neural TSP solvers, complementing training time objectives.

Related papers

• Efficient Traffic Prediction at Scale: A Systematic Study of STGCN Architectural Depth [9.291555165680863]
  Single-block architecture achieves optimal performance for short-term prediction (10 mins) on three of four datasets.<n>The 2-block variant incurs 61% higher CPU inference latency and 37% lower throughput relative to 1-block.<n>The 3-block architecture offers no favourable tradeoff, more than doubling computational cost for $$0.5% relative improvement.
  arXiv  Detail & Related papers  (2026-06-08T14:23:56Z)
• Surrogate Modeling for Neutron Transport: A Neural Operator Approach [7.289597749952393]
  This work introduces a neural operator based surrogate modeling framework for neutron transport computation.<n>Two architectures, the Deep Operator Network (DeepONet) and the Fourier Neural Operator (FNO), were trained for fixed source problems.<n>Both neural operator solvers reproduced reference eigenvalues with deviations up to 135 pcm for DeepONet and 112 pcm for FNO.
  arXiv  Detail & Related papers  (2026-02-07T00:56:07Z)
• Structure-Informed Estimation for Pilot-Limited MIMO Channels via Tensor Decomposition [51.56484100374058]
  This paper formulates pilot-limited channel estimation as low-rank tensor completion from sparse observations.<n>Experiments on synthetic channels demonstrate 10-20,dB normalized mean-square error (NMSE) improvement over least-squares (LS)<n> evaluations on DeepMIMO ray-tracing channels show 24-44% additional NMSE reduction over pure tensor-based methods.
  arXiv  Detail & Related papers  (2026-02-03T23:38:05Z)
• Renormalization Group Guided Tensor Network Structure Search [58.0378300612202]
  Network structure search (TN-SS) aims to automatically discover optimal network topologies and rank robustness for efficient tensor decomposition in high-dimensional data representation.<n>We propose RGTN (Renormalization Group guided Network search), a physics-inspired framework transforming TN-SS via multi-scale renormalization group flows.
  arXiv  Detail & Related papers  (2025-12-31T06:31:43Z)
• Beyond Random: Automatic Inner-loop Optimization in Dataset Distillation [11.37339433547758]
  We propose Automatic Truncated Backpropagation Through Time (AT-BPTT) for dataset distillation.<n>AT-BPTT adapts both truncation positions and window sizes according to intrinsic gradient behavior.<n>Experiments on CIFAR-10, CIFAR-100, Tiny-ImageNet, and ImageNet-1K show that AT-BPTT achieves state-of-the-art performance.
  arXiv  Detail & Related papers  (2025-10-06T14:22:28Z)
• Predictive Feature Caching for Training-free Acceleration of Molecular Geometry Generation [67.20779609022108]
  Flow matching models generate high-fidelity molecular geometries but incur significant computational costs during inference.<n>This work discusses a training-free caching strategy that accelerates molecular geometry generation.<n> Experiments on the GEOM-Drugs dataset demonstrate that caching achieves a twofold reduction in wall-clock inference time.
  arXiv  Detail & Related papers  (2025-10-06T09:49:14Z)
• Point-wise Diffusion Models for Physical Systems with Shape Variations: Application to Spatio-temporal and Large-scale system [1.474723404975345]
  We propose a point-wise diffusion model that processes-temporal points independently to efficiently predict complex physical systems with shape variations.<n>We validate our approach across three distinct physical domains with complex geometric configurations.<n>Our proposed model achieves superior performance compared to image-based diffusion model.
  arXiv  Detail & Related papers  (2025-08-02T06:55:59Z)
• Dataset Distillation with Neural Characteristic Function: A Minmax Perspective [39.77640775591437]
  We reformulate dataset distillation as a minmax optimization problem and introduce Neural Characteristic Function Discrepancy (NCFD)<n>NCFD is a comprehensive and theoretically grounded metric for measuring distributional differences.<n>Our method achieves significant performance gains over state-of-the-art methods on both low- and high-resolution datasets.
  arXiv  Detail & Related papers  (2025-02-28T02:14:55Z)
• Fast T2T: Optimization Consistency Speeds Up Diffusion-Based Training-to-Testing Solving for Combinatorial Optimization [83.65278205301576]
  We propose to learn direct mappings from different noise levels to the optimal solution for a given instance, facilitating high-quality generation with minimal shots.<n>This is achieved through an optimization consistency training protocol, which minimizes the difference among samples.<n>Experiments on two popular tasks, the Traveling Salesman Problem (TSP) and Maximal Independent Set (MIS), demonstrate the superiority of Fast T2T regarding both solution quality and efficiency.
  arXiv  Detail & Related papers  (2025-02-05T07:13:43Z)
• Consistency Trajectory Models: Learning Probability Flow ODE Trajectory of Diffusion [56.38386580040991]
  Consistency Trajectory Model (CTM) is a generalization of Consistency Models (CM) CTM enables the efficient combination of adversarial training and denoising score matching loss to enhance performance. Unlike CM, CTM's access to the score function can streamline the adoption of established controllable/conditional generation methods.
  arXiv  Detail & Related papers  (2023-10-01T05:07:17Z)
• Truncated tensor Schatten p-norm based approach for spatiotemporal traffic data imputation with complicated missing patterns [77.34726150561087]
  We introduce four complicated missing patterns, including missing and three fiber-like missing cases according to the mode-drivenn fibers. Despite nonity of the objective function in our model, we derive the optimal solutions by integrating alternating data-mputation method of multipliers.
  arXiv  Detail & Related papers  (2022-05-19T08:37:56Z)

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.