Skip to Main content Skip to Navigation
Conference papers

Multi-start local search algorithms on GPU

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. Even if local search (LS) algorithms allow to significantly reduce the computation time cost of the solution exploration space, the use of parallelism is required to accelerate the search process. Indeed, LSs are inherently parallel and three parallel models are often used to solve efficiently large combinatorial problems: algorithmic-level (multi-start model), iteration-level (parallel evaluation of the neighborhood), and the solution-level (parallel evaluation of a single solution). The main objective of this paper is to deal with the algorithmic-level on GPU architectures where many LSs are executed in parallel. More exactly, we propose to study different schemes of deployment for the design of multi-start LSs on GPU based on popular hill climbing (HC), simulated annealing (SA) and tabu search (TS).
Document type :
Conference papers
Complete list of metadatas

Cited literature [2 references]  Display  Hide  Download

https://hal.inria.fr/inria-00520469
Contributor : Thé Van Luong <>
Submitted on : Thursday, September 23, 2010 - 1:02:31 PM
Last modification on : Thursday, May 28, 2020 - 9:22:09 AM
Document(s) archivé(s) le : Friday, December 24, 2010 - 2:48:32 AM

File

meta10.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00520469, version 1

Citation

Thé Van Luong, Nouredine Melab, El-Ghazali Talbi. Multi-start local search algorithms on GPU. International Conference on Metaheuristics and Nature Inspired Computing (META), 2010, Djerba, Tunisia. ⟨inria-00520469⟩

Share

Metrics

Record views

344

Files downloads

214