Quadratic assignment problems. (English) Zbl 0607.90026

Finke, Gerd; Burkard, Rainer E.; Rendl, Franz

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

Keywords:

eigenvalue bounds; Quadratic assignment problems; Gilmore-Lawler bounds; trace formulation; reduction