Voltar
Artigo Revisado por pares
BIBTEX RIS

A New Lower Bound Via Projection for the Quadratic Assignment Problem

1992; Institute for Operations Research and the Management Sciences; Volume: 17; Issue: 3 Linguagem: Inglês

10.1287/moor.17.3.727

ISSN

1526-5471

Autores

Scott Hadley, Franz Rendl, Henry Wolkowicz,

Tópico(s)

Optimization and Search Problems

Resumo

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.

Referência(s)