×

Analysis of a high-performance TSP solver on the GPU. (English) Zbl 1414.68150

MSC:

68W40 Analysis of algorithms
68W10 Parallel algorithms in computer science
90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming

Keywords:

2-opt; CUDA; GPGPU; TSP; \(k\)-swap

Software:

TSPLIB; OpenCL; CUDA
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] David L. Applegate, Robert E. Bixby, Vasek Chvatal, and William J. Cook. 2007. The Traveling Salesman Problem: A Computational Study (Princeton Series in Applied Mathematics). Princeton University Press, Princeton, NJ. · Zbl 0904.90165
[2] Peter Bakkum and Kevin Skadron. 2010. Accelerating SQL database operations on a GPU with CUDA. In Proceedings of the 3rd Workshop on General-Purpose Computation on Graphics Processing Units (GPGPU’10). ACM, New York, NY, 94-103.
[3] Ian Buck, Tim Foley, Daniel Horn, Jeremy Sugerman, Kayvon Fatahalian, Mike Houston, and Pat Hanrahan. 2004. Brook for GPUs: Stream computing on graphics hardware. ACM Trans. Graph. 23, 3 (Aug. 2004), 777-786.
[4] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms (3rd ed.). The MIT Press. · Zbl 1187.68679
[5] A. Croes. 1958. A method for solving traveling salesman problems. Operat. Res. 5 (1958), 791-812. · Zbl 1414.90303
[6] Matthias Englert, Heiko Röglin, and Berthold Vöcking. 2014. Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP. Algorithmica 68, 1 (2014), 190-264. · Zbl 1358.68131
[7] David S. Johnson and Lyle A. Mcgeoch. 1997. The Traveling Salesman Problem: A Case Study in Local Optimization. John Wiley and Sons, London. · Zbl 0947.90612
[8] Tonci Caric Juraj Fosin, Davor Davidovic. 2013. A GPU implementation of local search operators for symmetric travelling salesman problem. PROMIT—Traffic and Transportation 25, 3 (2013), 225-234.
[9] E. Scott Larsen and David McAllister. 2001. Fast matrix multiplies using graphics hardware. In Proceedings of the 2001 ACM/IEEE Conference on Supercomputing (SC’01). ACM, New York, NY, 55-55.
[10] Marek Libura, Edo S. van der Poort, Gerard Sierksma, and Jack A. A. van der Veen. 1998. Stability aspects of the traveling salesman problem based on k-best solutions. Discrete Appl. Math. 87, 13 (1998), 159-185. · Zbl 0910.90264
[11] Shen Lin and Brian W. Kernighan. 1973. An effective heuristic algorithm for the travelling-salesman problem. Operat. Res. 21 (1973), 498-516. · Zbl 0256.90038
[12] Michael McCool and Stefanus Du Toit. 2004. Metaprogramming GPUs with Sh. AK Peters Ltd.
[13] NVIDIA Corporation. 2007. NVIDIA CUDA Compute Unified Device Architecture Programming Guide. NVIDIA Corporation.
[14] Molly A. O’Neil and Martin Burtscher. 2015. Rethinking the parallelization of random-restart hill climbing: A case study in optimizing a 2-opt TSP solver for GPU execution. In Proceedings of the 8th Workshop on General Purpose Processing Using GPUs (GPGPU’15). ACM, New York, NY, 99-108.
[15] Molly A. O’neil, Dan Tamir, and Martin Burtscher. 2011. A parallel GPU version of the traveling salesman problem. In 2011 International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA’11). Las Vegas, NV.
[16] Gerhard Reinelt. 1991. TSPLIB—Traveling salesman problem library. ORSA J. Comput. 3, 4 (21 Nov. 1991), 376-384. · Zbl 0775.90293
[17] Kamil Rocki and Reiji Suda. 2013. High-performance GPU accelerated local optimization in TSP. In Proceedings of the 2013 IEEE 27th International Symposium on Parallel and Distributed Processing Workshops and PhD Forum (IPDPSW’13). IEEE Computer Society, Washington, DC, 1788-1796.
[18] John E. Stone, David Gohara, and Guochun Shi. 2010. OpenCL: A parallel programming standard for heterogeneous computing systems. IEEE Des. Test 12, 3 (May 2010), 66-73.
[19] D. Strigl, K. Kofler, and S. Podlipnig. 2010. Performance and scalability of GPU-based convolutional neural networks. In Proceedings of the 2010 18th Euromicro International Conference on Parallel, Distributed and Network-Based Processing (PDP’10). 317-324.
[20] Akihiro Uchida, Yasuaki Ito, and Koji Nakano. 2012. An efficient GPU implementation of ant colony optimization for the traveling salesman problem. In Proceedings of the 2013 International Conference on Computing, Networking and Communications (ICNC’12), 94-102.
[21] M. G. A. Verhoeven, E. H. L. Aarts, and P. C. J. Swinkels. 1995. A parallel 2-opt algorithm for the traveling salesman problem. Future Gener. Comput. Syst. 11, 2 (March 1995), 175-182.
[22] Hongjian Wang, Naiyu Zhang, and Jean-Charles Crput. 2013. A massive parallel cellular GPU implementation of neural network to large scale euclidean TSP. In Advances in Soft Computing and Its Applications, Felix Castro, Alexander Gelbukh, and Miguel Gonzalez (Eds.). Lecture Notes in Computer Science, Vol. 8266. Springer, Berlin, 118-129.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.