Quantcast

A new bound for the quadratic assignment problem based on convex quadratic programming

Research paper by Kurt M. Anstreicher, Nathan W. Brixius

Indexed on: 01 Feb '01Published on: 01 Feb '01Published in: Mathematical Programming



Abstract

We describe a new convex quadratic programming bound for the quadratic assignment problem (QAP). The construction of the bound uses a semidefinite programming representation of a basic eigenvalue bound for QAP. The new bound dominates the well-known projected eigenvalue bound, and appears to be competitive with existing bounds in the trade-off between bound quality and computational effort.