Skip to Main content Skip to Navigation
New interface
Journal articles

Neighborhood Structures for GPU-based Local Search Algorithms

Thé Van Luong 1 Nouredine Melab 1 El-Ghazali Talbi 1 
1 DOLPHIN - Parallel Cooperative Multi-criteria Optimization
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe
Abstract : Local search algorithms are powerful heuristics for solving computationally hard problems in science and industry. In these methods, designing neighborhood operators to explore large promising regions of the search space may improve the quality of the obtained solutions at the expense of a high computation process. As a consequence, the use of GPU computing provides an efficient way to speed up the search. However, designing applications on GPU is still complex and many issues have to be faced. We provide a methodology to design and implement different neighborhood structures for LS algorithms on GPU. The work has been evaluated for binary problems and the obtained results are convincing both in terms of efficiency, quality and robustness of the provided solutions at run time.
Document type :
Journal articles
Complete list of metadata

Cited literature [10 references]  Display  Hide  Download
Contributor : Thé Van Luong Connect in order to contact the contributor
Submitted on : Thursday, September 23, 2010 - 12:22:57 PM
Last modification on : Friday, March 11, 2022 - 3:10:07 PM
Long-term archiving on: : Friday, December 24, 2010 - 2:46:13 AM


Files produced by the author(s)



Thé Van Luong, Nouredine Melab, El-Ghazali Talbi. Neighborhood Structures for GPU-based Local Search Algorithms. Parallel Processing Letters, 2010, 20 (4), pp.307-324. ⟨10.1142/S0129626410000260⟩. ⟨inria-00520461⟩



Record views


Files downloads