Parallel Combinatorial Optimization Heuristics with GPUs
Mohammad Harun Rashid, Lixin Tao · 2017
Local search metaheuristics can be used for solving hard optimization problems in science, engineering, economics and technology. By using Local search metaheuristics, we could obtain satisfactory resolution (approximate optimum) in a reasonable time. However, it is still very CPU time-consuming when solving large problem instances. As graphic process units (GPUs) have been evolved to support general purpose computing, they are taken as a major accelerator in scientific and industrial computing. In this paper, we present an optimized parallel iterated local search hill climbing algorithm efficiently accelerated on GPUs and test the algorithm with a typical case study of the Graph bisection in computational science.