CUDA-accelerated cooperative scatter search for solving the knapsack problem with forfeits

The Knapsack Problem with Forfeits (KPF) involves penalized conflicts between selected items, yielding a non-separable objective function and making large-scale instances computationally challenging for traditional CPU-based metaheuristics. This paper proposes CuCSS, a CUDA-accelerated cooperative scatter search framework that integrates GPU parallelism into both solution evaluation and local improvement phases. By combining a scatter search architecture with a GPU-accelerated multi-neighborhood tabu search, CuCSS efficiently accelerates profit aggregation, forfeit penalty computation, and incremental move evaluation through dedicated CUDA kernels. Extensive experiments on standard benchmark instances demonstrate that CuCSS achieves highly competitive performance, frequently matching or improving best-known solutions while maintaining strong robustness across independent runs. These results confirm the effectiveness of GPU-accelerated scatter search in addressing large-scale knapsack problems with forfeits.