HEATACO: Heatmap-Guided Ant Colony Decoding for Large-Scale Travelling Salesman Problems

• URL: http://arxiv.org/abs/2601.19041v1
• Date: Mon, 26 Jan 2026 23:51:19 GMT
• Title: HEATACO: Heatmap-Guided Ant Colony Decoding for Large-Scale Travelling Salesman Problems
• Authors: Bo-Cheng Lin, Yi Mei, Mengjie Zhang,
• Abstract summary: Heatmap-based non-autoregressive solvers for large-scale Travelling Salesman Problems output dense edge-probability scores.<n>We introduce HeatACO, a plug-and-play Max-Min Ant System decoder whose transition policy is softly biased by the heatmap.
• Score: 4.184504903540304
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Heatmap-based non-autoregressive solvers for large-scale Travelling Salesman Problems output dense edge-probability scores, yet final performance largely hinges on the decoder that must satisfy degree-2 constraints and form a single Hamiltonian tour. Greedy commitment can cascade into irreparable mistakes at large $N$, whereas MCTS-guided local search is accurate but compute-heavy and highly engineered. We instead treat the heatmap as a soft edge prior and cast decoding as probabilistic tour construction under feasibility constraints, where the key is to correct local mis-rankings via inexpensive global coordination. Based on this view, we introduce HeatACO, a plug-and-play Max-Min Ant System decoder whose transition policy is softly biased by the heatmap while pheromone updates provide lightweight, instance-specific feedback to resolve global conflicts; optional 2-opt/3-opt post-processing further improves tour quality. On TSP500/1K/10K, using heatmaps produced by four pretrained predictors, HeatACO+2opt achieves gaps down to 0.11%/0.23%/1.15% with seconds-to-minutes CPU decoding for fixed heatmaps, offering a better quality--time trade-off than greedy decoding and published MCTS-based decoders. Finally, we find the gains track heatmap reliability: under distribution shift, miscalibration and confidence collapse bound decoding improvements, suggesting heatmap generalisation is a primary lever for further progress.

Related papers

• Beyond the Heatmap: A Rigorous Evaluation of Component Impact in MCTS-Based TSP Solvers [11.388824026057735]
  The Heatmap + Monte Carlo Tree Search (MCTS)'' paradigm has recently emerged as a prominent framework for solving the Travelling Salesman Problem (TSP)
  arXiv  Detail & Related papers  (2024-11-14T07:13:08Z)
• Estimating the Decoding Failure Rate of Binary Regular Codes Using Iterative Decoding [84.0257274213152]
  We propose a new technique to provide accurate estimates of the DFR of a two-iterations (parallel) bit flipping decoder.<n>We validate our results, providing comparisons of the modeled and simulated weight of the syndrome, incorrectly-guessed error bit distribution at the end of the first iteration, and two-itcrypteration Decoding Failure Rates (DFR)
  arXiv  Detail & Related papers  (2024-01-30T11:40:24Z)
• Unsupervised Landmark Discovery Using Consistency Guided Bottleneck [63.624186864522315]
  We introduce a consistency-guided bottleneck in an image reconstruction-based pipeline. We propose obtaining pseudo-supervision via forming landmark correspondence across images. The consistency then modulates the uncertainty of the discovered landmarks in the generation of adaptive heatmaps.
  arXiv  Detail & Related papers  (2023-09-19T10:57:53Z)
• Distributed Extra-gradient with Optimal Complexity and Communication Guarantees [60.571030754252824]
  We consider monotone variational inequality (VI) problems in multi-GPU settings where multiple processors/workers/clients have access to local dual vectors. Extra-gradient, which is a de facto algorithm for monotone VI problems, has not been designed to be communication-efficient. We propose a quantized generalized extra-gradient (Q-GenX), which is an unbiased and adaptive compression method tailored to solve VIs.
  arXiv  Detail & Related papers  (2023-08-17T21:15:04Z)
• Lightweight Super-Resolution Head for Human Pose Estimation [42.51588635059534]
  Heatmap-based methods have become the mainstream method for pose estimation. However, heatmap-based approaches suffer from significant quantization errors with downscale heatmaps. We propose SRPose to reduce the quantization error and dependence on further post-processing.
  arXiv  Detail & Related papers  (2023-07-31T15:35:34Z)
• Attention Map Guided Transformer Pruning for Edge Device [98.42178656762114]
  Vision transformer (ViT) has achieved promising success in both holistic and occluded person re-identification (Re-ID) tasks. We propose a novel attention map guided (AMG) transformer pruning method, which removes both redundant tokens and heads. Comprehensive experiments on Occluded DukeMTMC and Market-1501 demonstrate the effectiveness of our proposals.
  arXiv  Detail & Related papers  (2023-04-04T01:51:53Z)
• Heatmap Distribution Matching for Human Pose Estimation [12.524484316923333]
  We show that optimizing the heatmap prediction in such a way, the model performance of body joint localization may not be consistently improved. We propose to formulate the optimization of the heatmap prediction as a distribution matching problem between the predicted heatmap and the dot annotation of the body joint. We show the effectiveness of our proposed method through extensive experiments on the COCO dataset and the MPII dataset.
  arXiv  Detail & Related papers  (2022-10-03T07:21:30Z)
• Subpixel Heatmap Regression for Facial Landmark Localization [65.41270740933656]
  Heatmap regression approaches suffer from discretization-induced errors related to both the heatmap encoding and decoding process. We propose a new approach for the heatmap encoding and decoding process by leveraging the underlying continuous distribution. Our approach offers noticeable gains across multiple datasets setting a new state-of-the-art result in facial landmark localization.
  arXiv  Detail & Related papers  (2021-11-03T17:21:28Z)
• Is 2D Heatmap Representation Even Necessary for Human Pose Estimation? [44.313782042852246]
  We propose a textbfSimple yet promising textbfDisentangled textbfRepresentation for keypoint coordinate (emphSimDR) In detail, we propose to disentangle the representation of horizontal and vertical coordinates for keypoint location, leading to a more efficient scheme without extra upsampling and refinement.
  arXiv  Detail & Related papers  (2021-07-07T16:20:12Z)
• Heatmap Regression via Randomized Rounding [105.75014893647538]
  We propose a simple yet effective quantization system to address the sub-pixel localization problem. The proposed system encodes the fractional part of numerical coordinates into the ground truth heatmap using a probabilistic approach during training.
  arXiv  Detail & Related papers  (2020-09-01T04:54:22Z)
• Train Your Data Processor: Distribution-Aware and Error-Compensation Coordinate Decoding for Human Pose Estimation [14.816632698778049]
  We study the heatmap decoding processing with a particular focus on the errors introduced throughout the prediction process. Thereout propose a Distribution-Aware and Error-Compensation Coordinate Decoding (DAEC) DAEC learns its decoding strategy from training data and remarkably improves the performance of state-of-the-art human pose estimation models.
  arXiv  Detail & Related papers  (2020-07-12T02:17:29Z)

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.