Skip to Main content Skip to Navigation
Conference papers

GPU-based Multi-start 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 : In practice, combinatorial optimization problems are complex and computationally time-intensive. Local search algorithms are powerful heuristics which allow to significantly reduce the computation time cost of the solution exploration space. In these algorithms, the multi-start model may improve the quality and the robustness of the obtained solutions. However, solving large size and time-intensive optimization problems with this model requires a large amount of computational resources. GPU computing is recently revealed as a powerful way to harness these resources. In this paper, the focus is on the multi-start model for local search algorithms on GPU. We address its re-design, implementation and associated issues related to the GPU execution context. The preliminary results demonstrate the effectiveness of the proposed approaches and their capabilities to exploit the GPU architecture.
Document type :
Conference papers
Complete list of metadatas

Cited literature [14 references]  Display  Hide  Download

https://hal.inria.fr/inria-00638813
Contributor : Thé Van Luong <>
Submitted on : Monday, November 7, 2011 - 3:53:28 PM
Last modification on : Thursday, May 28, 2020 - 9:22:09 AM
Document(s) archivé(s) le : Wednesday, February 8, 2012 - 2:30:40 AM

File

LION5.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00638813, version 1

Citation

Thé Van Luong, Nouredine Melab, El-Ghazali Talbi. GPU-based Multi-start Local Search Algorithms. Learning and Intelligent Optimization, 2011, Rome, Italy. ⟨inria-00638813⟩

Share

Metrics

Record views

400

Files downloads

814