On parallel local search for permutations

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.

Keywords:

• optimisation
• parallel local search
• Iterated Local Search
• GPU
• SPMD
• permutations
• Travelling Salesman Problem

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).