EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

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

Ke Zhou, Xiaochuan Luo, Juntao Zhao, Yuqiao Song

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).

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →