TY - JOUR
T1 - On improving convex quadratic programming relaxation for the quadratic assignment problem
AU - Xia, Yong
AU - Gharibi, Wajeb
N1 - Publisher Copyright:
© 2013, Springer Science+Business Media New York.
PY - 2015/10/1
Y1 - 2015/10/1
N2 - Relaxation techniques play a great role in solving the quadratic assignment problem, among which the convex quadratic programming bound (QPB) is competitive with existing bounds in the trade-off between cost and quality. In this article, we propose two new lower bounds based on QPB. The first dominates QPB at a high computational cost, which is shown equivalent to the recent second-order cone programming bound. The second is strictly tighter than QPB in most cases, while it is solved as easily as QPB.
AB - Relaxation techniques play a great role in solving the quadratic assignment problem, among which the convex quadratic programming bound (QPB) is competitive with existing bounds in the trade-off between cost and quality. In this article, we propose two new lower bounds based on QPB. The first dominates QPB at a high computational cost, which is shown equivalent to the recent second-order cone programming bound. The second is strictly tighter than QPB in most cases, while it is solved as easily as QPB.
KW - Capacitated transportation problem
KW - Lower bound
KW - Quadratic assignment problem
KW - Quadratic programming
UR - https://www.scopus.com/pages/publications/84940723438
U2 - 10.1007/s10878-013-9655-3
DO - 10.1007/s10878-013-9655-3
M3 - 文章
AN - SCOPUS:84940723438
SN - 1382-6905
VL - 30
SP - 647
EP - 667
JO - Journal of Combinatorial Optimization
JF - Journal of Combinatorial Optimization
IS - 3
ER -