A cooperative GPU-based Parallel Multistart Simulated Annealing algorithm for Quadratic Assignment Problem

dc.authoridSonuc, Emrullah/0000-0001-7425-6963
dc.authoridBAYIR, Safak/0000-0003-4719-8088
dc.authoridSEN, BAHA/0000-0003-3577-2548
dc.contributor.authorSonuc, Emrullah
dc.contributor.authorSen, Baha
dc.contributor.authorBayir, Safak
dc.date.accessioned2024-09-29T15:57:32Z
dc.date.available2024-09-29T15:57:32Z
dc.date.issued2018
dc.departmentKarabük Üniversitesien_US
dc.description.abstractGPU hardware and CUDA architecture provide a powerful platform to develop parallel algorithms. Implementation of heuristic and metaheuristic algorithms on GPUs are limited in literature. Nowadays developing parallel algorithms on GPU becomes very important. In this paper, NP-Hard Quadratic Assignment Problem (QAP) that is one of the combinatorial optimization problems is discussed. Parallel Multistart Simulated Annealing (PMSA) method is developed with CUDA architecture to solve QAP. An efficient method is developed by providing multistart technique and cooperation between threads. The cooperation is occurred with threads in both the same and different blocks. This paper focuses on both acceleration and quality of solutions. Computational experiments conducted on many Quadratic Assignment Problem Library (QAPLIB) instances. The experimental results show that PMSA runs up to 29x faster than a single-core CPU and acquires best known solution in a short time in many benchmark datasets. (C) 2018 Karabuk University. Publishing services by Elsevier B.V.en_US
dc.description.sponsorshipScientific Research Coordination Unit of Karabuk University [KBU-BAP-15/2-DR-027]en_US
dc.description.sponsorshipAuthors are grateful for valuable comments and suggestions of the referees. This work was supported by the Scientific Research Coordination Unit of Karabuk University under Grant no. KBU-BAP-15/2-DR-027.en_US
dc.identifier.doi10.1016/j.jestch.2018.08.002
dc.identifier.endpage849en_US
dc.identifier.issn2215-0986
dc.identifier.issue5en_US
dc.identifier.scopus2-s2.0-85051532969en_US
dc.identifier.scopusqualityQ1en_US
dc.identifier.startpage843en_US
dc.identifier.urihttps://doi.org/10.1016/j.jestch.2018.08.002
dc.identifier.urihttps://hdl.handle.net/20.500.14619/4874
dc.identifier.volume21en_US
dc.identifier.wosWOS:000445967100005en_US
dc.identifier.wosqualityN/Aen_US
dc.indekslendigikaynakWeb of Scienceen_US
dc.indekslendigikaynakScopusen_US
dc.language.isoenen_US
dc.publisherElsevier - Division Reed Elsevier India Pvt Ltden_US
dc.relation.ispartofEngineering Science and Technology-An International Journal-Jestechen_US
dc.relation.publicationcategoryMakale - Uluslararası Hakemli Dergi - Kurum Öğretim Elemanıen_US
dc.rightsinfo:eu-repo/semantics/openAccessen_US
dc.subjectCombinatorial optimizationen_US
dc.subjectCUDAen_US
dc.subjectGPUen_US
dc.subjectMultistart Simulated Annealingen_US
dc.subjectParallel algorithmsen_US
dc.subjectQuadratic Assignment Problemen_US
dc.titleA cooperative GPU-based Parallel Multistart Simulated Annealing algorithm for Quadratic Assignment Problemen_US
dc.typeArticleen_US

Dosyalar