Other RL-trained NAR methods

[henry-yeh]

Hey there! This is a great work~ Just wanted to kindly remind you of other RL-trained NAR methods for TSP:

[1] DeepACO: Neural-enhanced Ant Systems for Combinatorial Optimization [2] Combining Reinforcement Learning and Optimal Transport for the Traveling Salesman Problem [3] DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problems

[henry-yeh]

Also, I would be honored if you have interest in GLOP [4], where we use RL-trained NAR method for dividing VRP into TSPs, and offer a unified perspective for NAR and AR.

[4] GLOP: Learning Global Partition and Local Construction for Solving Large-scale Routing Problems in Real-time

[xybFight]

Thank you for your attention and interest in our work NAR4TSP.

NAR4TSP is an early piece of research, finalized in January 2022 and submitted for review in April of the same year. Unfortunately, due to the extended review period, we had to share our findings on arXiv in August 2023. We acknowledge the possibility of overlooking more recent works and consider incorporating relevant references as suggested once we receive feedback from the review process.

Regarding the RL-based NAR TSP solvers you mentioned, we would like to offer the following clarifications:

1. Our primary objective with the NAR architecture is to enhance the model's inference speed, further amplifying the advantages of using neural network models (i.e., replace intensive computations by a fast approximation [1]). In the reference to [2], which appears employ an iterative method based on the ant colony algorithm, we believe its inference speed may not surpass AM [3], let alone compare with NAR4TSP. We contend that given enough time for inference, existing exact solver like Concorde might be suffice without the need for neural network-based models.

2. References [4] and [5] share similar ideas with NAR4TSP. We would like to point out that NAR4TSP, being an early work, aims to explore the integration of RL and NAR approaches. NAR4TSP establishes the feasibility of obtaining returns in RL through the decoding of heatmaps (with experimental results support), serving as a foundation for our subsequent work, GANRKD [6].

3. Reference [7] seems to address large-scale TSPs based on the divide-and-conquer idea, which may not be directly relevant to the research topic of NAR4TSP (the basic NAR TSP model, more relevant to GCN [8]). We anticipate that this may become the subject of our follow-up research.

In summary, we believe that our work, NAR4TSP [9] and GNARKD [6], introduces a unique perspective to the NCO community by prioritizing the improvement of inference speed rather than merely trading time for solution quality. We kindly request that you quote from our article if you find our viewpoints relevant and useful.

Thank you once again for your interest in our work.

[1] Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: a methodological tour d’horizon. European Journal of Operational Research, 290:405–421, 2021. [2] Haoran Ye, Jiarui Wang, Zhiguang Cao, Helan Liang, and Yong Li. DeepACO: Neural-enhanced ant systems for combinatorial optimization. In Proceedings of Advances in Neural Information Processing Systems, 2023 [3] Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn to solve routing problems! In Proceedings of International Conference on Learning Representations, 2019. [4] Ruizhong Qiu and Zhiqing Sun and Yiming Yang. DIMES, A Differentiable Meta Solver for Combinatorial Optimization Problems. In Proceedings of Advances in Neural Information Processing Systems, 2022. [5] Yong Liang Goh, Wee Sun Lee, Xavier Bresson, Thomas Laurent, and Nicholas Lim. Combining Reinforcement Learning and Optimal Transport for the Traveling Salesman Problem. Arxiv: 2203.00903. [6] Yubin Xiao, Di Wang, Boyang Li, Mingzhao Wang, Xuan Wu, Changliang Zhou, You Zhou. Distilling Autoregressive Models to Obtain High-Performance Non-Autoregressive Solvers for Vehicle Routing Problems with Faster Inference Speed. In Proceedings of the AAAI Conference on Artificial Intelligence, 2024. [7] Haoran Ye, Jiarui Wang, Helan Liang, Zhiguang Cao, Yong Li, and Fanzhang Li. GLOP: Learning Global Partition and Local Construction for Solving Large-scale Routing Problems in Real Time. In Proceedings of the AAAI Conference on Artificial Intelligence, 2024. [8] Joshi, C. K.; Laurent, T.; and Bresson, X. 2019. An efficient graph convolutional network technique for the travelling salesman problem. In Proceedings of INFORMS Annual Meeting, Session on Boosting Combinatorial Optimization using Machine Learning, 1–17. [9] Yubin Xiao, Di Wang, Boyang Li, Huanhuan Chen, Wei Pang, Xuan Wu, Hao Li, Dong Xu, Yanchun Liang, and You Zhou. Reinforcement Learning-based Non-Autoregressive Solver for Traveling Salesman Problems. Arxiv: 2308.00560.

[henry-yeh]

I see! Thank you for such a comprehensive clarification! Your works are awesome. We definitely find many insights from them and will cite them in our future work~

Best of luck with your submission and future works, we are keen to follow them 🚀