Detail publikačního výsledku

How to start a heuristic? Utilizing lower bounds for solving the quadratic assignment problem

MATOUŠEK, R.; DOBROVSKÝ, L.; KŮDELA, J.

Original Title

How to start a heuristic? Utilizing lower bounds for solving the quadratic assignment problem

English Title

How to start a heuristic? Utilizing lower bounds for solving the quadratic assignment problem

Type

WoS Article

Original Abstract

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.

English abstract

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.

Keywords

Heuristics; Lower bounds; Metaheuristics; Quadratic assignment problem; Starting values

Key words in English

Heuristics; Lower bounds; Metaheuristics; Quadratic assignment problem; Starting values

Authors

MATOUŠEK, R.; DOBROVSKÝ, L.; KŮDELA, J.

RIV year

2022

Released

31.12.2021

Publisher

Growing Science

ISBN

1923-2934

Periodical

International Journal of Industrial Engineering Computations

Volume

13

Number

2

State

Canada

Pages from

151

Pages to

164

Pages count

14

URL

http://www.growingscience.com/ijiec/Vol13/IJIEC_2021_33.pdf

Full text in the Digital Library

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-2926",
  url="http://www.growingscience.com/ijiec/Vol13/IJIEC_2021_33.pdf"
}

Documents

IJIEC_2021_33