Semi-definite programming relaxation of quadratic assignment problems based on nonredundant matrix splitting
Semi-definite programming relaxation of quadratic assignment problems based on nonredundant matrix splitting
复制标题
DOI：
10.1007/s10589-014-9663-y
复制
发表时间：
2014-06
影响因子：
2.2
通讯作者：
Jiming Peng;Tao Zhu;Hezhi Luo;K. Toh
中科院分区：
文献类型：
--
作者：
Jiming Peng;Tao Zhu;Hezhi Luo;K. Toh
二次分配问题是离散优化问题中最具挑战性的一类。最近，已经提出了基于矩阵分裂的QAP的一类新的半定松弛模型（Mittelmann和Peng，SIAM J Optim 20：3408-3426，2010; Peng等人， Math Program Comput 2：59-77，2010）。在本文中，我们考虑的问题，如何选择一个适当的矩阵分裂计划，使所得到的松弛模型是容易解决的，并能够提供一个强的界限。为此，我们首先引入了一个新的概念，所谓的冗余和非冗余矩阵分裂，并表明，松弛基于非冗余矩阵分裂可以提供一个更强的约束比冗余的。然后，我们提出了遵循最小迹原则，通过解决一个辅助半定规划问题，找到一个非冗余矩阵分裂。我们表明，应用最小迹原理直接导致所谓的正交矩阵分裂（Peng et al.， Math Program Comput 2：59-77，2010）。为了找到其他非冗余矩阵分裂方案，其产生的松弛模型是相对容易解决的，我们阐述了两个分裂计划的基础上所谓的一个矩阵和和矩阵。我们分析了这两种情况下的辅助问题的解决方案，并描述了它们何时可以提供非冗余矩阵分裂。从理论上比较了这两种分裂方案的下界。最后给出了一些大型QAP问题的数值结果，进一步验证了我们的理论结论。
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.