Semi-definite programming relaxation of quadratic assignment problems based on nonredundant matrix splitting

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.