Skip to main content

Research Repository

Advanced Search

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

Sonuç, Emrullah; Özcan, Ender

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


Authors

Emrullah Sonuç

Profile Image

ENDER OZCAN ender.ozcan@nottingham.ac.uk
Professor of Computer Science and Operational Research



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.

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.

Files





You might also like



Downloadable Citations