Abstract
We investigate some ways in which massively parallel computing devices can be exploited in local search algorithms. We show that the substantial speedups that can be gained from parallel neighbourhood evaluation enables an efficient best improvement local search, and that this in turn enables further speedups through selection and parallel application of a set of independent, improving moves. Our experiments demonstrate a total speedup of up to several hundred times compared to a classical, sequential best improvement search. We also demonstrate how an exchange of good partial solutions between the incumbent and best found solutions improves the efficiency of the Iterated Local Search algorithm.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Ahuja RK, Ergun Ö, Orlin JB and Punnen AP (2002). A survey of very large-scale neighborhood search techniques. Discrete Applied Mathematics 123 (1–3): 75–102.
Applegate DL, Bixby RE, Chvatal V and Cook WJ (2007). The Traveling Salesman Problem: A Computational Study (Princeton Series in Applied Mathematics). Princeton University Press: Princeton, NJ.
Brodtkorb AR, Dyken C, Hagen TR, Hjelmervik JM and Storaasli OO (2010). State-of-the-art in heterogeneous computing. Scientific Programming 18 (1): 1–33.
Burke EK and Kendall G (2005). Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques. Springer: New York.
Congram RK, Potts CN and van de Velde SL (2002). An iterated dynasearch algorithm for the single-machine total weighted tardiness scheduling problem. INFORMS Journal on Computing 14 (1): 52–67.
Cook W and Seymour P (2003). Tour merging via branch-decomposition. INFORMS Journal on Computing 15 (3): 233–248.
Deineko VG and Woeginger GJ (2000). A study of exponential neighborhoods for the travelling salesman problem and for the quadratic assignment problem. Mathematical Programming 87 (3): 519–542.
Ergun Z, Orlin JB and Steele-Feldman A (2006). Creating very large scale neighborhoods out of smaller ones by compounding moves. Journal of Heuristics 12 (1–2): 115–140.
Glover F and Kochenberger G (2003). Handbook of Metaheuristics (International Series in Operations Research & Management Science). Springer: Dordrecht, The Netherlands.
Hansen P and Mladenovic N (2001). Variable neighborhood search: Principles and applications. European Journal of Operational Research 130 (3): 449–467.
Harding S and Banzhaf W (2007). Fast genetic programming on GPUs. In: Ebner M, O‘Neill M, Ekárt A, Vanneschi L and Esparcia-Alcázar (eds). Genetic Programming. Lecture Notes in Computer Science Vol. 4445. Springer: New York, pp 90–101.
Hoos HH and Stützle T (2005). Stochastic Local Search: Foundations and Applications. Morgan Kaufmann: San Francisco, CA.
Janiak A, Janiak W and Lichtenstein M (2008). Tabu search on GPU. Journal of Universal Computer Science 14 (14): 2416–2427.
Karp RM (1972). Reducibility among combinatorial problems. In: Miller RE and Thatcher JW (eds). Complexity of Computer Computations. Plenum Press: New York, pp 85–103.
Langdon W and Banzhaf W (2008). A SIMD interpreter for genetic programming on GPU graphics cards. In: O’Neill M et al (eds). Genetic Programming. Lecture Notes in Computer Science Vol. 4971. Springer: New York, pp 73–85.
Lourenço HRD, Martin OC and Stützle T (2002). Iterated local search. In: Glover F and Kochenberger G (eds). Handbook of Metaheuristics. Kluwer Academic Publishers: Norwell, MA, pp 321–353.
Luong TV, Melab N and Talbi E-G (2009). Parallel local search on GPU. Rapport de recherche RR-6915, INRIA.
Owens JD, Houston M, Luebke D, Green S, Stone JE and Phillips JC (2008). GPU computing. Proceedings of the IEEE 96 (5): 879–899.
Schatz M and Trapnell C (2007). Fast Exact String Matching on the GPU. University of Maryland. Technical report.
Stützle T and Hoos HH (2001). Analysing the run-time behaviour of iterated local search for the travelling salesman problem. In: Hansen P and Ribeiro CC (eds). Essays and Surveys in Metaheuristics. Operations Research/Computer Science Interfaces Series, Springer: New York, pp 589–611.
Yu Q, Chen C and Pan Z (2005). Parallel genetic algorithms on programmable graphics hardware. In: Wang L, Chen K and Ong YS (eds). Advances in Natural Computation. Lecture Notes in Computer Science Vol. 3612. Springer: New York, pp 1051–1059.
Zhongwen L and Hongzhi L (2006). Cellular Genetic Algorithms and Local Search for 3-SAT Problem on Graphic Hardware. IEEE Congress on Evolutionary Computation, 2006. CEC 2006: Vancouver, Canada.
Acknowledgements
We thank colleagues at SINTEF ICT, Department of Applied Mathematics, especially Christopher Dyken, Johan S. Seland, Geir Hasle, and Oddvar Kloster for valuable input and interesting discussions. This work is supported by the Research Council of Norway and the UK Engineering and Physical Sciences Research Council (EPSRC).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Riise, A., Burke, E. On parallel local search for permutations. J Oper Res Soc 66, 822–831 (2015). https://doi.org/10.1057/jors.2014.29
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1057/jors.2014.29