The Rank-One Quadratic Assignment Problem

Yang Wang (), Wei Yang (), Abraham P. Punnen (), Jingbo Tian (), Aihua Yin () and Zhipeng Lü ()
Additional contact information
Yang Wang: School of Management, Northwestern Polytechnical University, 710072 Xi’an, China
Wei Yang: School of Management, Northwestern Polytechnical University, 710072 Xi’an, China
Abraham P. Punnen: Department of Mathematics, Simon Fraser University Surrey, Surrey, British Columbia V3T 0A3, Canada
Jingbo Tian: Department of Civil Engineering and Applied Mechanics, McGill University, Montreal, Quebec H3A 0G4, Canada
Aihua Yin: School of Software and Communication Engineering, Jiangxi University of Finance and Economics, 330032 Nanchang, China
Zhipeng Lü: School of Computer Science and Technology, Huazhong University of Science and Technology, 430074 Wuhan, China

INFORMS Journal on Computing, 2021, vol. 33, issue 3, 979-996

Abstract: In this paper, we study the quadratic assignment problem with a rank-one cost matrix (QAP-R1). Four integer-programming formulations are introduced of which three are assumed to have partial integer data. Unlike the standard quadratic assignment problem, some of our formulations can solve reasonably large instances of QAP-R1 with impressive running times and are faster than some metaheuristics. Pairwise relative strength of the LP relaxations of these formulations are also analyzed from theoretical and experimental points of view. Finally, we present a new metaheuristic algorithm to solve QAP-R1 along with its computational analysis. Our study offers the first systematic experimental analysis of integer-programming models and heuristics for QAP-R1. The benchmark instances with various characteristics generated for our study are made available to the public for future research work. Some new polynomially solvable special cases are also introduced. Summary of Contribution: This paper aims to advance our knowledge and ability in solving an important special case of the quadratic assignment problem. It shows how to exploit inherent properties of an optimization problem to achieve computational advantages, a strategy that was followed by researchers in model building and algorithm developments for decades. Our computational results attest to this time-tested general philosophy. The paper presents the first systematic computational study of the rank one quadratic assignment problem, along with new mathematical programming models and complexity analysis. We believe the theoretical and computational results of this paper will inspire further research on the topic and will be of significant value to practitioners using rank one quadratic assignment models.

Keywords: quadratic assignment; integer-programming formulations; complexity; polynomially solvable cases; metaheuristics (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2020.1003 (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:33:y:2021:i:3:p:979-996

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 ().