REVIEW 4 major objections 6 minor
Bandit based Dynamic Candidate Edge Selection in Solving Traveling Salesman Problems
T0 review · 4 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read Per-city bandits that dynamically pick candidate edges from enlarged sets improve LKH and transfer to MTSP and CVRP.
desk verdict Useful bandit-based candidate-selection idea for LKH, but the headline win over LKH is confounded by unequal compute per trial and needs time-equalized evidence. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is a per-city multi-armed bandit (MAB) whose arms are the edges in that city's enlarged candidate set; pulling an arm selects that edge as one of the candidate edges for the current trial. Each arm carries a learned M-value updated by exponential smoothing, $M(i,j) = (1-\lambda)M(i,j) + \lambda r(R,R^*)$, with reward $r(R,R^*)=L(R^*)-L(R)$ measuring how much the trial's local optimum improves on the best tour found so far. Three pulling strategies are used cooperatively: epsilon-greedy explores with probability $\epsilon$, M-greedy takes the largest M-values, and $\alpha$-greedy takes the largest $\alpha$-values. The per-trial costs are linear in the number of cities: $O(n C_{max}\log C_{max})$ for selection and $O(n)$ for updates.
What would settle it
Run bandLKH and LKH on fl1577 with the same wall-clock budget of, say, 2000 seconds and record the best tour each second; if LKH matches or beats bandLKH once time is equalized, the bandit selection is not the cause of the reported improvement. As a complementary check, replace the learned M-greedy and epsilon-greedy pulls with random pulls from the enlarged set; if random selection achieves the same average gap, the learned M-values are doing no work.
Extended reading notes
Core claim
The central claim is that LKH's search quality is limited less by its local-search operators than by the fixed candidate-edge lists those operators are allowed to use, and that adaptively selecting edges with per-city multi-armed bandits removes that limit. In bandLKH, each city's candidate set is enlarged from five to seven edges, and a bandit attached to that city pulls five arms per trial. Three policies--epsilon-greedy over learned M-values, greedy over M-values, and greedy over the alpha-values--are alternated whenever the best tour has not improved for a fixed number of trials. The M-value of an edge is updated after each trial by exponential smoothing with reward equal to the gap between the best tour found and the newly obtained local optimum. The paper reports that this dynamic selection finds the best-known solution more often and with a smaller average gap than LKH on the tested instances, and that it also improves LKH-3 on MTSP and CVRP.
Load-bearing premise
The load-bearing premise is that comparing bandLKH and LKH under the same MaxTrials is a fair test, even though each bandLKH trial costs more wall-clock time, so the reported advantage could shrink or disappear if both ran for the same time.
Editorial extensions
If this is right
- Instances where LKH misses the optimum because a critical edge is absent from a city's static candidate list become reachable, since the enlarged set gives that edge a chance to be pulled.
- Each of the three pulling strategies contributes to robustness: the paper's ablations show that removing epsilon-greedy, M-greedy, or alpha-greedy worsens the average gap.
- The mechanism transfers to other routing problems without changing the underlying solver, as shown by bandLKH-3 improving LKH-3 on both MTSP and CVRP.
- Because the added cost is linear, the improvement is not bought with asymptotically higher complexity, so the method remains applicable to instances with tens of thousands of cities.
- bandLKH also beats the learning-based variants VSR-LKH and NeuroLKH on average solution quality across the tested TSP instances.
Reading between the lines
- Beyond the paper: an equal-time comparison would isolate whether the bandit's advantage comes from dynamic selection or simply from spending more wall-clock time per trial; the current equal-MaxTrials protocol does not separate these.
- Beyond the paper: the same M-value reward signal could be attached to any local-search heuristic that consumes candidate-edge lists, including variants without an alpha-value, such as pickup-and-delivery or min-max routing solvers.
- Beyond the paper: the reward function only rewards edges that appear in solutions improving on the current best; a reward that also credits edges in good-but-suboptimal tours, or penalizes edges in bad tours, might learn faster and could be tested as a drop-in change to UpdateM.
- Beyond the paper: the enlarged set size is fixed at seven; adaptively growing or shrinking that size during the search, which the paper names as future work, could tune the exploration-exploitation balance per instance.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. This paper proposes bandLKH, a modified LKH algorithm for the TSP. Instead of using LKH's fixed candidate set of size 5 per city, bandLKH enlarges each candidate set to size 7 (Cmax) and, in each trial, uses a multi-armed bandit per city to select 5 (Narm) candidate edges to guide the Lin-Kernighan search. Three selection policies (epsilon-greedy, M-greedy based on learned M-values, and alpha-greedy based on precomputed alpha-values) are alternated when no improvement is seen for T_type trials. M-values are updated with an incremental reward r = L(R*) - L(R) common to all selected edges. The authors report experiments on TSPLIB, National TSP, and VLSI instances, comparing with LKH, VSR-LKH, and NeuroLKH, and also apply the method to LKH-3 for MTSP and CVRP. They report that bandLKH obtains better average solutions than LKH on 52 of 62 hard instances and better success rates on 33 of 62, with smaller average gaps, and similar improvements for bandLKH-3.
Significance. If the reported improvements are validated under a fair compute budget, the paper makes a useful practical contribution: it shows that dynamic, bandit-based candidate edge selection from a slightly enlarged set can improve the robustness of LKH-style local search for TSP and related problems. The method is simple, has linear overhead, and is potentially generalizable to other routing heuristics. The experimental coverage is broad (82 TSPLIB instances up to 85,900 cities, National/VLSI sets, 100 CVRP instances, 82 MTSP instances) and includes ablation studies. However, the main evaluation protocol equalizes trial counts rather than wall-clock time, and the hyperparameter tuning instances are not disclosed; these issues currently prevent a clean attribution of the observed gains to the bandit mechanism. The paper also contains a numerical inconsistency in the reported average gaps that needs correction.
major comments (4)
- [Section 5.1 / Table 1] The evaluation protocol sets MaxTrials equal for bandLKH and LKH while MaxTime is a one-day cap that is never reached, so the comparison effectively gives each algorithm the same number of trials. However, bandLKH's trials are substantially more expensive: Table 1 reports, for example, fl1400 at 113 s vs 219 s, fl1577 at 1172 s vs 1921 s, rl5934 at 305 s vs 1607 s, and pla85900 at 9270 s vs 25843 s. Under this protocol, bandLKH receives 1.5–3x (and up to 5x) more compute per trial, so the headline claim in Section 5.2 that 'bandLKH has significantly better performance and robustness than LKH' is not cleanly attributable to the bandit-based candidate selection. Please report time-equalized experiments (e.g., equal wall-clock budgets or equal numbers of Lin-Kernighan calls with identical candidate-set sizes) to separate the benefit of the bandit mechanism from the benefit of extra computation.
- [Section 5.1] The hyperparameters C_max, N_arm, T_type, epsilon, and lambda were tuned with SMAC3 on 'some sampled instances', but the tuning instances are not identified. If any of them overlap with the test benchmarks, the comparison against default-parameter LKH (and against VSR-LKH / NeuroLKH results taken from the literature) is circular. Please specify the tuning set, its size, and confirm that it is disjoint from all evaluation sets; otherwise, state how the tuned parameters generalize.
- [Section 4.3, Eqs. (2)-(3)] The reward r(R,R*) is identical for every selected edge in a trial, so all arms pulled in the same trial receive the same increment to their M-values. This update rule cannot distinguish the contribution of individual edges to the tour improvement. Please provide a justification for why this coarse credit assignment is sufficient for edge-level selection, or include an ablation with edge-specific rewards (e.g., based on whether the edge appears in the improved tour) to support the bandit mechanism.
- [Table 1 bottom row] The row 'Average Gap (%)' reports bandLKH's average best gap as -0.0030%, yet Section 5.2 states that all BKS values are proven optimal. A negative gap is impossible under that claim. Please correct the sign or explain the discrepancy; this inconsistency affects the credibility of the quantitative summary.
minor comments (6)
- [Section 4.2] In the time complexity statement, 'O(n C_max log(C_max)' is missing a closing parenthesis; it should read O(n C_max log(C_max)).
- [Section 5.1] The sentence 'In each run, the algorithm will terminate and start the next run when it finds the optimal solution' is ambiguous; please rephrase to clarify that a run stops early only if the optimum is found.
- [General] The manuscript has numerous spacing and formatting errors (e.g., missing spaces between words and equations run into the text); a thorough copyedit is needed.
- [Section 5.3 / Table 2] The comparison with VSR-LKH and NeuroLKH does not state whether the results for the baselines were taken from their original papers under their own compute settings; please clarify the comparability of these results.
- [Sections 5.2-5.4] The word 'significant' is used to describe the improvements, but no statistical test is reported; consider adding a Wilcoxon signed-rank test or similar for the win/loss counts in Tables 1-4.
- [Table 4] The ablation with LKH-Cmax does not report running times; since LKH-Cmax uses all 7 candidate edges, its per-trial cost is higher than bandLKH's, and the comparison may also be compute-confounded. Please report time or a compute-controlled variant.
Circularity Check
No circularity: the MAB values are learned online per instance from the search objective, not fitted to test-set optima, and all headline comparisons are against external benchmarks.
full rationale
This is an empirical algorithm paper with no claimed first-principles derivation. The central mechanism (Sections 4.1-4.3) maintains per-instance M-values updated online from the reward r = L(R*) - L(R), where R* and R are solutions found during that same run; this is a standard reinforcement-learning feedback loop, not a parameter fitted to the test-set optimum. The comparisons in Section 5.2 are against TSPLIB, National TSP, and VLSI benchmarks with published best-known solutions, and the MAB is trained separately on each instance rather than on the benchmark optima, so no predicted quantity equals an input by construction. The only fitted quantities are hyperparameters (C_max, N_arm, T_type, epsilon, lambda) tuned by SMAC3 on 'some sampled instances' (Section 5.1); because the sampled instances are not disclosed, this is a potential tuning/selection risk, but the quoted text does not establish that test instances were used for tuning, so it cannot be scored as circularity. The equal-MaxTrials comparison gives bandLKH more wall-clock time per trial than LKH (Table 1, e.g., fl1577: 1172 s vs 1921 s), which is a fairness/validity concern rather than a circularity concern. The only self-citation, using VSR-LKH to set T_type = MaxTrials/20 (Section 5.1), is a minor hyperparameter choice and is not load-bearing for the central claim. No circular step can be exhibited from the paper's own equations or citation chain.
Assumptions & free parameters
free parameters (5)
- C_max (enlarged candidate set size) =
7
- N_arm (number of arms pulled per bandit) =
5
- epsilon (exploration probability) =
0.15
- lambda (incremental reward parameter) =
0.16
- T_type (no-improvement trials before switching bandtype) =
MaxTrials/20
assumptions (4)
- domain assumption The alpha-value metric, computed from a minimum 1-tree, is a reliable predictor of edge quality for LKH candidate selection.
- ad hoc to paper The enlarged candidate set of size C_max=7 contains enough high-quality edges to support better solutions than the original size-5 set.
- ad hoc to paper The reward r(R,R*)=L(R*)-L(R) provides a useful credit assignment for every selected edge, despite being identical for all pulled arms.
- ad hoc to paper Rotating among epsilon-greedy, M-greedy, and alpha-greedy after T_type no-improvement trials improves robustness.
Cite this review
Pith. "Pith review of Bandit based Dynamic Candidate Edge Selection in Solving Traveling Salesman Problems." pith.science (2026). https://pith.science/paper/3F4LYT3I
@misc{pith2026250515862,
author = {Pith},
title = {Pith review of: Bandit based Dynamic Candidate Edge Selection in Solving Traveling Salesman Problems},
year = {2026},
howpublished = {\url{https://pith.science/paper/3F4LYT3I}},
note = {Machine review of arXiv:2505.15862}
}
read the original abstract
Algorithms designed for routing problems typically rely on high-quality candidate edges to guide their search, aiming to reduce the search space and enhance the search efficiency. However, many existing algorithms, like the classical Lin-Kernighan-Helsgaun (LKH) algorithm for the Traveling Salesman Problem (TSP), often use predetermined candidate edges that remain static throughout local searches. This rigidity could cause the algorithm to get trapped in local optima, limiting its potential to find better solutions. To address this issue, we propose expanding the candidate sets to include other promising edges, providing them an opportunity for selection. Specifically, we incorporate multi-armed bandit models to dynamically select the most suitable candidate edges in each iteration, enabling LKH to make smarter choices and lead to improved solutions. Extensive experiments on multiple TSP benchmarks show the excellent performance of our method. Moreover, we employ this bandit-based method to LKH-3, an extension of LKH tailored for solving various TSP variant problems, and our method also significantly enhances LKH-3's performance across typical TSP variants.
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.