×

Solving quadratic assignment problems using convex quadratic programming relaxations. (English) Zbl 0991.90107

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.

MSC:

90C27 Combinatorial optimization
90C20 Quadratic programming
90B80 Discrete location and assignment
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDFBibTeX XMLCite
Full Text: DOI