Please use this identifier to cite or link to this item: https://doi.org/10.1007/s10589-014-9663-y
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. https://doi.org/10.1007/s10589-014-9663-y
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
URI: http://scholarbank.nus.edu.sg/handle/10635/126644
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.

SCOPUSTM   
Citations

4
checked on Jun 16, 2018

WEB OF SCIENCETM
Citations

4
checked on May 30, 2018

Page view(s)

9
checked on Mar 12, 2018

Google ScholarTM

Check

Altmetric


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