Scholarlink

<p>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.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

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

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年5月28日

查看全文
  • Ke Zhou,
  • Xiaochuan Luo,
  • Juntao Zhao,
  • Yuqiao Song

摘要

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.