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

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26210%2F21%3APU142805" target="_blank" >RIV/00216305:26210/21:PU142805 - isvavai.cz</a>

Výsledek na webu

<a href="http://www.growingscience.com/ijiec/Vol13/IJIEC_2021_33.pdf" target="_blank" >http://www.growingscience.com/ijiec/Vol13/IJIEC_2021_33.pdf</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.5267/j.ijiec.2021.12.003" target="_blank" >10.5267/j.ijiec.2021.12.003</a>

Jazyk výsledku

angličtina

Název v původním jazyce

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

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

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

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2021

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

International Journal of Industrial Engineering Computations

ISSN

1923-2926

e-ISSN

1923-2934

Svazek periodika

13

Číslo periodika v rámci svazku

2

Stát vydavatele periodika

CA - Kanada

Počet stran výsledku

14

Strana od-do

151-164

Kód UT WoS článku

000739637000001

EID výsledku v databázi Scopus

2-s2.0-85123600067