Technical Summary: HEATACO – A Heatmap-Guided Max–Min Ant System for Large-Scale TSPs

1. Problem Statement

The paper addresses the Travelling Salesman Problem (TSP), specifically focusing on the decoding stage of non-autoregressive (NAR) neural solvers. These solvers predict an edge-confidence heatmap in a single forward pass, assigning scores to potential edges. However, a heatmap is not a valid tour; it often contains disconnected cycles, violates degree constraints (nodes having more than two incident edges), and includes false positives.

The core challenge is the heatmap-to-tour decoding problem: converting a fixed, dense heatmap ($O(n^2)$ scores) into a feasible Hamiltonian cycle ($n$ edges) that satisfies global constraints. Existing decoders face a trade-off:

• Greedy Merging: Fast and deterministic but yields low-quality tours because it cannot revise early, potentially misleading edge choices.
• MCTS-guided k-opt Search: Produces higher-quality tours but is computationally expensive, requires predictor-specific tuning of hyperparameters (e.g., exploration constants), and relies on per-instance tree searches.

The authors argue that there is a need for a predictor-agnostic decoder that can convert heatmaps from different pretrained models into feasible tours without retraining or specific tuning, while maintaining computational efficiency and high solution quality.

2. Methodology: HEATACO

The authors propose HEATACO, a scalable decoder based on the Max–Min Ant System (MMAS), a robust variant of Ant Colony Optimization (ACO). HEATACO integrates the fixed heatmap into the MMAS construction rule via a novel capped, degree-aware evidence factor.

Key Components:

1. Candidate List Construction:

   • Instead of considering all $O(n^2)$ edges, the algorithm restricts construction to a sparse candidate list of size $k=20$ per node.
   • Candidates are selected based on the heatmap (edges with confidence $> \theta_h$) and filled with nearest neighbors if the heatmap is sparse, ensuring connectivity.

2. Degree-Aware Evidence Bias ($e_{ij}$):

   • The heatmap is treated as ordinal evidence rather than calibrated probability.
   • For each node, a degree baseline ($b_i$) is calculated based on the $(d^*+1)$-th highest confidence edge, where $d^*$ is the tour degree (2 for symmetric TSP, 1 for ATSP outgoing).
   • The evidence factor $e_{ij}$ for an edge is the ratio of its confidence to this baseline, capped at a minimum of 1. This ensures that an edge only receives a bias boost if its confidence exceeds the node's capacity to accept it, filtering out "noisy" high-confidence edges that are merely the best among many similar options.

3. Automatic Scaling ($\kappa$):

   • To prevent the heatmap from permanently overriding the pheromone feedback (which learns instance-specific structure), the strength of the evidence bias ($\kappa$) is automatically scaled.
   • $\kappa$ is derived from the pheromone dynamic range ($\tau_{max}/\tau_{min}$) and the 90th percentile of the log-margins of the evidence factors.
   • This scaling ensures the heatmap influences early sampling but allows the pheromone feedback to correct misleading guidance as the search progresses. A single configuration works across different predictors without retraining.

4. Search Process:

   • Initialization: A nearest-neighbor tour initializes the pheromone bounds.
   • Construction: $m$ ants build tours in parallel using a pseudorandom proportional rule combining pheromones, heuristic distance, and the heatmap evidence factor.
   • Update: Pheromones evaporate and are reinforced by the best tour found in the iteration (or restart/global best).
   • Local Search: Optional 2-opt or 3-opt (for symmetric TSP) or directed 2-opt (for ATSP) is applied to refine tours before pheromone updates.

3. Key Contributions

• A Predictor-Agnostic Decoder: HEATACO decodes heatmaps from diverse pretrained models (AttGCN, DIMES, UTSP, DIFUSCO) without retraining the predictor or tuning the decoder per model.
• Capped, Degree-Aware Evidence: A mechanism that rewards edges only when they exceed the node's degree capacity, preventing the decoder from being overwhelmed by dense, low-discriminability heatmaps.
• Automatic Scaling: A method to scale the heatmap bias relative to the pheromone dynamic range, ensuring robustness across different heatmap qualities and instance scales.
• Comprehensive Evaluation: The method is evaluated on TSP500, TSP1K, and TSP10K, as well as out-of-distribution (OOD) benchmarks (Clustered, Gaussian, TSPLIB) and the Asymmetric TSP (ATSP).

4. Experimental Results

The paper compares HEATACO against standard MMAS, greedy merging, and MCTS-guided k-opt search across four heatmap sources.

• vs. Greedy Merging: HEATACO significantly outperforms greedy decoding, reducing optimality gaps from >10% (often >30% on large instances) to near-optimal levels.
• vs. MCTS: On in-distribution benchmarks (TSP500, TSP1K, TSP10K), HEATACO with 2-opt achieves lower optimality gaps and shorter decoding times than the published MCTS baselines for the same fixed heatmaps. For example, on TSP1K, HEATACO+2-opt reaches ~0.2–0.4% gap in ~4–8 seconds, whereas MCTS takes ~100 seconds for ~0.5–1.5% gap.
• vs. Standard MMAS:
  • Construction Phase: Heatmap guidance significantly improves the initial construction quality for all predictors and scales, reducing gaps by several percentage points before local search.
  • With Local Search:
    • On TSP500 and TSP1K, HEATACO remains beneficial even with 2-opt and 3-opt, though the marginal gain decreases as local search strength increases.
    • On TSP10K, the advantage of heatmap guidance diminishes or reverses after strong local search (3-opt). The paper attributes this to reduced complementarity: strong geometric repair (3-opt) can recover the tour structure independently, making the heatmap's contribution redundant or occasionally detrimental if it biases the search away from geometrically optimal paths.
• Generalization:
  • ATSP: HEATACO transfers well to the Asymmetric TSP, showing significant gains where local search (directed 2-opt) is weaker.
  • Distribution Shifts: Performance on OOD data (Clustered, Gaussian, TSPLIB) correlates with heatmap reliability. When the heatmap remains sparse and discriminative (e.g., DIFUSCO on TSPLIB), HEATACO succeeds. When the heatmap becomes too dense or loses discriminability (e.g., DIMES on pr1002), performance degrades.
  • SoftDist Control: Experiments with a non-learned "SoftDist" heatmap (based purely on distance) show that at large scales with strong local search, a geometric prior is often sufficient, reinforcing that learned heatmaps are only valuable when they provide structure beyond simple proximity.

5. Significance and Claims

The paper claims that HEATACO provides a common, automatically scaled procedure for converting heatmaps from different pretrained models into feasible tours. Its significance lies in:

• Decoupling Prediction from Decoding: It allows researchers to reuse existing heatmap predictors without needing to retrain them or tune a specific decoder for each.
• Efficiency: It achieves state-of-the-art decoding speeds and solution qualities compared to MCTS, which is computationally prohibitive for large-scale problems.
• Diagnostic Insight: The work identifies that the value of learned heatmaps is bounded by two factors: heatmap reliability (under distribution shifts) and complementarity with local search (at large scales where geometric repair is strong).
• Practical Utility: It offers a robust fallback or enhancement for neural combinatorial solvers, particularly in scenarios where local search is weak (e.g., ATSP) or where rapid decoding is required.

The authors modestly conclude that while neural heatmaps are powerful, they do not always outperform classical search; their utility depends on the quality of the edge evidence and the strength of the geometric repair available. Future work is suggested to combine these diagnostics to dynamically select between HEATACO and a pure MMAS fallback.