The Quadratic Assignment Problem

In this chapter we introduce the quadratic assignment problem (QAP) . We start with the definition of the QAP and some frequently used formulations for it. Then, we consider the applications of the QAP and discuss in more details the most celebrated ones: applications in facility location and applications in wiring problems. Further, three mixed integer linear programming (MILP) formulations of the QAP are introduced: the Kaufman and Broeckx linearization [141], the Frieze and Yadegar linearization [83], and the linearization of Padberg and Rijal [177]. These formulations are chosen among numerous MILP formulation proposed in the literature in the hope that they can better help for a deep understanding of the QAP and its combinatorial structure. Consider that the linearization of Kaufman and Broeckx is perhaps the smallest QAP linearizations in terms of the number of variables and constraints, whereas some of the best existing bounding procedures for the QAP are obtained by building upon the linearization of Frieze and Yadegar. Furthermore, the linearization of Padberg and Rijal is the basis of recent significant results on the QAP polytope. Based on this linearization, the affine hull and the dimension of the QAP polytope (symmetric QAP polytope) have been computed. Moreover, some valid inequalities for the QAP polytope and some facet defining equalities for the symmetric QAP polytope have been identified. Finally, we consider computational complexity aspects of the QAP, discussing among others the complexity of approximating the problem, and the complexity of the local search.

This chapter gives a summary on approaches and methods used for solving QAPs to optimality. Since the QAP is an NP-hard problem, only explicit (simple and straightforward) and implicit enumeration methods are known for solving it exactly. For a long time, branch and bound algorithms have been the most successful optimization approaches to QAPs, outperforming cutting plane algorithms whose convergence running time is simply unfeasible. Recently, theoretical results obtained on the combinatorial structure of the QAP polytope have raised new hopes that, in the future, polyhedral cutting planes can be successfully used for solving reasonably sized QAPs. Clearly, the design of efficient branch and cut methods in the vein of those already developed for the TSP (see for example [178]) is conditioned by the identification of new valid and possibly facet defining inequalities for the QAP polytope, and the development of the corresponding separation algorithms. Hence, quite a lot of efforts are required before the current size limits of solvable QAPs can be significantly improved.

We saw in the previous section that only small QAP instances (instances of size up to 22) can be solved to optimality. On the other side, the large spectrum of applications of the QAP often leads to instances of much larger size. Under these conditions, polynomial time heuristics providing suboptimal solutions to the QAP abound in the literature. Without pretending to mention all kinds of heuristic approaches which have been applied to QAPs, we try to review the main and most fruitful ideas in this research direction. There are five main streams of heuristic approaches to QAP, listed in chronological order below.

In this chapter and in the two next chapters we consider polynomially solvable and provably difficult (NP-hard) cases of the QAP. As there is no hope to find a polynomial time algorithm for solving the general QAP, and as QAP instances arising in different practical applications may often have a special structure, it is interesting to derive polynomial time algorithms for solving special cases of the problem. On the other hand, any information on provably difficult (NP-hard) cases of the problem is of particular relevance for a better understanding of the problem and its complexity. Nowadays there exist only few, sporadic results concerning this challenging but difficult aspect of research on the QAP. We try to give a systematic presentation of the already existing results on complexity questions related to special cases of the QAP, focusing on methodology issues. Further, we formulate a number of open problems which we consider to be a promising obj ect of further research in this direction.

In this chapter which is a continuation of the previous one, we consider two restricted version of the QAP: the Anti-Monge—Toeplitz QAP and the KalmansonToeplitz QAP. The Anti-Monge—Toeplitz QAP is a restricted version of the QAP, where one of the coefficient matrices is a left-higher graded Anti-Monge matrix and the other one is a symmetric Toeplitz matrix. The interest in this problem is motivated by a number of practical applications, e.g. the turbine problem and the data arrangement problem, some of which will be considered in detail in the second section of this chapter. Moreover, the Anti-Monge—Toeplitz QAP contains the TSP on symmetric Monge matrices as a special case. Despite the very special structure of the Anti-Monge—Toeplitz QAP, i.e., the quite restrictive conditions to be fulfilled by its coefficient matrices, the problem is NP-hard. Namely, the turbine problem which is a special case of the Anti-Monge—Toeplitz QAP is NPhard, as shown by Burkard, Çela, Rote and Woeginger [33] . However, for Toeplitz matrices satisfying some additional conditions, (e.g. benevolent, k-benevolent, or bandwidth-2 matrices) , the Anti-Monge Toeplitz QAP becomes polynomially solvable. These polynomially solvables special cases of the problem which are constant permutation QAPs, will be described in detail in the first section of this chapter. Then, a polynomially solvable version of the Kalmanson-Toeplitz QAP, which i.e. a QAP with a Kialmanson and a Toeplitz matrix, is described. Further, so-called permuted polynomially solvable cases of the QAP are briefly discussed.

Many optimization problems in graphs can be formulated as QAPs with a special structure. Most of these optimization problems in graphs are NP-hard. However a number of polynomially solvable special cases have been identified for them. We believe that the general knowledge and understanding of the QAP can benefit from a closer look at these problems and the corresponding formulations as QAPs. This is the motivation for writing this chapter.

In this chapter we discuss a natural generalization of the QAP, namely the biquadratic assignment problem, shortly denoted by BiQAP. In the BiQAP a weighted sum of products of four variables x _ij is to be minimized subject to assignment constraints on the variables x _ij .