Skip to Main content Skip to Navigation
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 metadatas

Cited literature [10 references]  Display  Hide  Download

https://hal.inria.fr/inria-00520461
Contributor : Thé Van Luong <>
Submitted on : Thursday, September 23, 2010 - 12:22:57 PM
Last modification on : Thursday, May 28, 2020 - 9:22:09 AM
Document(s) archivé(s) le : Friday, December 24, 2010 - 2:46:13 AM

File

PPL.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00520461, version 1

Citation

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

Share

Metrics

Record views

373

Files downloads

745