On parallel local search for permutations

On parallel local search for permutations

0.00 Avg rating0 Votes
Article ID: iaor201525814
Volume: 66
Issue: 5
Start Page Number: 822
End Page Number: 831
Publication Date: May 2015
Journal: Journal of the Operational Research Society
Authors: ,
Keywords: heuristics, heuristics: local search
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.

Reviews

Required fields are marked *. Your email address will not be published.