CUDA-accelerated cooperative scatter search for solving the knapsack problem with forfeits
Journal of King Saud University Computer and Information Sciences · 2026-08 · 38 (6)
DOI: 10.1007/s44443-026-00717-3 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of King Saud University Computer and Information Sciences, online erschienen am 28.05.2026. Verfasst von Ke Zhou und 3 weiteren Autor:innen. Die Arbeit nennt 37 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
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.
Zitieren
APA
Zhou, K., Luo, X., Zhao, J., & Song, Y. (2026). CUDA-accelerated cooperative scatter search for solving the knapsack problem with forfeits. Journal of King Saud University Computer and Information Sciences, 38(6). https://doi.org/10.1007/s44443-026-00717-3
Vancouver
Zhou K, Luo X, Zhao J, Song Y. CUDA-accelerated cooperative scatter search for solving the knapsack problem with forfeits. Journal of King Saud University Computer and Information Sciences. 2026;38(6). doi:10.1007/s44443-026-00717-3
BibTeX
@article{Zhou2026,
author = {Zhou, Ke and Luo, Xiaochuan and Zhao, Juntao and Song, Yuqiao},
title = {CUDA-accelerated cooperative scatter search for solving the knapsack problem with forfeits},
journal = {Journal of King Saud University Computer and Information Sciences},
year = {2026},
volume = {38},
number = {6},
doi = {10.1007/s44443-026-00717-3}
}
EUVIMED