GPU-based Multi-start Local Search Algorithms
INRIA Dolphin Project / Opac LIFL CNRS, 40 avenue Halley, 59650 Villeneuve d’Ascq Cedex, France
inria-00638813, 2011
@inproceedings{LUONG:2011:INRIA-00638813:1,
hal_id={inria-00638813},
url={http://hal.inria.fr/inria-00638813/en/},
title={GPU-based Multi-start Local Search Algorithms},
author={Luong, Th{‘e} Van and Melab, Nouredine and Talbi, El-Ghazali},
language={Anglais},
affiliation={DOLPHIN – INRIA Lille – Nord Europe – INRIA – CNRS : UMR8022 – Universit{‘e} des Sciences et Technologies de Lille – Lille I},
booktitle={Learning and Intelligent Optimization},
publisher={Springer},
address={Rome, Italie},
volume={6683},
editor={Carlos A. Coello Coello},
series={Lecture Notes in Computer Science},
audience={internationale},
year={2011},
pdf={http://hal.inria.fr/inria-00638813/PDF/LION5.pdf}
}
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.
November 22, 2011 by hgpu
