Please use this identifier to cite or link to this item:
Title: Semi-definite programming relaxation of quadratic assignment problems based on nonredundant matrix splitting
Authors: Peng, J.
Zhu, T.
Luo, H.
Toh, K.-C. 
Keywords: Lower bound
Matrix splitting
Quadratic assignment problem (QAP)
Semi-definite programming (SDP)
Semi-definite relaxation (SDR)
Issue Date: 2014
Citation: Peng, J., Zhu, T., Luo, H., Toh, K.-C. (2014). Semi-definite programming relaxation of quadratic assignment problems based on nonredundant matrix splitting. Computational Optimization and Applications 60 (1) : 171-198. ScholarBank@NUS Repository.
Abstract: Quadratic assignment problems (QAPs) are known to be among the most challenging discrete optimization problems. Recently, a new class of semi-definite relaxation models for QAPs based on matrix splitting has been proposed (Mittelmann and Peng, SIAM J Optim 20:3408-3426, 2010 ; Peng et al., Math Program Comput 2:59-77, 2010). In this paper, we consider the issue of how to choose an appropriate matrix splitting scheme so that the resulting relaxation model is easy to solve and able to provide a strong bound. For this, we first introduce a new notion of the so-called redundant and non-redundant matrix splitting and show that the relaxation based on a non-redundant matrix splitting can provide a stronger bound than a redundant one. Then we propose to follow the minimal trace principle to find a non-redundant matrix splitting via solving an auxiliary semi-definite programming problem. We show that applying the minimal trace principle directly leads to the so-called orthogonal matrix splitting introduced in (Peng et al., Math Program Comput 2:59-77, 2010). To find other non-redundant matrix splitting schemes whose resulting relaxation models are relatively easy to solve, we elaborate on two splitting schemes based on the so-called one-matrix and the sum-matrix. We analyze the solutions from the auxiliary problems for these two cases and characterize when they can provide a non-redundant matrix splitting. The lower bounds from these two splitting schemes are compared theoretically. Promising numerical results on some large QAP instances are reported, which further validate our theoretical conclusions. © 2014 Springer Science+Business Media New York.
Source Title: Computational Optimization and Applications
ISSN: 09266003
DOI: 10.1007/s10589-014-9663-y
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Dec 10, 2018


checked on Dec 10, 2018

Page view(s)

checked on Nov 16, 2018

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.