On improving convex quadratic programming relaxation for the quadratic assignment problem

被引：2

作者：

Xia, Yong ^{[1
]}

Gharibi, Wajeb ^{[2
]}

机构：

[1] Beihang Univ, Sch Math & Syst Sci, State Key Lab Software Dev Environm, LMIB,Minist Educ, Beijing 100191, Peoples R China

[2] Jazan Univ, Coll Comp Sci & Informat Syst, Jazan 828226694, Saudi Arabia

来源：

JOURNAL OF COMBINATORIAL OPTIMIZATION | 2015年 / 30卷 / 03期

基金：

中国国家自然科学基金;

关键词：

Quadratic assignment problem; Lower bound; Capacitated transportation problem; Quadratic programming;

D O I：

10.1007/s10878-013-9655-3

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

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.

引用

页码：647 / 667

页数：21

共 18 条

[1] Lagrangian relaxation of quadratic matrix constraints [J].

Anstreicher, K ;

Wolkowicz, H .

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS, 2000, 22 (01) :41-55

[2] Recent advances in the solution of quadratic assignment problems [J].

Anstreicher, KM .

MATHEMATICAL PROGRAMMING, 2003, 97 (1-2) :27-42

[3] A new bound for the quadratic assignment problem based on convex quadratic programming [J].

Anstreicher, KM ;

Brixius, NW .

MATHEMATICAL PROGRAMMING, 2001, 89 (03) :341-357

[4] Solving quadratic assignment problems using convex quadratic programming relaxations [J].

Brixius, NW ;

Anstreicher, KM .

OPTIMIZATION METHODS & SOFTWARE, 2001, 16 (1-4) :49-68

[5]

Burkard R E., 1998, Handbook of combinatorial optimization, P1713

[6] QAPLIB - A quadratic assignment problem library [J].

Burkard, RE ;

Karisch, SE ;

Rendl, F .

JOURNAL OF GLOBAL OPTIMIZATION, 1997, 10 (04) :391-403

[7]

CELA E, 1998, QUADRATIC ASSIGNMENT

[8]

Finke G, 1987, Ann. Discrete Math., V132, P61, DOI [DOI 10.1016/S0304-0208(08)73232-8, 10.1016/S0304-0208(08)73232-8]

[9]

Grant Michael, 2014, CVX: MATLAB software for disciplined convex programming, version 2.1

[10] A NEW LOWER BOUND VIA PROJECTION FOR THE QUADRATIC ASSIGNMENT PROBLEM [J].

HADLEY, SW ;

RENDL, F ;

WOLKOWICZ, H .

MATHEMATICS OF OPERATIONS RESEARCH, 1992, 17 (03) :727-739

← 1 2 →