×

zbMATH — the first resource for mathematics

Quadratic assignment problems. (English) Zbl 0607.90026
Surveys in combinatorial optimization, Lect. Rio de Janeiro/Braz. 1985, Ann. Discrete Math. 31, 61-82 (1987).
[For the entire collection see Zbl 0599.00013.]
Quadratic assignment problems (QAPs) arise in connection with important locational problems. So far, however, only QAPs of very moderate sizes can be solved optimally. The most successful computer algorithms are branch and bound methods which elaborate on the so-called Gilmore-Lawler bounds.
We shall use the trace formulation of QAPs, which was first suggested by C. S. Edwards [Math. Program. Study 13, 35-52 (1980; Zbl 0441.90081)], to derive the known reduction results by means of simple matrix manipulations. This approach also yields completely new competitive bounds for the symmetric case based on the eigenvalues of the underlying matrices. The eigenvalue related bounds give access to an optimal reduction procedure and also help to characterize QAPs which are almost linear.

MSC:
90B05 Inventory, storage, reservoirs
90C27 Combinatorial optimization
90C08 Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.)
65K05 Numerical mathematical programming methods
68Q25 Analysis of algorithms and problem complexity