The quadratic assignment problem. Theory and algorithms (Q1377989): Difference between revisions

This monograph surveys the state of the art of quadratic assignment problems (QAPs) and describes for the first time in detail special cases of the QAP which can be solved by polynomial algorithms. Given the set \(N:=\{1,2,\ldots,n\}\) and two \(n \times n\) matrices \(A=(a_{ij})\) and \(B=(b_{ij})\), the QAP asks for a permutation \(\pi\) of \(N\) which minimizes \[ \sum_{i=1}^n \sum_{j=1}^n a_{\pi(i)\pi(j)}b_{ij}. \] The first chapter deals with problem formulations, applications and linearizations of the QAP and dicusses the computational complexity of these problems. The second chapter surveys exact algorithms for the QAP such as branch and bound and cutting plane methods. A strong emphasis is given to the computation of lower bounds (Gilmore-Lawler bound, eigenvalue bounds, bounds based on linear programming and semidefinite programming relaxations, decomposition). Chapter 3 deals with heuristics (construction and improvement methods) and metaheuristics like simulated annealing (SA), genetic algorithms and greedy randomized adaptive search (GRASP). Moreover, the surprising asymptotic behaviour of QAPs, namely that asymptotically almost every solution is optimal, is described. The next 3 chapters deal with special cases of the QAP which are polynomially solvable. First, problems with specially structured matrices \(A\) and \(B\) are described. In particular the anti-Monge-Toeplitz QAP is discussed, where \(A\) is an anti-Monge matrix and \(B\) is a Toeplitz matrix. This problem has several applications (turbine runner problem, data arrangement). Then special cases related to the underlying graph structure are discussed. Here \(A\) is viewed as a weighted adjacency matrix of some undirected graph with \(n\) vertices. In particular relations to the feedback arc set problem and to certain packing problems in graphs are established. The last chapter deals with a generalization of the QAP, the so-called biquadratic assignment problem (BiQAP) \[ \sum_{i=1}^n \sum_{j=1}^n \sum_{k=1}^n \sum_{l=1}^n a_{\pi(i)\pi(j)\pi(k)\pi(l)}b_{ijkl}. \] Lower bounds for this problem are derived and heuristics (SA, tabu search, GRASP) are discussed. Moreover, it is shown that BiQAPs have the same asymptotic behaviour as QAPs. The monograph closes with an extensive bibliography of 232 titles. Altogether this is the most comprehensive and up-to-date book on the important problem class of QAPs, which not only surveys known results but also contributes lots of own investigations.