On parallel local search for permutations

Atle Riise and Edmund K Burke
Additional contact information
Atle Riise: SINTEF ICT, Department of Applied Mathematics, University of Oslo, Oslo, Norway
Edmund K Burke: University of Stirling, Stirling, UK

Journal of the Operational Research Society, 2015, vol. 66, issue 5, 822-831

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.

Date: 2015
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.palgrave-journals.com/jors/journal/v66/n5/pdf/jors201429a.pdf Link to full text PDF (application/pdf)
http://www.palgrave-journals.com/jors/journal/v66/n5/full/jors201429a.html Link to full text HTML (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:pal:jorsoc:v:66:y:2015:i:5:p:822-831

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/41274

Access Statistics for this article

Journal of the Operational Research Society is currently edited by Tom Archibald and Jonathan Crook

More articles in Journal of the Operational Research Society from Palgrave Macmillan, The OR Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().