Invited Review

A survey for the quadratic assignment problem☆

2.1.1. Integer linear programming formulations (IP)

First, we present the QAP as a Boolean program followed by a linear programming problem, where the binary constraints are relaxed. The Boolean formulation was initially proposed by Koopmans and Beckmann (1957) and later used in several works such as Steinberg, 1961, Lawler, 1963, Gavett and Plyter, 1966, Elshafei, 1977, Bazaraa and Sherali, 1979, Bazaraa and Kirca, 1983, Christofides and Benavent, 1989, Bos, 1993, Mans et al., 1995, Jünger and Kaibel, 2000, Jünger and Kaibel, 2001a, Jünger and Kaibel, 2001b, Liang, 1996, Torki et al., 1996, Tsuchiya et al., 1996, Tsuchiya et al., 2001, Ball et al., 1998, Ishii and Sato, 1998, Kaibel, 1998, Kochhar et al., 1998, Martin, 1998, Spiliopoulos and Sofianopoulou, 1998, and most recently, Siu and Chang, 2002, Yu and Sarker, 2003 and, finally, Fedjki and Duffuaa (2004).

We consider f_ij the flow between facilities i and j, and d_kp the distance between locations k and p. It is our goal to calculate:(2.1)$\min \sum _{i\text{,}j=1}^n\sum _{k\text{,}p=1}^n{f}_{\mathit{ij}}{d}_{\mathit{kp}}{x}_{\mathit{ik}}{x}_{\mathit{jp}}$(2.2)$\mathrm{s}.\mathrm{t}.\sum _{i=1}^n{x}_{\mathit{ij}}=11⩽j⩽n\text{,}$(2.3)$\sum _{j=1}^n{x}_{\mathit{ij}}=11⩽i⩽n\text{,}$(2.4)$x_{\mathit{ij}}\in \{0\text{,}1\}1⩽i\text{,}j⩽n\text{.}$If we consider the cost of assignment of activities to locations, a general form for a QAP instance of order n is given by three matrices F = [f_ij], D = [d_kp] and B = [b_ik], the first two matrices defining the flows between facilities and the distances between locations, b_ik being the allocation costs of facilities to locations. This problem can be defined as:(2.5)$\min \sum _{i\text{,}j=1}^n\sum _{k\text{,}p=1}^n{f}_{\mathit{ij}}{d}_{\mathit{kp}}{x}_{\mathit{ik}}{x}_{\mathit{jp}}+\sum _{i\text{,}k=1}^n{b}_{\mathit{ik}}{x}_{\mathit{ik}}$Since the linear term of (2.5) is easy to solve, most authors discarded it.

A more general QAP version was proposed by Lawler (1963) and involves costs c_ijkp that do not necessarily correspond to products of flows and distances. The Lawler formulation is as follows:(2.6)$\min \sum _{i\text{,}j=1}^n\sum _{k\text{,}p=1}^n{c}_{\mathit{ijkp}}{x}_{\mathit{ik}}{x}_{\mathit{jp}}$This model was also used in Bazaraa and Elshafei, 1979, Drezner, 1995, Sarker et al., 1995, Sarker et al., 1998, Brüngger et al., 1997, Brüngger et al., 1998, Chiang and Chiang, 1998, Hahn and Grant, 1998, Hahn et al., 1998, Gong et al., 1999, Rossin et al., 1999.

2.1.2. Mixed integer linear programming (MILP) formulations

The QAP, as a mixed integer programming formulation, is found in the literature in different forms. All of them replace the quadratic terms by linear terms. For example, Lawler (1963) used n⁴ variables,$c_{\mathit{ijkp}}=f_{\mathit{ij}}{d}_{\mathit{kp}}\mathrm{and}{y}_{\mathit{ijkp}}=x_{\mathit{ik}}{x}_{\mathit{jp}}\text{,}1⩽i\text{,}j\text{,}k\text{,}p⩽n\text{.}$Other formulations use relaxations of the original problem. In this category, one can find the papers by Love and Wong, 1976a, Love and Wong, 1976b, Kaufman and Broeckx, 1978, Bazaraa and Sherali, 1980, Christofides et al., 1980, Burkard and Bonniger, 1983, Frieze and Yadegar, 1983, Assad and Xu, 1985, Adams and Sherali, 1986, Christofides and Benavent, 1989 and the works of Adams and Johnson, 1994, Drezner, 1995, Gouveia and Voß, 1995, Milis and Magirou, 1995, Padberg and Rijal, 1996, White, 1996, Ramachandran and Pekny, 1998, Karisch et al., 1999 and of Ramakrishnan et al. (2002).

In general, QAP linearizations based on MILP models present a huge number of variables and constraints, a fact that makes this approach unpopular. However, these linearizations, together with some constraint relaxations, lead to the achievement of much improved lower bounds for the optimal solution. In this regard, we have the works of Kaufman and Broeckx, 1978, Bazaraa and Sherali, 1980, Frieze and Yadegar, 1983, Adams and Sherali, 1986, Adams and Johnson, 1994, Padberg and Rijal, 1996. Çela (1998) mentions three QAP linearizations: Kaufman and Broeckx (1978), which has the advantage of a smaller number of restrictions; Frieze and Yadegar (1983), for achieving the best lower bounds via Lagrangean relaxation and Padberg and Rijal (1996) owing to its polytope description. The formulation presented by Frieze and Yadegar (1983) describes the QAP in a linear form, using n⁴ real variables, n² Boolean variables and n⁴ + 4n³ + n² + 2n constraints. The authors show that the formulation given in (2.7), (2.8), (2.9), (2.10), (2.11), (2.12), (2.13), (2.14), (2.15), (2.16) below is equivalent to Eqs. (2.1), (2.2), (2.3), (2.4), Çela (1998).(2.7)$\min \sum _{i\text{,}j=1}^n\sum _{k\text{,}p=1}^n{f}_{\mathit{ij}}{d}_{\mathit{kp}}·y_{\mathit{ijkp}}$(2.8)$\mathrm{s}.\mathrm{t}.\sum _{i=1}^n{x}_{\mathit{ik}}=11⩽k⩽n\text{,}$(2.9)$\sum _{k=1}^n{x}_{\mathit{ik}}=11⩽i⩽n\text{,}$(2.10)$\sum _{i=1}^n{y}_{\mathit{ijkp}}=x_{\mathit{jp}}1⩽j\text{,}k\text{,}p⩽n\text{,}$(2.11)$\sum _{j=1}^n{y}_{\mathit{ijkp}}=x_{\mathit{ik}}1⩽i\text{,}k\text{,}p⩽n\text{,}$(2.12)$\sum _{k=1}^n{y}_{\mathit{ijkp}}=x_{\mathit{jp}}1⩽i\text{,}j\text{,}p⩽n\text{,}$(2.13)$\sum _{p=1}^n{y}_{\mathit{ijkp}}=x_{\mathit{ik}}1⩽i\text{,}j\text{,}k⩽n\text{,}$(2.14)$y_{\mathit{iikk}}=x_{\mathit{iik}}1⩽i\text{,}k⩽n\text{,}$(2.15)$x_{\mathit{ik}}\in \{0\text{,}1\}1⩽i\text{,}k⩽n\text{,}$(2.16)$0⩽y_{\mathit{ijkp}}⩽11⩽i\text{,}j\text{,}k\text{,}p⩽n\text{.}$

2.1.3. Formulations by permutations

Taking a simple approach, the pairwise allocation of facility costs to adjacent locations is proportional to flows and to distances between them. The QAP formulation that arises from this proportionality and uses the permutation concept can be found in Hillier and Michael, 1966, Graves and Whinston, 1970, Pierce and Crowston, 1971, Burkard and Stratman, 1978, Roucairol, 1979, Roucairol, 1987, Burkard, 1984, Frenk et al., 1985, Bland and Dawson, 1991, Bland and Dawson, 1994, Battiti and Tecchiolli, 1994, Bui and Moon, 1994, Chakrapani and Skorin-Kapov, 1994, Fleurent and Ferland, 1994, Li et al., 1994b, Mautor and Roucairol, 1994a, Mautor and Roucairol, 1994b, Li and Smith, 1995, Taillard, 1995, Bozer and Suk-Chul, 1996, Colorni et al., 1996, Huntley and Brown, 1996, Peng et al., 1996, Tian et al., 1996, Tian et al., 1999, Cung et al., 1997, Mavridou and Pardalos, 1997, Merz and Freisleben, 1997, Nissen, 1997, Pardalos et al., 1997, Angel and Zissimopoulos, 1998, Deineko and Woeginger, 1998, Talbi et al., 1998a, Talbi et al., 1998b, Talbi et al., 2001, Tansel and Bilen, 1998, Abreu et al., 1999, Fleurent and Glover, 1999, Gambardella et al., 1999, Maniezzo and Colorni, 1999. More recently, the following articles were released: Ahuja et al., 2000, Angel and Zissimopoulos, 2000, Angel and Zissimopoulos, 2001, Angel and Zissimopoulos, 2002, Stützle and Holger, 2000, Arkin et al., 2001, Pitsoulis et al., 2001, Abreu et al., 2002, Gutin and Yeo, 2002, Hasegawa et al., 2002, Boaventura-Netto, 2003, Rangel and Abreu, 2003. Costa and Boaventura-Netto (1994) studied the non-symmetrical QAP through a directed graph formulation.

Let S_n be the set of all permutations with n elements and π ∈ S_n. Consider f_ij the flows between facilities i and j and d_π(i)π(j) the distances between locations π(i) and π(j). If each permutation π represents an allocation of facilities to locations, the problem expression becomes:(2.17)$\underset{\pi \in S_n}{\min }\sum _{i\text{,}j=1}^n{f}_{\mathit{ij}}{d}_{\pi (i)\pi (j)}\text{.}$This formulation is equivalent to the first one presented in (2.1), (2.2), (2.3), (2.4), since the constraints (2.2), (2.3) define permutation matrices X = [x_ij] related to S_n elements, as in (2.17), where, for all 1 ⩽ i, j ⩽ n,(2.18)$x_{\mathit{ij}}=\begin{array}{cc}1\text{,}\hfill & \mathrm{if}\pi (i)=j\text{;}\hfill \\ 0\text{,}\hfill & \mathrm{if}\pi (i)\ne j.\hfill \end{array}$

2.1.4. Trace formulation

This formulation is supported by linear algebra and exploits the trace function (the sum of the matrix main diagonal elements) in order to determine QAP lower bounds for the cost. This approach allows for the application of spectral theory, which makes possible the use of semi-definite programming to the QAP. The trace formulation, by Edwards (1980), can be stated as:(2.19)$\underset{X\in S_n}{\min }\mathrm{tr}(F·X·D·X^{\mathrm{t}})\text{.}$Afterwards, this approach was used in several works: Finke et al., 1987, Hadley et al., 1990, Hadley et al., 1992a, Hadley et al., 1992b, Hadley et al., 1992c, Hadley, 1994, Karisch et al., 1994, Karisch and Rendl, 1995, Zhao et al., 1998, Anstreicher et al., 1999, Wolkowicz, 2000a, Wolkowicz, 2000b, Anstreicher and Brixius, 2001.

The following formulations define QAP relaxations through the dual of the Lagrangean dual, as we find in Karisch et al., 1994, Zhao et al., 1998, Wolkowicz, 2000a, Wolkowicz, 2000b. Let e be a vector with each coordinate equal to 1. If X is a permutation matrix and B is a cost matrix, then the SDP formulation is:(2.20)$\min \mathrm{tr}(F·X·D-2B)X^{\mathrm{t}}$(2.21)$\mathrm{s}.\mathrm{t}.\mathit{Xe}=e\text{,}$(2.22)$X^{\mathrm{t}}e=e\text{,}$(2.23)$X_{\mathit{ij}}\in \{0\text{,}1\}\forall i\text{,}j\text{.}$Another formulation that follows this approach, Zhao et al. (1998), is(2.24)$\min \mathrm{tr}F·X·D·X^{\mathrm{t}}-2{\mathit{BX}}^{\mathrm{t}}$(2.25)$\mathrm{s}.\mathrm{t}.{\mathit{XX}}^{\mathrm{t}}=X^{\mathrm{t}}X=I\text{,}$(2.26)$\mathit{Xe}=X^{\mathrm{t}}e=e\text{,}$(2.27)$X_{\mathit{ij}}^2-X_{\mathit{ij}}=0\forall i\text{,}j\text{.}$From the formulations (2.20), (2.21), (2.22), (2.23), (2.24), (2.25), (2.26), (2.27) one can derive semi-definite relaxations for the QAP. Roupin (2004) presents a simple algorithm to obtain SDP relaxations for any quadratic or linear program with bivalent variables, starting from an existing linear relaxation of the considered combinatorial problem. This algorithm is applied to obtain semi-definite relaxations for three classical combinatorial problems: the k-Cluster Problem, the Quadratic Assignment Problem, and the Constrained-Memory Allocation Problem.

2.1.5. Graph formulation

Let us consider two undirected weighted complete graphs, the first one having its edges associated to flows and the second one, to distances. The QAP can be thought as the problem of finding an optimal allocation of the vertices of one graph on those of the other. In this formulation the solution costs are given as the sum of products of corresponding edge weights (see Fig. 1).

1. Download : Download full-size image

Fig. 1. Allocation of cliques K_F over K_D concerning permutation π = (4, 2, 1, 3).

The algebraic and combinatorial approach adopted by Abreu et al. (1999) was the impetus for Marins et al. (2004) to define a new algebraic graph–theoretical approach involving line-graph automorphisms. The line-graph of a given graph G, denoted L(G), is determined by taking each edges of G as a vertex of L(G), while an edge of L(G) is defined as a pair of edges that are adjacent in G. A graph automorphism is a permutation of its vertices that preserves the edges. The set of all automorphisms of G together with the permutations composition is a group denoted by Aut(L(G)) (Kreher and Stinson (1998)).

From a theorem by Whitney (1932), if G = K_n, n ≠ 2 and 4, then Aut(G) and Aut(L(G)) constitute isomorphic groups. Based on this result, Marins et al. (2004) noticed that solving the QAP means either finding a permutation π ∈ S_n or finding a L(K_n) automorphism, which is a C_n,2 permutation, that minimizes the following expression:(2.28)$\underset{\pi \in \mathrm{Aut}(L(K_n))}{\min }\sum _{i=1}^N{f}_i{d}_{\pi (i)}\text{.}$It is appropriate to mention White (1995), wherein a number of QAP representations are discussed with respect to their convexity and concavity and also Yamada (1992), where a formulation is presented for the QAP on an n-dimensional grid.

2.2.1. The quadratic bottleneck assignment problem (QBAP)

Steinberg (1961) considered QBAP a variation of QAP with applications to backboard wiring. In that work, a placement algorithm was presented for the optimal connection of n elements in individual locations so that the length wire needed to connect two elements is minimized. The basic claim of the paper is: the optimal weighted-wire-length equals the least among the maximum-wire-length norms. This concept arises from the principle that it may be better to minimize the largest cost in a problem, than to minimize the overall cost.

The QBAP general program is obtained from the QAP formulation by substituting the maximum operation in the objective function for the sums, which suggests the term bottleneck function:(2.30)$\underset{\pi \in S_n}{\min }\max \{f_{\mathit{ij}}{d}_{\pi (i)\pi (j)}:1⩽i\text{,}j⩽n\}\text{.}$A general formulation related to (2.30) was studied in Burkard and Finke, 1982, Burkard and Zimmermann, 1982, Kellerer and Wirsching, 1998, Burkard, 2002.

2.2.2. The biquadratic assignment problem (BiQAP)

Proposed by Burkard et al. (1994), this problem can be found in other works, such as Burkard and Çela, 1995, Mavridou et al., 1998, Burkard, 2002. The flow and distance matrices are order n⁴ and the BiQAP-formulation is:(2.31)$\underset{\pi \in S_n}{\min }\sum _{i\text{,}j\text{,}k\text{,}l=1}^n{f}_{\mathit{ijkl}}{d}_{\pi (i)\pi (j)\pi (k)\pi (l)}\text{.}$

2.2.3. The quadratic 3-dimensional assignment problem (Q3AP)

Pierskalla (1967b) introduced it in a technical memorandum. The work was never published in the open literature. Since then, nothing on the subject has been found in the publication databases. Hahn et al. (2004) re-discovered the Q3AP while working with others on a problem arising in data transmission system design. The purpose of the work is to jointly optimize pairs of mappings for multiple transmissions using higher order signal constellations. The resulting problem formulation is:(2.32)$\min \left.\begin{array}{c}\sum _{i=1}^N\sum _{j=1}^N\sum _{p=1}^N{b}_{\mathit{ijp}}{u}_{\mathit{ij}}{w}_{\mathit{ip}}+\sum _{i=1}^N\sum _{j=1}^N\sum _{p=1}^N\sum _{k=1}^N\sum _{n=1}^N\sum _{q=1}^N\hfill \\ \times C_{\mathit{ijpknq}}{u}_{\mathit{ij}}{u}_{\mathit{kn}}{w}_{\mathit{ip}}{w}_{\mathit{kq}}:\mathbf{u}\in \mathbf{X}\text{,}\mathbf{w}\in \mathbf{X}\text{;}\mathbf{u}\text{,}\mathbf{w}\mathrm{binary}\hfill \end{array}\right\}\text{,}$where(2.33)$\mathbf{x}\in \mathbf{X}\equiv \left.\mathbf{x}⩾0:\sum _{i=1}^N{x}_{\mathit{ij}}=1\mathrm{for}j=1\text{,}\dots \text{,}N\text{;}\sum _{j=1‘}^N{x}_{\mathit{ij}}=1\mathrm{for}i=1\text{,}\dots \text{,}N\right\}\text{.}$

2.2.4. The quadratic semi-assignment problem (QSAP)

This is a special case used to model clustering and partitioning problems by Hansen and Lih (1992). It can be written as:(2.34)$\min \sum _{k=1}^m\sum _{i\text{,}j=1}^n{c}_{\mathit{ij}}{x}_{\mathit{ik}}{x}_{\mathit{jk}}$(2.35)$\mathrm{s}.\mathrm{t}.\sum _{k=1}^m{x}_{\mathit{ik}}=11⩽i⩽n\text{,}$(2.36)$x_{\mathit{ij}}\in \{0\text{,}1\}1⩽i\text{,}j⩽n\text{.}$Other applications can be found in Simeone, 1986a, Simeone, 1986b, Bullnheimer, 1998. References for polynomial heuristics and lower bounds are found in Freeman et al., 1966, Magirou and Milis, 1989, Carraresi and Malucelli, 1994, Billionnet and Elloumi, 2001. Samra et al. (2005) presented a simple, but effective method of enhancing and exploiting diversity from multiple packet transmissions in systems that employ non-binary linear modulations such as phase-shift keying (PSK) and quadrature amplitude modulation (QAM). The optimal adaptation scheme reduces to solving the general form of the QAP, wherein the problem costs cannot be expressed as products of flows and distances (see Eq. (2.6), above).

2.2.5. The multiobjective QAP (mQAP)

Knowles and Corne (2002) presented another QAP variation considering several flow and distance matrices. This problem is a benchmark case for multiobjective metaheuristics or multiobjective evolutionary algorithms. According to the authors, this model is more suitable for some layout problems, such as the allocation of facilities in hospitals, where it is desired to minimize the products of the flows by the distances between doctors and patients, and between nurses and medical equipment simultaneously. The mathematical expression is then,(2.37)$\begin{array}{cc}\hfill & \underset{\pi \in S_n}{\min }\overrightarrow{C}(\pi )=\{C^1(\pi )\text{,}{C}^2(\pi )\text{,}\dots \text{,}{C}^m(\pi )\}\text{,}\hfill \\ \hfill & \mathrm{where}{C}^k(\pi )=\sum _{i\text{,}j=1}^n{f}_{\mathit{ij}}^k{d}_{\pi (i)\pi (j)}\text{,}1⩽k⩽m\text{.}\hfill \end{array}$In this last constraint, $f_{\mathit{ij}}^k$ denotes the kth flow between i- and j-facilities. More recently, Knowles and Corne (2003) presented instance generators for the multiobjective version of QAP. Lopez-Ibanez et al. (2004) discuss the design of ACO algorithms. Paquete and Stützle (2004) developed a study of stochastic local search algorithms for the biobjective QAP with different degrees of correlation between the flow matrices. Kleeman et al. (2004) analyze a parallel technique and Day and Lamont (2005) present a specific algorithm.

A combination QAP queuing model is discussed by Smith and Li (2001), in the context of traffic networks.

4.1.1. The effects of methodology and computer speed improvements

A number of important problem instances have been solved to optimality in recent years. The details can be found on the QAPLIB homepage (QAPLIB (2004)): Ste36b-c (by Nyström in 1999); Bur26a (by Hahn in October 2001); Ste36a (by Brixius and Anstreicher in October 2001); Kra30b, Kra32 and Tho30 (by Anstreicher et al. in November 2000); Kra30a (by Hahn in December 2000); Tai25a (by Hahn in 2003); and Bur26b-h (by Hahn in 2004).

4.3.1. The following metaheuristics are based on natural process metaphors

Simulated annealing is a local search algorithm that exploits the analogy between combinatorial optimization algorithms and statistical mechanics (Kirkpatrick et al., 1983). This analogy is made by associating the feasible solutions of the combinatorial optimization problem to states of the physical system, having costs associated to these states energies. Let E_i and E_i+1 be two energy successive states, corresponding to two neighbor solutions and let ΔE = E_i+1 − E_i. The following situations can occur: if ΔE < 0, there is an energy reduction and the process continues. In other words, there is a reduction on the problem cost function and the new allocation may be accepted; if ΔE = 0, there is a stability situation and there is no change in the energy state. This means that the problem cost function was not changed; if ΔE > 0, an increase on the energy is characterized and it is useful for the physical process to permit particle accommodation, i.e., the problem cost function is increased. Instead of eliminating this allocation, its use is subjected to the values of a probability function, to avoid convergence into poor local minima. Burkard and Rendl (1984) proposed one of the first applications of simulated annealing to the QAP. After that, Wilhelm and Ward (1987) presented the new equilibrium components for it. Connolly (1990) introduced an optimal temperature concept that gave valuable results. Later, Abreu et al. (1999) applied the technique by trying to reduce the number of inversions associated to the problem solution, together with the cost reduction. Other approaches for the simulated annealing applied to the QAP are Bos, 1993, Yip and Pao, 1994, Burkard and Çela, 1995, Peng et al., 1996, Tian et al., 1996, Tian et al., 1999, Mavridou and Pardalos, 1997, Chiang and Chiang, 1998, Misevicius, 2000b, Misevicius, 2003c, Tsuchiya et al., 2001, Siu and Chang, 2002, Baykasoglu, 2004.

Genetic algorithms are techniques that simulate the natural selection and adaptation found in nature. These algorithms keep a population formed by a subset of individuals that correspond, in the QAP case, to the feasible permutations, with fitness values associated to their permutation cost. By means of the so-called genetic operators, and of selection criteria, the algorithm replaces one population by another with best available fitness values. The scheme is based on the idea that the best individuals survive and generate descendents that carry their genetic characteristics, in the same way that biological species propagate in nature.

Genetic algorithms generally begin with a population of randomly generated initial individuals (i.e., solutions). Their costs are evaluated and a subset with the lowest cost solutions is selected. Genetic operations are applied to this subset, thus generating a new solution set (a new population). The process continues until some stopping criterion is met. See Davis, 1987, Goldberg, 1989. Various ideas for the use of genetic algorithms on the QAP can be found in Bui and Moon, 1994, Tate and Smith, 1995, Mavridou and Pardalos, 1997, Kochhar et al., 1998, Tavakkoli-Moghaddain and Shayan, 1998, Gong et al., 1999, Drezner and Marcoulides, 2003, El-Baz, 2004, Wang and Okazaki, 2005. Drezner (2005a) presented a two-phase genetic algorithm. The first one is a quick genetic strategy that runs several times, keeping the best solution at each iteration to build a starting population for Phase 2. The use of these algorithms in the QAP context presents some difficulties in getting the optimal solution, even for small instances. However, some hybrid ideas using genetic algorithms have shown to be more efficient, as discussed later in this paper.

Scatter search is a technique introduced by Glover (1977) in a heuristic study of integer linear programming problems. It is an evolutionary method that takes linear combinations of solution vectors in order to produce new solution vectors in successive generations. This metaheuristic is composed of initial and evolutionary phases. In the initial phase, a reference set of good solutions is made. In each subsequent (evolutionary) phase, new solutions are generated using strategically selected combinations of the reference subset. Then, a set of the best newly generated solutions is moved into the reference set. The evolutionary phase procedure is repeated until a stop criterion is satisfied. Application of scatter search to the QAP can be found in Cung et al. (1997).

Ant colony optimization (ACO) refers to a class of distributed algorithms that has as its most important feature the definition of properties in the interaction of several simple agents (the ants). Its principle is the way in which ants are able to find a path from the colony to a food source. The set of ants, cooperating in an ordinary activity to solve a problem, constitute the ant system. The main characteristic of this method is the fact that the interaction of these agents generates a synergetic effect, because the quality of the obtained solutions increases when these agents work together, interacting among themselves. Numerical results for the QAP are presented in Maniezzo and Colorni, 1995, Maniezzo and Colorni, 1999, Colorni et al., 1996, Dorigo et al., 1996. Gambardella et al. (1999) show ant colony as a competitive metaheuristic, mainly for instances that have few good solutions close to each other. Other references are in Stützle and Dorigo, 1999, Stützle and Holger, 2000, Talbi et al., 2001, Middendorf et al., 2002, Solimanpur et al., 2004, Randall, 2004, Ying and Liao, 2004. A novel external memory implementation is introduced, based on the use of partially complete sequences of solution components from above-average quality individuals (i.e., ants), over a number of previous iterations. Elements of such variable-size partial permutation sequences are taken from randomly selected locations of parental individuals and stored in an external memory called the partial permutation memory, Acan (2005).

Although neural networks and Markov chains are structurally different from metaheuristics, they are also based on a nature metaphor and they have been applied to the QAP, Bousonocalzon and Manning, 1995, Liang, 1996, Obuchi et al., 1996, Tsuchiya et al., 1996, Ishii and Sato, 1998, Ishii and Sato, 2001, Rossin et al., 1999, Shin and Niitsuma, 2000, Nishiyama et al., 2001, Hasegawa et al., 2002, Uwate et al., 2004.

4.3.2. The following metaheuristics are based directly on theoretical and experimental considerations

Tabu search is a local search algorithm that was introduced by Glover, 1989a, Glover, 1989b to find good quality solutions for integer programming problems. Its main feature is an updated list of the best solutions that were found in the search process. Each solution receives a priority value or an aspiration criterion. Their basic ingredients are: a tabu list, used to keep the history of the search process evolution; a mechanism that allows the acceptance or rejection of a new allocation in the neighborhood, based on the tabu list information and on their priorities; and a mechanism that allows the alternation between neighborhood diversification and intensification strategies. Adaptations for the QAP can be found in Skorin-Kapov, 1990, Skorin-Kapov, 1994, Taillard, 1991, Bland and Dawson, 1991, Rogger et al., 1992, Chakrapani and Skorin-Kapov, 1993, Misevicius, 2003a, Misevicius, 2005, Drezner, 2005b. Despite the inconvenience of depending on the size of the tabu list and the way this list is managed, the performances of those algorithms show them as being very efficient strategies for the QAP, as analyzed by Taillard, 1991, Battiti and Tecchiolli, 1994. Taillard (1995) presents a comparison between the uses of tabu search and genetic algorithm, when applied to the QAP.

Greedy randomized adaptive search procedure (GRASP) is a random and iterative technique where, at each step, an approximate solution for the problem is obtained. The final solution is the best resulting one among all iterations. At each step, the first solution is constructed through a random greedy function and the following solutions are obtained by applying on the previous solution a local search algorithm that gives a new best solution regarding to the previous one. At the end of all iterations, the resulting solution is the best generated one. It is not guaranteed that GRASP solutions do not stick to a local optimum, so it is important to apply the local search phase to try to improve them. The use of suitable data structures and careful implementations allow an efficient local search. This technique was applied to the QAP by several researchers, as follows: Li et al., 1994b, Feo and Resende, 1995, Resende et al., 1996, Fleurent and Glover, 1999, Ahuja et al., 2000, Pitsoulis et al., 2001, Rangel et al., 2000. Oliveira et al. (2004) built a GRASP using the path-relinking strategy, which looks for improvements along the paths joining pairs of good solutions. GRASP was also applied to a QAP variation: BiQAP, Mavridou et al. (1998).

Variable neighborhood search (VNS) was introduced by Mladenovic and Hansen (1997). It is based on systematic movement within a set of neighborhoods, conveniently defined. A number of change rules can be invoked. A change is applied when the exploring the current neighborhood does not produce a better solution. VNS has been applied to large combinatorial problem instances. In Taillard and Gambardella (1999), three VNS strategies are proposed for the QAP. One of them is a search over variable neighborhood, according to the basic paradigm. The other two are hybrids in combination with some of the previously described methods.

Stützle (in press) applied an iterated local search (ILS), a simple and powerful stochastic local search, wherein, to avoid stagnation behavior, using acceptance criteria that allow moves to poorer local optima enhances the algorithm. The paper proposes population-based ILS extensions.

There are several other hybrid algorithms for the QAP. In Bölte and Thonemann (1996), a combination of simulated annealing and genetic algorithm is presented. Battiti and Tecchiolli, 1994, Bland and Dawson, 1994, Chiang and Chiang, 1998, Misevicius, 2001, Misevicius, 2004a use tabu search with simulated annealing, while Talbi et al., 1998b, Hasegawa et al., 2002 use tabu search with a neural network, and Youssef et al. (2003) use tabu search, simulated annealing and fuzzy logic together. Some hybrid algorithms combine a genetic algorithm with tabu search, Fleurent and Ferland, 1994, Drezner, 2003, or with a greedy algorithm, Ahuja et al. (2000). All were proved to be more promising than the genetic algorithm alone.

More recently, there are more complex procedures in this class, such as Lim et al., 2000, Lim et al., 2002, who work with hybrid genetic algorithms based on k-gene exchange local search and Misevicius (2004b), who introduced new results for the quadratic assignment problem used an improved hybrid genetic procedure. Dunker et al. (2004) combined dynamic programming with evolutionary computation for solving a dynamic facility layout problem. Balakrishnan et al. (2003) used GATS, a hybrid algorithm that considers a possible planning horizon, which combines genetic with tabu search and is designed to obtain all global optima.

Some categories of hybrid genetic algorithms are known as mimetic algorithms or evolutionary algorithms and some works can be found in this context: Brown and Huntley, 1991, Nissen, 1994, Huntley and Brown, 1996, Merz and Freisleben, 1997, Merz and Freisleben, 1999, Merz and Freisleben, 2000, Nissen, 1997, Ostrowski and Ruoppila, 1997. Misevicius et al. (2002) presented an algorithm based on the reconstruct and improve principle. The main components of this meta-heuristics are a reconstruction (mutation) procedure and an improvement (local search) procedure. Misevicius, 2003b, Misevicius, 2003d presented a new heuristic, based on the run and recreate cause. The main components are ruin (mutation) and a recreate (improvement) procedure.

There is also a technique introduced by Goldbarg and Goldbarg (2002) that uses a variation of the genetic algorithms, known as transgenetic heuristics. In the QAP case, the results presented are comparable to others, with virtually no improvement in computational times. The use of several metaheuristics and hybrid proposals on QAP is discussed and their results are compared and analyzed in Maniezzo and Colorni, 1995, Taillard et al., 2001. Kelly et al. (1994) studied diversification strategies for the QAP; Fedjki and Duffuaa (2004) developed a work using extreme points in a search algorithm to solve the QAP. Finally, several techniques use parallel and massive computation, Roucairol, 1987, Pardalos and Crouse, 1989, Brown and Huntley, 1991, Taillard, 1991, Chakrapani and Skorin-Kapov, 1993, Laursen, 1993, Mans et al., 1995, Obuchi et al., 1996, Brüngger et al., 1997, Brüngger et al., 1998, Clausen et al., 1998, Talbi et al., 1998a, Talbi et al., 1998b, Talbi et al., 2001, Anstreicher et al., 2002, Moe, 2003. Most of these references were cited in other procedure classes.