How to start a heuristic? Utilizing lower bounds for solving the quadratic assignment problem
| Autor: | Radomil Matousek, Ladislav Dobrovsky, Jakub Kudela |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2022 |
| Předmět: | |
| Zdroj: | International Journal of Industrial Engineering Computations, Vol 13, Iss 2, Pp 151-164 (2022) |
| Druh dokumentu: | article |
| ISSN: | 1923-2926 1923-2934 |
| DOI: | 10.5267/j.ijiec.2021.12.003 |
| Popis: | 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. |
| Databáze: | Directory of Open Access Journals |
| Externí odkaz: |
|