{"id":"90adde5b-6999-40ab-9e8a-dfea6cf6d4d5","arxiv_id":"2505.15862","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"A multi-armed bandit that dynamically picks candidate edges from enlarged sets improves the LKH heuristic's consistency on TSP, MTSP, and CVRP benchmarks.","lead":"Researchers added a multi-armed bandit learner to the LKH solver for the Traveling Salesman Problem, letting each city dynamically choose five candidate edges from a pool of seven in every search round instead of using a fixed five. On TSP, multiple-salesmen, and vehicle-routing benchmarks the modified solver found optimal or near-optimal tours more consistently than the original, though it typically consumed more compute time per trial.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Equal-trials comparison may conflate bandit benefit with extra compute; time-equalized runs are needed to support 'significantly better'.","rationale":"The manuscript's central claim is that MAB-based dynamic candidate selection yields significantly better performance and robustness than static LKH candidate sets. The reader's identified weakest assumption is exactly the equal-trials protocol. The evidence in Table 1 supports the existence of a runtime gap: bandLKH uses 1.5-3x more wall-clock time on many instances, including cases where LKH runs out of trials (Trials column hits the cap) and still loses on time, such as fl1400 and fl1577. This makes the improvement attribution ambiguous because two confounds are present simultaneously: (1) more compute per trial, and (2) the dynamic selection mechanism. The paper's own statement that MaxTime is a one-day cap never reached confirms that wall-clock time was not the controlling budget. The second concern, undisclosed SMAC3 tuning instances, is also legitimate because the paper reports tuning on 'some sampled instances' without identifying them; the MTSP benchmark is constructed from TSPLIB by using the first city as depot, so tune/test overlap on TSPLIB would be a real circularity risk. Both concerns are empirical and falsifiable, not internal inconsistencies. The verdict of CONDITIONAL is appropriate because the proposed method is novel, clearly described, and has strong ablations (Table 4, LKH-Cmax comparison), but the headline claim of 'significantly better' requires a time-equalized comparison and disclosed tuning splits before it can be accepted as definitive. I agree with the reader that conditional acceptance is the right call.","tokens_in":24447,"tokens_out":1653,"duration_ms":13249,"concrete_test":"Run both LKH and bandLKH on the 10,000-city subset of TSPLIB instances from Table 1 with MaxTime set to a common value (e.g., the time LKH needs for its MaxTrials, and a second budget equal to that of bandLKH), and report the best/average gaps and success rates as a function of wall-clock time. If bandLKH does not dominate LKH at equal time, the headline claim of Section 5.2 should be downgraded. Additionally, rerun the ablation LKH-Cmax with Cmax=7 under the time-equalized budget to confirm that dynamic selection, not the enlarged candidate set alone, drives any remaining advantage.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The paper compares bandLKH and LKH under identical MaxTrials but not identical wall-clock time (Section 5.1). Table 1 shows bandLKH consistently using 1.5-3x more time (e.g., fl1400: 113s vs 219s; fl1577: 1172s vs 1921s; rl5934: 305s vs 1607s). Because bandLKH spends extra time on bandit overhead and enlarged Cmax=7 candidate sets, equal-trials comparison gives it more compute per trial. The central claim in Section 5.2 that 'bandLKH has significantly better performance and robustness than LKH' would be weakened if the advantage shrinks or disappears under time-equalized budgets. The paper does not report time-equalized results, so the improvement cannot be cleanly attributed to dynamic bandit selection. A second issue: the parameters Cmax, Narm, Ttype, epsilon, lambda were tuned by SMAC3 on 'some sampled instances', but the tuning instances are not disclosed; if tuning used test instances, comparisons become circular.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":24776,"tokens_out":9479,"duration_ms":79055,"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":[{"comment":"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":"Section 5.1 / Table 1"},{"comment":"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":"Section 5.1"},{"comment":"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.","section":"Section 4.3, Eqs. (2)-(3)"},{"comment":"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.","section":"Table 1 bottom row"}],"minor_comments":[{"comment":"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":"Section 4.2"},{"comment":"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.","section":"Section 5.1"},{"comment":"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":"General"},{"comment":"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.","section":"Section 5.3 / Table 2"},{"comment":"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.","section":"Sections 5.2-5.4"},{"comment":"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.","section":"Table 4"}],"recommendation":"major_revision","confidential_remarks":"The paper tackles a relevant problem and the proposed idea is interesting, but the current evaluation does not support the strong claim of 'significantly better' due to the compute-budget confound. The undisclosed tuning set and the negative-gap inconsistency in Table 1 need to be resolved. I recommend major revision rather than rejection because the central idea is plausible and the required experiments (time-equalized runs, tuning-set disclosure) are within the scope of a revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the MAB-for-dynamic-candidate-selection mechanism is genuinely new, the benchmarks are extensive, and the ablation against a fixed enlarged candidate set is the right control. But the paper's central claim that bandLKH 'significantly outperforms' LKH is not cleanly supported because equal MaxTrials gives bandLKH much more wall-clock time per run.\n\nThe new thing is real: unlike VSR-LKH, which reorders fixed candidates, and NeuroLKH, which fixes the set before search, bandLKH pulls arms from an enlarged Cmax=7 set every iteration and updates M-values from tour length rewards. That's a legitimate extension and the algorithm is described clearly enough to reproduce. The paper deserves credit for the full TSPLIB/National/VLSI sweep, the MTSP and CVRP generalization tests, and the ablation that compares bandLKH to LKH-Cmax: showing the bandit filter beats just enlarging the set argues the mechanism does more than add compute.\n\nThe soft spots are real. Table 1 shows bandLKH routinely spending 1.5-3x more wall-clock time (e.g., fl1400: 113s vs 219s; fl1577: 1172s vs 1921s; rl5934: 305s vs 1607s) while running the same MaxTrials. Equal-trials comparison therefore gives bandLKH a compute advantage, so part of the gap could just be more search effort. The paper does not report time-equalized results, so the 'significant' claim is not yet nailed down. The hyperparameters (Cmax, Narm, Ttype, epsilon, lambda) were tuned by SMAC3 on 'some sampled instances' without disclosure; if any of those are on the test set, the comparisons become circular. Finally, the CVRP numbers are mixed (56 vs 35 wins on best, 61 vs 35 on average), so calling that a 'significant enhancement' overstates.\n\nNone of this kills the paper. The mechanism is plausible, the implementation looks careful, and the LKH-Cmax ablation is a good control that partially offsets the compute-confound worry. But a serious referee should ask for time-equalized runs (or per-trial cost accounting), full disclosure of tuning instances, and more tempered claims on CVRP.\n\nVerdict: send it to review. The right outcome is probably conditional acceptance after those clarifications, not a desk reject.","headline":"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.","tokens_in":25244,"tokens_out":2648,"would_cite":false,"duration_ms":22460,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Per-city bandits that dynamically pick candidate edges from enlarged sets improve LKH and transfer to MTSP and CVRP.","keywords":["traveling salesman problem","multi-armed bandit","candidate edge selection","Lin-Kernighan-Helsgaun algorithm","local search","reinforcement learning","vehicle routing","LKH-3"],"falsifier":"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.","tokens_in":24241,"feed_emoji":"🎰","tokens_out":8638,"duration_ms":67989,"temperature":0.7,"pith_summary":"The paper argues that the Lin-Kernighan-Helsgaun (LKH) heuristic is held back by its fixed per-city candidate-edge lists, and that letting a set of multi-armed bandits choose those edges dynamically, from slightly enlarged lists, produces better tours with negligible extra cost. The resulting solver, bandLKH, attaches a bandit to each city; each trial the bandit pulls five candidate edges, the chosen edges steer the LKH search, and the bandit's M-values are updated by how much the resulting tour improves. On the paper's benchmark sets, bandLKH reaches the best-known optimum more often than LKH and reports an average gap about 57 percent smaller on the instances shown. The same bandit wrapper applied to LKH-3 also improves solution quality on MTSP and CVRP instances. A sympathetic reading of the reported experiments is that a small, learned, dynamic selection mechanism is a better use of freedom in candidate sets than either fixing them small or enlarging them without filtering.","feed_headline":"Per-city bandits pick better tour edges than LKH's fixed lists","feed_subtitle":"Each city's bandit chooses five candidate edges per search trial, cutting average gap to best-known by about 57 percent.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"The base LKH algorithm whose static per-city candidate sets bandLKH replaces.","marker":"[12]"},{"why":"Defines the alpha-value used to build the enlarged candidate sets and by the alpha-greedy pulling strategy.","marker":"[14]"},{"why":"The reinforcement-learning LKH variant that bandLKH is compared against and whose no-improvement-trial schedule informs T_type.","marker":"[15]"},{"why":"The deep-learning candidate-selection variant bandLKH is compared against.","marker":"[16]"},{"why":"The LKH extension for TSP variants that bandLKH-3 wraps.","marker":"[17]"},{"why":"Provides the multiple-pull bandit formulation used for selecting N_arm edges per trial.","marker":"[36]"},{"why":"Supplies the CVRP benchmark set used to evaluate bandLKH-3.","marker":"[37]"}],"fun_headline_variants":["Bandit picks dynamic edges, bests LKH's fixed lists","Adaptive edge selection via bandits boosts TSP solver","Dynamic candidate edges cut TSP gap 57% vs LKH","Bandit-powered LKH finds better tours on the fly","Smarter edge choice trims LKH's average gap by 57%"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Bandit picks dynamic edges, bests LKH's fixed lists","Adaptive edge selection via bandits boosts TSP solver","Dynamic candidate edges cut TSP gap 57% vs LKH","Bandit-powered LKH finds better tours on the fly","Smarter edge choice trims LKH's average gap by 57%"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000481,"raw_usage":{"total_tokens":2375,"prompt_tokens":936,"completion_tokens":1439,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":552,"completion_tokens_details":{"reasoning_tokens":1350}},"tokens_in":552,"tokens_out":1439,"duration_ms":9583,"temperature":1.0,"reasoning_tokens":1350,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T15:22:54.570534+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}