Eigenvalue Bounds Versus Semidefinite Relaxations for the Quadratic Assignment Problem
Eigenvalue Bounds Versus Semidefinite Relaxations for the Quadratic Assignment Problem
复制标题
二次分配问题的特征值界与半定松弛
DOI：
--
复制
发表时间：
2000
影响因子：
3.1
通讯作者：
K. Anstreicher
中科院分区：
文献类型：
--
作者：
K. Anstreicher
最近证明了二次分配问题（QAP）的一个著名的特征值界实际上对应于一个半定规划（SDP）松弛。然而，这个界限是计算上有用的，分配约束的QAP必须首先被消除，然后应用到一个低维问题的界限。由此产生的“投影特征值界”是QAP的最佳可用界之一，特别是当考虑到相对于获得它们的复杂性的界的质量时。在本文中，我们表明，投影本征值界也与SDP松弛的原始QAP。这种“隐式”SDP松弛类似于Lin和Saigal [On Solving Large-scale Semifinite Programming Problems-A Case Study of Quadratic Assignment Problem，Department of Industrial Engineering and Operations Research，University of Michigan，1997]和Zhao等人[J. Combin. Optim.，2（1998），pp. 71-109]。
It was recently demonstrated that a well-known eigenvalue bound for the quadratic assignment problem (QAP) actually corresponds to a semidefinite programming (SDP) relaxation. However, for this bound to be computationally useful, the assignment constraints of the QAP must first be eliminated and the bound then applied to a lower-dimensional problem. The resulting "projected eigenvalue bound" is one of the best available bounds for the QAP, especially when considering the quality of bounds relative to the complexity of obtaining them. In this paper we show that the projected eigenvalue bound is also related to an SDP relaxation of the original QAP. This "implicit" SDP relaxation is similar to SDP relaxations of the QAP proposed by Lin and Saigal [On Solving Large-scale Semidefinite Programming Problems---A Case Study of Quadratic Assignment Problem, Department of Industrial Engineering and Operations Research, University of Michigan, 1997] and Zhao et al. [J. Combin. Optim., 2 (1998), pp. 71-109].