Přístupnostní navigace
E-přihláška
Vyhledávání Vyhledat Zavřít
Detail publikace
MATOUŠEK, R. DOBROVSKÝ, L. KŮDELA, J.
Originální název
How to start a heuristic? Utilizing lower bounds for solving the quadratic assignment problem
Typ
článek v časopise ve Web of Science, Jimp
Jazyk
angličtina
Originální abstrakt
The Quadratic Assignment Problem (QAP) is one of the classical combinatorial optimization problems and is known for its diverse applications. The QAP is an NP-hard optimization problem which attracts the use of heuristic or metaheuristic algorithms that can find quality solutions in an acceptable computation time. On the other hand, there is quite a broad spectrum of mathematical programming techniques that were developed for finding the lower bounds for the QAP. This paper presents a fusion of the two approaches whereby the solutions from the computations of the lower bounds are used as the starting points for a metaheuristic, called HC12, which is implemented on a GPU CUDA platform. We perform extensive computational experiments that demonstrate that the use of these lower bounding techniques for the construction of the starting points has a significant impact on the quality of the resulting solutions.
Klíčová slova
Heuristics; Lower bounds; Metaheuristics; Quadratic assignment problem; Starting values
Autoři
MATOUŠEK, R.; DOBROVSKÝ, L.; KŮDELA, J.
Vydáno
31. 12. 2021
Nakladatel
Growing Science
ISSN
1923-2934
Periodikum
International Journal of Industrial Engineering Computations
Ročník
13
Číslo
2
Stát
Kanada
Strany od
151
Strany do
164
Strany počet
14
URL
http://www.growingscience.com/ijiec/Vol13/IJIEC_2021_33.pdf
Plný text v Digitální knihovně
http://hdl.handle.net/11012/203280
BibTex
@article{BUT175648, author="Radomil {Matoušek} and Ladislav {Dobrovský} and Jakub {Kůdela}", title="How to start a heuristic? Utilizing lower bounds for solving the quadratic assignment problem", journal="International Journal of Industrial Engineering Computations", year="2021", volume="13", number="2", pages="151--164", doi="10.5267/j.ijiec.2021.12.003", issn="1923-2934", url="http://www.growingscience.com/ijiec/Vol13/IJIEC_2021_33.pdf" }