- Estimating Bounds for Quadratic Assignment Problems Associated with Hamming and Manhattan Distance Matrices based on Semidefinite Programming Hans Mittelmann (mittelmannasu.edu) Jiming Peng (pengjuiuc.edu) Abstract: Quadratic assignment problems (QAPs) with a Hamming distance matrix of a hypercube or a Manhattan distance matrix of rectangular grids arise frequently from communications and facility locations and are known to be among the hardest discrete optimization problems. In this paper we consider the issue of how to obtain lower bounds for those two classes of QAPs based on semidefinite programming (SDP). By exploiting the data structure of the involved distance matrix $B$, we first show that for any permutation matrix $X$, the matrix $Y=\alpha E-XBX^T$ is positive semi-definite, where $\alpha$ is a properly chosen parameter depending only on the associated graph in the underlying QAP and $E=ee^T$ is a rank one matrix whose elements have value 1. This results in a natural way to approximate the original QAPs via SDP relaxation based on the matrix splitting technique. Our new SDP relaxations have a smaller size compared with other SDP relaxations in the literature and can be solved efficiently by most open source SDP solvers. Experimental results show that for the underlying QAPs of size up to n=200, strong bounds can be obtained effectively. Keywords: Quadratic Assignment Problem (QAP),Semidefinite Programming (SDP), Singular Value Decomposition (SVD), Lower bound Category 1: Applications -- OR and Management Sciences Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming ) Citation: SIAM J. Optim. 20, 3408-3426 (2010) Download: [PDF]Entry Submitted: 05/14/2008Entry Accepted: 05/15/2008Entry Last Modified: 08/30/2013Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society.