Name
Abstract | ||
|---|---|---|
The quadratic assignment problem (QAP) is arguably one of the hardest NP-hard discrete optimization problems. Problems of dimension greater than 25 are still considered to be large scale. Current successful solution techniques use branch-and-bound methods, which rely on obtaining strong and inexpensive bounds. In this paper, we introduce a new semidefinite programming (SDP) relaxation for generating bounds for the QAP in the trace formulation. We apply majorization to obtain a relaxation of the orthogonal similarity set of the quadratic part of the objective function. This exploits the matrix structure of QAP and results in a relaxation with much smaller dimension than other current SDP relaxations. We compare the resulting bounds with several other computationally inexpensive bounds such as the convex quadratic programming relaxation (QPB). We find that our method provides stronger bounds on average and is adaptable for branch-and-bound methods. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1287/moor.1090.0419 | Math. Oper. Res. |
Keywords | DocType | Volume |
current SDP relaxation,convex quadratic programming relaxation,smaller dimension,Low-Dimensional Semidefinite Relaxation,semidefinite programming relaxations,interior- point methods,Quadratic Assignment Problem,large scale problems.,inexpensive bound,current successful solution technique,quadratic assignment problem,branch-and-bound method,new semidefinite programming,computationally inexpensive bound,quadratic part | Journal | 34 |
Issue | ISSN | Citations |
4 | 0364-765X | 11 |
PageRank | References | Authors |
0.58 | 23 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yichuan Ding | 1 | 62 | 5.14 |
| Henry Wolkowicz | 2 | 1444 | 260.72 |