Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry
Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry
复制标题
DOI：
10.1007/s10107-010-0411-5
复制
发表时间：
2012-06-01
影响因子：
2.7
通讯作者：
Sotirov, Renata
中科院分区：
文献类型：
--
作者：
de Klerk, Etienne;Sotirov, Renata
Zhao et al. （J .数学学报，1998）引入了二次分配问题的半定规划（SDP）界。根据经验，这些边界在实践中通常是相当好的，但是计算要求很高，即使对于相对较小的实例也是如此。对于数据矩阵具有大自同态群的QAP实例，可以更有效地计算这些边界，如Klerk和Sotirov（数学程序A， 122(2), 225-246, 2010）所示。在同样的情况下，我们将展示如何在其中一个数据矩阵具有传递自同构群的QAP实例中获得更强的界。为了说明我们的方法，我们计算了来自QAP库QAPLIB的几个实例的改进下界。
Semidefinite programming (SDP) bounds for the quadratic assignment problem (QAP) were introduced in Zhao et al. (J Comb Optim 2:71-109, 1998). Empirically, these bounds are often quite good in practice, but computationally demanding, even for relatively small instances. For QAP instances where the data matrices have large automorphism groups, these bounds can be computed more efficiently, as was shown in Klerk and Sotirov (Math Program A, 122(2), 225-246, 2010). Continuing in the same vein, we show how one may obtain stronger bounds for QAP instances where one of the data matrices has a transitive automorphism group. To illustrate our approach, we compute improved lower bounds for several instances from the QAP library QAPLIB.