A New Lower Bound Via Projection for the Quadratic Assignment Problem

New lower bounds for the quadratic assignment problem QAP are presented. These bounds are based on the orthogonal relaxation of QAP. The additional improvement is obtained by making efficient use of a tractable representation of orthogonal matrices having constant row and column sums. The new bound...

Full description

Saved in:
Bibliographic Details
Published in:Mathematics of operations research 1992-08, Vol.17 (3), p.727-739
Main Authors: Hadley, S. W, Rendl, F, Wolkowicz, H
Format: Article
Language:English
Subjects:
Algorithms
Applied mathematics
Applied sciences
Discrete mathematics
Dot product of vectors
eigenvalue bounds
Eigenvalues
Eigenvectors
Exact sciences and technology
Experiments
Flows in networks. Combinatorial problems
Functions
Integers
Iterative solutions
Linear transformations
lower bounds
Mathematical analysis
Objective functions
Operational research and scientific management
Operational research. Management science
Operations research
orthogonal projection
quadratic assignment problem
relaxations
Theory
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:New lower bounds for the quadratic assignment problem QAP are presented. These bounds are based on the orthogonal relaxation of QAP. The additional improvement is obtained by making efficient use of a tractable representation of orthogonal matrices having constant row and column sums. The new bound is easy to implement and often provides high quality bounds under an acceptable computational effort.
ISSN:0364-765X
1526-5471
DOI:10.1287/moor.17.3.727