Brixius, Nathan W.; Anstreicher, Kurt M. Solving quadratic assignment problems using convex quadratic programming relaxations. (English) Zbl 0991.90107 Optim. Methods Softw. 16, No. 1-4, 49-68 (2001). Summary: We describe a branch-and-bound algorithm for the quadratic assignment problem (QAP) that uses a convex quadratic programming (QP) relaxation to obtain a bound at each node. The QP subproblems are approximately solved using the Frank-Wolfe algorithm, which in this case requires the solution of a linear assignment problem on each iteration. Our branching strategy makes extensive use of dual information associated with the QP subproblems. We obtain state-of-the-art computational results on large benchmark QAPs. Cited in 13 Documents MSC: 90C27 Combinatorial optimization 90C20 Quadratic programming 90B80 Discrete location and assignment 90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut Keywords:branch-and-bound algorithm; quadratic assignment problem; convex quadratic programming; Frank-Wolfe algorithm Software:HTCondor MW; ZRAM; QAPLIB; Meschach PDFBibTeX XMLCite \textit{N. W. Brixius} and \textit{K. M. Anstreicher}, Optim. Methods Softw. 16, No. 1--4, 49--68 (2001; Zbl 0991.90107) Full Text: DOI