CUDA-based parallel local search for the set-union knapsack problem

The Set-Union Knapsack Problem (SUKP) is a complex combinatorial optimisation problem with applications in resource allocation, portfolio selection, and logistics. This paper presents a parallel local search algorithm for solving SUKP on the Compute Unified Device Architecture (CUDA) platform in Graphics Processing Units (GPUs). The proposed method employs a compact algorithm that divides the search space into smaller regions. For diversity, each thread in a GPU block starts the search process from a different location in a region using a different initial solution. Each thread then searches the local optimum by utilising communication between individuals through a crossover operator exploiting the best solution within the GPU block. Through extensive experiments on a set of SUKP benchmark instances ranging in size from small to large, we demonstrate the effectiveness of the proposed algorithm in finding high-quality solutions within comparable time frames. Furthermore, a comparative performance analysis with the current state-of-the-art SUKP algorithms reveals the competitive advantage of the proposed method. The GPU-based parallel local search algorithm using uniform crossover is a valuable addition to the repertoire of algorithms addressing SUKP, highlighting its potential for practical applications in real-world decision-making scenarios.