4263

Large neighborhood local search optimization on graphics processing units

The Van Luong, Nouredine Melab, El-Ghazali Talbi
CNRS LIFL, INRIA Lille Nord Eur., Villeneuve-d’Ascq, France
IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum (IPDPSW), 2010

@inproceedings{van2010large,

   title={Large neighborhood local search optimization on graphics processing units},

   author={Van Luong, T. and Melab, N. and Talbi, E.G.},

   booktitle={Parallel & Distributed Processing, Workshops and Phd Forum (IPDPSW), 2010 IEEE International Symposium on},

   pages={1–8},

   year={2010},

   organization={IEEE}

}

Download Download (PDF)   View View   Source Source   

604

views

Local search (LS) algorithms are among the most powerful techniques for solving computationally hard problems in combinatorial optimization. These algorithms could be viewed as "walks through neighborhoods" where the walks are performed by iterative procedures that allow to move from a solution to another one in the solution space. In these heuristics, designing operators to explore large promising regions of the search space may improve the quality of the obtained solutions at the expense of a highly computationally process. Therefore, the use of graphics processing units (GPUs) provides an efficient complementary 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 large neighborhood LS algorithms on GPU. The work has been experimented for binary problems by deploying multiple neighborhood structures. The obtained results are convincing both in terms of efficiency, quality and robustness of the provided solutions at run time.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: