A Graphics Processing Unit Algorithm to Solve the Quadratic Assignment Problem Using Level-2 Reformulation-Linearization Technique

Alexandre Domingues Gonçalves (), Artur Alves Pessoa (), Cristiana Bentes (), Ricardo Farias () and Lúcia Maria de A. Drummond ()
Additional contact information
Alexandre Domingues Gonçalves: Instituto Federal do Rio de Janeiro, Rio de Janeiro, 21941-901, Brazil
Artur Alves Pessoa: Engenharia de Produção - Universidade Federal Fluminense, Niteroi, 24220-900, Brazil
Cristiana Bentes: Engenharia de Sistemas e Computação - Universidade do Estado do Rio de Janeiro, Rio de Janeiro, 20550-900, Brazil
Ricardo Farias: COPPE Sistemas - Universidade Federal do Rio de Janeiro, Rio de Janeiro, 21941-914, Brazil
Lúcia Maria de A. Drummond: Instituto de Computação - Universidade Federal Fluminense, Niteroi, 24220-900, Brazil

INFORMS Journal on Computing, 2017, vol. 29, issue 4, 676-687

Abstract: The quadratic assignment problem (QAP) is a combinatorial optimization problem that arises in many real-world applications, such as equipment allocation in industry. The QAP is NP-hard and, in practice, one of the hardest combinatorial optimization problems to solve to optimality. Exact solutions of QAP are typically obtained by the branch-and-bound method. This method, however, potentially requires a high computational effort, and the use of good lower bounds is essential to prune the search tree. Branch-and-bound algorithms that use the dual-ascent procedure based on the level-2 reformulation linearization technique (RLT2) belong to the state of the art on exactly solving QAP. In this work, we propose a parallel implementation of that branch-and-bound algorithm. Our approach uses the Auction Algorithm of Bertsekas and Castañon to solve the linear assignment problems of RLT2, which allows us to take advantage of the massive parallel environment of graphics processing units to speed up the lower bound computation and implement some memory optimization techniques to address large-size problems. We report experimental results that show significant execution time reductions compared to previous works and allow us to provide, for the first time, exact solutions for two instances of QAP: tai35b and tai40b.

Keywords: quadratic assignment problem; GPU computing; reformulation linearization technique (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2017.0754 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:29:y:2017:i:4:p:676-687

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().