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

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

0.00 Avg rating0 Votes
Article ID: iaor2002479
Country: Germany
Volume: 89
Issue: 3
Start Page Number: 341
End Page Number: 357
Publication Date: Jan 2001
Journal: Mathematical Programming
Authors: ,
Keywords: quadratic assignment
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.

Reviews

Required fields are marked *. Your email address will not be published.