{"id":"60f1d0a2-e64b-4a36-af23-402a0eb0b243","arxiv_id":"2501.04072","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":5,"one_line_summary":"A modified LKH that re-ranks candidate edges with a dynamically updated backbone frequency and a bandit-chosen mix of metrics finds better tours on many large TSPLIB instances than stock LKH.","lead":"This paper adds a learning layer to the Lin-Kernighan-Helsgaun (LKH) solver for the traveling salesman problem, using search history to re-rank candidate edges and a multi-armed bandit to pick the ranking metric. The goal is to help the classic solver escape local optima and find better tours on large instances.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"CTSP comparison in Table 5 is internally inconsistent; the MABB-LKH-3 column appears row-shifted relative to LKH-3, so the claimed generalization to LKH-3 is unsupported by the reported data.","rationale":"I read the paper as claiming a general framework that boosts both LKH and LKH-3. The TSP experiments (Table 2) are extensive, and the mechanism (backbone + MAB) is plausible, though runtime overhead is not always accounted for. However, the generalization claim to LKH-3 is the advertised extra contribution, and it is supported by the CTSP and CVRPTW tables. Table 5 is demonstrably corrupted: the MABB-LKH-3 column matches a shifted copy of the LKH-3 column at least for the small-instance block, and large-instance entries look implausible. The text's summary counts do not match the table. This is an internal inconsistency, not a matter of consensus, and it directly undermines the central claim. The reader's formal weakest_assumption points to the pseudo-backbone/gamma mechanism, which I do not see as the decisive flaw; the table is. I therefore partially agree with the reader: same overall verdict, different primary concern.","tokens_in":25453,"tokens_out":8083,"duration_ms":65792,"concrete_test":"Obtain the per-instance CTSP results from the authors' public repository and compare each row of Table 5 against the logged outputs. Specifically, check whether the MABB-LKH-3 column is the LKH-3 column shifted by 16 rows (eil21-2 MABB = eil101-4 LKH); if so, the table must be regenerated with correct alignment. Then re-run the comparison on the 65 instances with MaxTrials=10,000 and 10 runs, and recompute the better/worse counts before any claim about CTSP is accepted.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim of significant improvement over LKH-3 for CTSP rests entirely on Table 5, and that table is internally inconsistent. Concretely, the MABB-LKH-3 value for eil21-2 is 726813, which is exactly the LKH-3 value reported for eil101-4; the MABB-LKH-3 value for eil31-4 is 144918, which is the LKH-3 value for eil21-2. This pattern holds across the small-instance block (a shift of 16 rows), and the large-instance block shows absurd values (e.g., fnl2461_3: MABB-LKH-3 best 64,074,850 vs LKH-3 best 105,477) that contradict the text's summary of 'better in 25, worse in 11' instances. The win/loss counts in the text cannot be derived from the printed numbers, so the CTSP comparison is not reproducible or trustworthy. Because the paper's generalization claim to LKH-3 is a central contribution, this internal inconsistency is load-bearing.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes MABB-LKH, an extension of the Lin-Kernighan-Helsgaun heuristic for TSP. The method maintains pseudo-backbone edge frequencies computed from its own historical local optima, combines them with alpha-values and distances through a weighted metric alpha_bd_w, and uses a UCB-based multi-armed bandit to select the combination weight in each trial. The same machinery is applied to LKH-3, yielding MABB-LKH-3, and is tested on CTSP and CVRPTW. The paper reports that MABB-LKH improves over LKH on 45 TSPLIB instances and over NeuroLKH on instances up to 6,000 cities, and that MABB-LKH-3 improves over LKH-3 on many CTSP and CVRPTW benchmarks, with an ablation study attributing part of the gain to the bandit mechanism.","tokens_in":25720,"tokens_out":10255,"duration_ms":91480,"significance":"If the reported results are taken at face value, the contribution is practically useful: it obtains state-of-the-art-quality TSP solutions with a lightweight, training-free mechanism that reuses search statistics, and the same recipe is plausibly portable to other LKH-3 solvable problems. The strengths include a broad TSP testbed (45 instances, ten runs each), a public code link, and an ablation study that isolates the MAB component. However, the central generalization claim to LKH-3 rests on a CTSP table that is internally inconsistent, and the experimental protocol leaves open a tuning-on-test-set explanation. These issues are load-bearing and must be resolved before the claims can be accepted.","major_comments":[{"comment":"The CTSP results in Table 5 are internally inconsistent and cannot support the claimed comparison. In the small-instance block, the MABB-LKH-3 column is a cyclic shift of the LKH-3 column: e.g., eil21-2 reports MABB-LKH-3 Best 726813, which is exactly the LKH-3 Best for eil101-4, and eil31-4 reports MABB-LKH-3 Best 144918, which is exactly the LKH-3 Best for eil21-2; the pattern continues through eil101-7. In the large-instance block, entries such as fnl2461_3 (MABB-LKH-3 Best 64,074,850 vs LKH-3 Best 105,477) differ by orders of magnitude. The text's summary that MABB-LKH-3 is 'better in 25, worse in 11' instances cannot be derived from the printed numbers. Because the LKH-3/CTSP generalization is a stated central contribution, this table must be corrected or that claim removed before the paper can be evaluated.","section":"Section 5.4, Table 5"},{"comment":"The hyperparameters bs, m, s, c, and gamma were tuned with SMAC3, but the manuscript does not state which instances were used for tuning. If the same TSPLIB, CTSP, and CVRPTW instances used in Tables 2-13 were used for tuning, then the reported comparisons are partly in-sample and the observed advantages may reflect parameter fitting rather than algorithmic merit. Please report the exact tuning protocol, including the instance sets and budget, and provide validation on held-out instances or a nested evaluation.","section":"Section 5.1.1, Table 1"},{"comment":"The CVRPTW comparison aggregates results over groups of instances and over 10 runs without reporting standard deviations, per-instance counts, or significance tests. Several claimed improvements are small enough to be within run-to-run variation; for example, Table 8 R1 improves only from 11750.58 to 11737.58 (about 0.11%), and Table 10 C1 improves from 7289.88 to 7264.20 (about 0.35%). The global statement of 'significant improvement' is not statistically supported without this information. Please provide per-instance results with variance estimates or appropriate significance tests.","section":"Section 5.4, Tables 6-13"}],"minor_comments":[{"comment":"'Lin-Kernighan-Helsguan' should be 'Lin-Kernighan-Helsgaun'.","section":"Abstract and keywords"},{"comment":"The sentence 'The comparison results between MABB-LKH with LKH-3' should read 'MABB-LKH-3 with LKH-3'.","section":"Section 5.4, first paragraph"},{"comment":"The captions repeatedly say 'Solomom'; this should be 'Solomon'.","section":"Tables 6-13 captions"},{"comment":"The x-axis instance order mixes different sizes, and the cumulative-gap curves are hard to distinguish for the smaller instances. Sorting by instance size and using distinct markers would improve readability.","section":"Figure 2"},{"comment":"The notation w_A_t is not defined explicitly; please state that w_A_t is the weight associated with the arm selected at trial t.","section":"Algorithm 1, line 14"},{"comment":"The indexing V_t^i overloads the trial subscript and the arm superscript; clarifying the time-step and arm indices would avoid ambiguity.","section":"Equation (7)"}],"recommendation":"major_revision","confidential_remarks":"The Table 5 inconsistency is severe and should be treated as a data-integrity matter, not a formatting nit: the MABB-LKH-3 column appears to be a misaligned copy of the LKH-3 column. Before any revision is evaluated, the authors should be asked to provide raw per-run logs for the CTSP experiments and to clarify whether the same benchmark instances were used for SMAC3 tuning. If the corrected data do not support the current claims, rejection would be appropriate."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things worth knowing. The TSP half of this paper is a credible incremental contribution: a dynamic pseudo-backbone, refreshed at every local optimum, combined with the alpha-value and distance, with a UCB bandit choosing the mixing weight per trial. The ablation in Figure 2 does the right thing—it compares fixed-weight variants against the MAB version—and the TSPLIB results on 45 instances up to 85,900 cities are extensive, with 10 runs, success counts, averages, trials, and times reported. The proposed update rule (Eq. 2) and UCB-selected metric mix (Eqs. 4-5) are not in the cited literature; prior backbone work was static, and VSR-LKH replaced alpha with a Q-value rather than combining three metrics adaptively. That part deserves a real look.\n\nThe CTSP half, as printed, does not support the paper's generalization claim. Table 5 is internally inconsistent: the MABB-LKH-3 column appears row-shifted against LKH-3 (eil21-2 shows 726813, which is LKH-3's value for eil101-4), and the large-instance block shows MABB-LKH-3 with best solutions 100-1000x worse than LKH-3 (fnl2461_3: 64,074,850 vs 105,477), directly contradicting the text's summary of 'better in 25, worse in 11.' Those counts cannot be recovered from the printed numbers. This is not a minor typo; it is the only evidence for the LKH-3 generalization claim, and it cannot be trusted.\n\nTwo softer issues. The five hyperparameters were tuned with SMAC3 on the same benchmarks, and the paper does not separate tuning from evaluation or report significance, so part of the TSP gain may be fitted rather than predicted. Also, wall-clock time is often worse for MABB-LKH (pla33810: 83k seconds vs 46k), and the small-instance regressions (gr666) are downplayed in the abstract.\n\nWho this is for: people building learning wrappers around LKH and those who care about cheap, historically guided candidate-edge selection. The TSP results deserve a serious referee; the CTSP table needs to be fixed or removed. I would send it out and let the authors repair the damaged generalization claim.","headline":"Solid incremental TSP results undermined by a broken CTSP table that sinks the LKH-3 generalization claim.","tokens_in":26239,"tokens_out":3472,"would_cite":false,"duration_ms":30474,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C27","90C59"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that adding a dynamically updated backbone frequency and a multi-armed bandit metric selector to LKH improves its ability to find optimal TSP tours, and that the same mechanism improves LKH-3 on CTSP and CVRPTW.","keywords":["traveling salesman problem","Lin-Kernighan-Helsgaun algorithm","multi-armed bandit","backbone information","local search","vehicle routing problem","colored TSP","capacitated VRP with time windows"],"falsifier":"On a hard TSP instance with a known optimum, record after the first 100 trials how many of the 100 most frequent backbone edges actually belong to the optimal tour. If that count is no higher than the count for a random edge sample, the backbone signal is uninformative and the claimed improvement must come from the bandit's metric diversity alone.","tokens_in":25239,"feed_emoji":"🎰","tokens_out":7452,"duration_ms":69513,"temperature":0.7,"pith_summary":"Traveling salesman heuristics live or die by which edges they consider promising. LKH ranks candidate edges by the alpha-value, a fixed, globally computed measure, and the paper argues that this single fixed guide gets stuck in local optima. The paper claims that supplementing alpha with raw distance and a dynamically updated backbone frequency, the fraction of past local optima containing each edge, lets the search escape more often. A multi-armed bandit chooses, trial by trial, how to weight the three signals, and the resulting algorithm finds known optimal tours more often and in fewer trials than LKH on many instances with 500 to 85,900 cities. The same recipe inside LKH-3 is claimed to improve two routing variants, Colored TSP and Capacitated VRP with Time Windows.","feed_headline":"Bandit and backbone steer TSP search to more optima","feed_subtitle":"A multi-armed bandit picks how to weight alpha, distance, and historical edge popularity, and LKH finds known optima faster.","key_machinery":"The object that carries the argument is the $\\alpha bd_w$ evaluation metric, a normalized weighted sum of the $\\alpha$-value and the $bd$-value, where $bd$ multiplies edge distance by $(1-b_{ij})$. The multi-armed bandit is the selector: at trial $t$ it picks arm $A_t$ with weight $w_{A_t}$, applies a discount $\\gamma^{t-b_s}$ to gradually raise backbone influence, re-sorts each city's candidate set by $\\alpha bd_w$, and runs the standard LinKernighan trial; the reward measures how much closer the resulting local optimum came to the lower bound. This mechanism turns accumulated search history into a changing guide for future candidate-edge choices.","core_discovery":"The central discovery is that historical edge popularity, pseudo-backbone information extracted for free from the solver's own local optima, can be folded into LKH's candidate-edge ordering in a way that helps rather than hurts. The paper defines $b_{ij}=\\eta_{ij}/t$, the fraction of completed trials in which edge $(i,j)$ appeared in a local optimum, combines it with distance into $bd(i,j)=(1-b_{ij})d(i,j)$, then normalizes and blends this with the $\\alpha$-value through a weight $w$ to get the $\\alpha bd_w$-value. Instead of committing to one $w$, the algorithm maintains a UCB bandit whose arms are different $w$ values; after each trial it rewards the chosen arm according to how much closer the local optimum came to the lower bound. A discount factor $\\gamma^{t-b_s}$ gradually raises the backbone's influence as trials accumulate. The paper's experiments are presented as showing that this adaptive reordering of candidate edges, with no change to the underlying $k$-opt operator, improves solution quality and reduces trials-to-optimum compared with LKH, and that the same mechanism improves LKH-3 on the two tested routing variants.","pith_inferences":["The reward in Equation (6) depends on the quality of the lower bound $L(T)$; on problem families with weak lower bounds, such as some asymmetric or non-metric instances, the bandit's reward signal would be noisier, so the method's transfer may be less smooth than the two tested VRP variants suggest.","A direct test of the backbone hypothesis would compare MABB-LKH against a version using an oracle edge frequency derived from the known optimal tour; the gap between the two would quantify how much headroom remains in the pseudo-backbone extraction.","The fixed geometric discount schedule $\\gamma^{t-b_s}$ is a modelling choice; an adaptive schedule driven by the bandit's own confidence could make the method robust to instances where backbone information is slow to stabilize.","Because the method only re-orders candidate edges, it could be composed with learned candidate-edge generators rather than viewed as an alternative: the backbone and bandit would then guide a smaller, pre-filtered candidate set."],"forward_implications":["LKH's candidate-order mechanism can be made adaptive without altering the $k$-opt core, so any LK-family solver could adopt the same bandit-plus-backbone wrapper.","On instances where LKH already finds the optimum, MABB-LKH typically reaches it in fewer trials, so the practical gain is time-to-optimum as well as success rate on hard instances.","The extension to LKH-3 implies the method transfers to constrained and vehicle-routing problems that are solved by transformation to constrained TSP.","The ablation results imply that no single hand-tuned weighting of alpha, distance, and backbone dominates; the bandit's dynamic choice is what provides the gain.","Because the backbone needs roughly 100 trials to accumulate, the benefit is small on very short runs and grows with instance size, consistent with the paper's observation that the cumulative gap widens on larger instances."],"supporting_citations":[{"why":"The base LKH solver under study; supplies the k-opt trial loop, candidate sets, and the LinKernighan() routine the paper wraps.","marker":"[9]"},{"why":"Defines the minimum 1-tree lower bound from which the alpha-value in Equation (1) is computed, the global metric the paper extends.","marker":"[16]"},{"why":"Introduces backbone-guided TSP local search and the earlier backbone-times-distance combination that motivates the bd-value in Equation (3).","marker":"[18]"},{"why":"The LKH lineage that generalizes k-opt submoves and already considered backbone candidate edges, which the paper says had limited effect and now reworks.","marker":"[15]"},{"why":"The LKH-3 extension to constrained TSP and VRP that MABB-LKH-3 modifies; provides the CTSP and CVRPTW solving framework.","marker":"[23]"},{"why":"The deep-learning baseline NeuroLKH whose fixed learned candidate edges are compared against MABB-LKH's adaptive reordering in Tables 3 and 4.","marker":"[33]"},{"why":"Source of the upper-confidence-bound arm-selection rule used in Equation (5) for the bandit.","marker":"[40]"}],"fun_headline_variants":["Bandit tunes edge metric, LKH finds better tours","Historical edge popularity guides TSP heuristic","Bandit picks edge weights to speed LKH search","LKH learns edge scoring from its own history","Pseudo-backbone edges push LKH past local optima"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that edges appearing often in the solver's own past local optima are genuinely better edges, and that the fixed schedule for trusting them more over time helps instead of misleads.","fun_headline_variants_meta":{"raw":{"variants":["Bandit tunes edge metric, LKH finds better tours","Historical edge popularity guides TSP heuristic","Bandit picks edge weights to speed LKH search","LKH learns edge scoring from its own history","Pseudo-backbone edges push LKH past local optima"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00083,"raw_usage":{"total_tokens":3704,"prompt_tokens":1106,"completion_tokens":2598,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":722,"completion_tokens_details":{"reasoning_tokens":2523}},"tokens_in":722,"tokens_out":2598,"duration_ms":16015,"temperature":1.0,"reasoning_tokens":2523,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T21:44:39.169886+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On a hard TSP instance with a known optimum, record after the first 100 trials how many of the 100 most frequent backbone edges actually belong to the optimal tour. If that count is no higher than the count for a random edge sample, the backbone signal is uninformative and the claimed improvement must come from the bandit's metric diversity alone.","supporting_citations":[{"cited_title":"An effective implementation of the Lin–Kernighan traveling salesman heuristic.European Journal of Operational Re- search, 126(1):106–130, 2000","cited_arxiv_id":null,"evidence_quote":"The base LKH solver under study; supplies the k-opt trial loop, candidate sets, and the LinKernighan() routine the paper wraps."},{"cited_title":"Thetraveling-salesmanproblem and minimum spanning trees","cited_arxiv_id":null,"evidence_quote":"Defines the minimum 1-tree lower bound from which the alpha-value in Equation (1) is computed, the global metric the paper extends."},{"cited_title":"A novel local search algorithm for the traveling salesman problem that exploits backbones","cited_arxiv_id":null,"evidence_quote":"Introduces backbone-guided TSP local search and the earlier backbone-times-distance combination that motivates the bd-value in Equation (3)."},{"cited_title":"General k-opt submoves for the Lin–Kernighan TSPheuristic","cited_arxiv_id":null,"evidence_quote":"The LKH lineage that generalizes k-opt submoves and already considered backbone candidate edges, which the paper says had limited effect and now reworks."},{"cited_title":"An extension of the Lin-Kernighan-Helsgaun TSP solver for constrained traveling salesman and vehicle routing prob- lems","cited_arxiv_id":null,"evidence_quote":"The LKH-3 extension to constrained TSP and VRP that MABB-LKH-3 modifies; provides the CTSP and CVRPTW solving framework."},{"cited_title":"NeuroLKH: Combining deep learning model with Lin-Kernighan-Helsgaun heuristic for solving the traveling salesman problem","cited_arxiv_id":null,"evidence_quote":"The deep-learning baseline NeuroLKH whose fixed learned candidate edges are compared against MABB-LKH's adaptive reordering in Tables 3 and 4."},{"cited_title":"Cascaded algorithm-selection and hyper-parameter optimization with extreme-region upper confi- dence bound bandit","cited_arxiv_id":null,"evidence_quote":"Source of the upper-confidence-bound arm-selection rule used in Equation (5) for the bandit."}],"review_version":1}