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

Basit Öğe Kaydı
dc.authoridOzcan, Ender/0000-0003-0276-1391
dc.authoridSonuc, Emrullah/0000-0001-7425-6963
dc.contributor.authorSonuc, Emrullah
dc.contributor.authorOzcan, Ender
dc.date.accessioned2024-09-29T15:57:51Z
dc.date.available2024-09-29T15:57:51Z
dc.date.issued2024
dc.departmentKarabük Üniversitesien_US
dc.description.abstractThe 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.en_US
dc.description.sponsorshipBIDEB-2219 International Postdoctoral Research Fellowship Programme [1059B192001306]en_US
dc.description.sponsorshipThis work was supported by BIDEB-2219 International Postdoctoral Research Fellowship Programme (Grant No. 1059B192001306) , thanks to Scientific and Technological Research Council of Turkiye (TUBITAK) .en_US
dc.identifier.doi10.1016/j.knosys.2024.112095
dc.identifier.issn0950-7051
dc.identifier.issn1872-7409
dc.identifier.scopus2-s2.0-85195775251en_US
dc.identifier.scopusqualityQ1en_US
dc.identifier.urihttps://doi.org/10.1016/j.knosys.2024.112095
dc.identifier.urihttps://hdl.handle.net/20.500.14619/5023
dc.identifier.volume299en_US
dc.identifier.wosWOS:001257622700001en_US
dc.identifier.wosqualityN/Aen_US
dc.indekslendigikaynakWeb of Scienceen_US
dc.indekslendigikaynakScopusen_US
dc.language.isoenen_US
dc.publisherElsevieren_US
dc.relation.ispartofKnowledge-Based Systemsen_US
dc.relation.publicationcategoryMakale - Uluslararası Hakemli Dergi - Kurum Öğretim Elemanıen_US
dc.rightsinfo:eu-repo/semantics/openAccessen_US
dc.subjectCombinatorial optimisationen_US
dc.subjectHeuristicen_US
dc.subjectParallel local searchen_US
dc.subjectSet-union knapsack problemen_US
dc.titleCUDA-based parallel local search for the set-union knapsack problemen_US
dc.typeArticleen_US

Dosyalar

Koleksiyon

WoS İndeksli Yayınlar Koleksiyonu
Scopus İndeksli Yayınlar Koleksiyonu