Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
Solving the Asymmetric Traveling Salesman Problem via Trace-Guided Cost Augmentation
Authors: Zhen Zhang, Prof Javen Qinfeng Shi, Wee Sun Lee
NeurIPS 2025 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Empirically, our method achieves state-of-the-art performance on standard asymmetric TSP benchmarks and demonstrates strong scalability and accuracy, particularly on large or highly asymmetric instances where heuristic solvers such as LKH-3 often struggle. ... Extensive experiments show our method outperforms LKH-3 on ATSP benchmarks and scales well to large problem sizes. ... In Section 5, Experimental Results, the paper presents comparisons of methods on various ATSP and symmetric TSP instances, reporting Avg. GAP, Median GAP, and Runtime (s) in tables, clearly indicating an empirical evaluation. |
| Researcher Affiliation | Academia | Zhen Zhang 1Responsible AI Research Centre Australian Institute for Machine Learning 2The University of Adelaide & 3CSRIO EMAIL Javen Qingfeng Shi 1Responsible AI Research Centre Australian Institute for Machine Learning 2The University of Adelaide EMAIL Wee Sun Lee School of Computing National University of Singapore EMAIL |
| Pseudocode | Yes | Algorithm 1 Approximate Projected Gradient Descent for Exponentiated TSP Relaxation 1: Input: Cost matrix D Rn n, initial step size α > 0, scaling factor γ > 0, max iterations T 2: Initialize Y D 3: Compute initial assignment πprev Linear Assignment( Y) 4: for t = 1 to T do 5: Compute gradient: Yf(Y) = D exp(Y) + λ i=0 (i + 1) exp(Y)i # 6: Update Ynew Y α Yf(Y) 7: Project: X = Sinkhorn(exp(Ynew)), Ynew log(X) elementwise projection onto Dn 8: Compute new assignment πnew Linear Assignment( Ynew) 9: if πnew = πprev then 10: α α/2 11: else 12: α 2α 13: end if 14: Y Ynew, πprev πnew 15: if πnew has only one loop then 16: break 17: end if 18: end for 19: Output: Y, permutation πnew |
| Open Source Code | No | Answer: [No] Justification: The code will be made publication after publication. |
| Open Datasets | Yes | We evaluate our method on randomly generated Asymmetric TSP (ATSP) instances of sizes 20, 50, 100, 200, 500, and 1000. Following prior works [16], the cost matrices for these instances are generated by sampling each entry independently from a uniform distribution over the interval [0, 1]. ... Additionally, we evaluate our approach on symmetric TSP instances of sizes 20 and 50. ... We evaluated our algorithm on large-scale ATSP benchmark instances from TSPLIB, particularly those derived from stacker crane problems. |
| Dataset Splits | No | The paper describes how instances were randomly generated and evaluated (e.g., "average from 128 instances"), but does not specify traditional training/test/validation splits for machine learning experiments from a pre-existing dataset. The datasets used are either randomly generated for evaluation or established benchmarks like TSPLIB which do not typically involve such splits for this type of problem. |
| Hardware Specification | Yes | All experiments were conducted on a workstation equipped with an AMD Ryzen 9 3900X CPU, 128GB DDR4 memory, and an NVIDIA RTX 3090 GPU. |
| Software Dependencies | No | Our proposed method was implemented using Python and Sci Py, and it was also executed on a single CPU process without utilizing the GPU. |
| Experiment Setup | Yes | Algorithm 1 Approximate Projected Gradient Descent for Exponentiated TSP Relaxation 1: Input: Cost matrix D Rn n, initial step size α > 0, scaling factor γ > 0, max iterations T |