NEIGHBORHOOD STRUCTURES FOR GPU-BASED LOCAL SEARCH ALGORITHMS

摘要

Local search algorithms are powerful heuristics for solving computationally hard prob-nlems in science and industry. In these methods, designing neighborhood operators tonexplore large promising regions of the search space may improve the quality of the ob-ntained solutions at the expense of a high-cost computation process. As a consequence,nthe use of GPU computing provides an efficient way to speed up the search. However,ndesigning applications on a GPU is still complex and many issues have to be faced. Wenprovide a methodology to design and implement different neighborhood structures fornLS algorithms on a GPU. The work has been evaluated for binary problems and thenobtained results are convincing both in terms of efficiency, quality and robustness of thenprovided solutions at run time.