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

Sonuç, Emrullah; Özcan, Ender

Abstract

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.

Citation

Sonuç, E., & Özcan, E. (2024). CUDA-based parallel local search for the set-union knapsack problem. Knowledge-Based Systems, 299, Article 112095. https://doi.org/10.1016/j.knosys.2024.112095

• Journal Article Type: Article
• Acceptance Date: Jun 6, 2024
• Online Publication Date: Jun 8, 2024
• Publication Date: Sep 5, 2024
• Deposit Date: Jun 15, 2024
• Publicly Available Date: Jun 19, 2024
• Journal: Knowledge-Based Systems
• Print ISSN: 0950-7051
• Electronic ISSN: 1872-7409
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 299
• Article Number: 112095
• DOI: https://doi.org/10.1016/j.knosys.2024.112095
• Keywords: Combinatorial optimisation, Heuristic, Parallel local search, Set-union knapsack problem
• Public URL: https://nottingham-repository.worktribe.com/output/36016629
• Publisher URL: https://www.sciencedirect.com/science/article/pii/S0950705124007299?via%3Dihub
• Additional Information: This article is maintained by: Elsevier; Article Title: CUDA-based parallel local search for the set-union knapsack problem; Journal Title: Knowledge-Based Systems; CrossRef DOI link to publisher maintained version: https://doi.org/10.1016/j.knosys.2024.112095; Content Type: article; Copyright: © 2024 The Author(s). Published by Elsevier B.V.