New Variants of SDLS Algorithm for LABS Problem Dedicated to GPGPU Architectures.

Low autocorrelation binary sequence (LABS) remains an open hard optimisation problem that has many applications. One of the promising directions for solving the problem is designing advanced solvers based on local search heuristics. The paper proposes two new heuristics developed from the steepest-descent local search algorithm (SDLS), implemented on the GPGPU architectures. The introduced algorithms utilise the parallel nature of the GPU and provide an effective method of solving the LABS problem. As a means for comparison, the efficiency between SDSL and the new algorithms is presented, showing that exploring the wider neighbourhood improves the results.