Journal article
Solving quadratic assignment problems using convex quadratic programming relaxations
Optimization methods & software, Vol.16(1-4), pp.49-68
01/01/2001
DOI: 10.1080/10556780108805828
Abstract
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
Details
- Title: Subtitle
- Solving quadratic assignment problems using convex quadratic programming relaxations
- Creators
- Kurt M. Anstreicher - University of IowaNathan W. Brixius - University of Iowa
- Resource Type
- Journal article
- Publication Details
- Optimization methods & software, Vol.16(1-4), pp.49-68
- Publisher
- Gordon and Breach Science Publishers
- DOI
- 10.1080/10556780108805828
- ISSN
- 1055-6788
- eISSN
- 1029-4937
- Language
- English
- Date published
- 01/01/2001
- Academic Unit
- Industrial and Systems Engineering; Computer Science; Business Analytics
- Record Identifier
- 9984380515502771
Metrics
2 Record Views