# A Simulated Annealing Algorithm for the Generalized Quadratic Assignment Problem
## 2 Mathematical Models
### Mathematical Programming Models  
The GQAP is the problem of assigning a set of \(M\) facilities to a set of \(N\) locations, where \(M>N\), such that the sum of the assignment and transportation costs is minimized. The assumptions of the GQAP are as follows.  
1. One or more facilities may be assigned to each location such that the capacities of the locations are not exceeded.
2. The objective is to minimize the sum of the assignment and the transportation costs. The assignment costs consist of the cost of installing each facility (e.g., machine) to each location, and the transportation costs consist of the costs of moving materials processed on the machines between the machines.
3. The input data are deterministic and known. That is, the number of units of materials transported between facilities \(i\) and \(j\) (\(f_{ij}\)), the distances between locations \(k\) and \(l\) (\(d_{kl}\)), the space requirement of each facility \(i\) (\(r_{i}\)), the capacity of each location \(k\) (\(C_{k}\)), the costs of assigning or installing facility \(i\) to location \(k\) (\(a_{ik}\)), and the unit cost per distance unit of transporting materials between each pair of facility \(i\) at location \(k\) and facility \(j\) at location \(l\) (\(c_{ikl}\)) are deterministic and known.  
The mathematical programming formulation of the GQAP is given below and is an adaptation of the nonlinear programming model presented by [PERSON] and [PERSON] [2], but first the decision variables are defined as follows.  
\[x_{ik}=\left\{\begin{array}{c}1,\text{ if facility }i\text{ is assigned to location }k\\ 0,\text{ otherwise}\end{array}\right. \tag{1}\]  
\[\text{Minimize }z=\sum_{i=1}^{M}\sum_{k=1}^{N}a_{ik}x_{ik}+\sum_{i=1}^{M} \sum_{\begin{subarray}{c}j=1\\ j\
eq i\end{subarray}}^{M}\sum_{k=1}^{N}\sum_{l=1}^{N}c_{ijkl}f_{ij}d_{kl}x_{ ik}x_{jl}\\ l\
eq k\end{array}\]Subject to  
\[\sum_{k=1}^{N}x_{ik}=1\ \forall i \tag{2}\]  
\[\sum_{i=1}^{M}r_{i}x_{ik}\leq C_{k}\forall k \tag{3}\]  
\[x_{ik}=0\ or\ 1\ \forall i,\ k \tag{4}\]  
Objective function (1) minimizes the sum of the assignment and transportation costs. Constraints (2) ensures that each facility is assigned to exactly one location. Constraints (3) are used to ensure that the capacity of each location is not exceeded. Last, the restrictions on the variables are given in Constraint (4). Since the second term in Objective function (1), which is used to obtain total transportation cost, is nonlinear, the model above is a nonlinear binary integer programming model. To obtain the global optimal solution for the GQAP, the model is linearized by using a simple standard transformation by substituting \(w_{ijkl}\) for the term \(x_{ik}x_{jl}\). As a result, this gives the linearized objective function and the additional constraints.  
\[\text{Minimize}=\sum_{i=1}^{M}\sum_{k=1}^{N}a_{ik}x_{ik}+\sum_{i=1}^{M}\sum_{ j=1}^{M}\sum_{k=1}^{N}\sum_{l=1}^{N}c_{ijkl}f_{jl}a_{kl}w_{ijkl} \tag{5}\]  
\[w_{ijkl}\geq x_{ik}+x_{jl}-1\ \forall i,j\
eq i,\ k,\ l\
eq k \tag{6}\]  
\[w_{ijkl}\geq 0\ \forall i,j\
eq i,\ k,\ l\
eq k \tag{7}\]  
Therefore, the linearized mathematical model for the GQAP consists of Objective function (5) subject to Constraints (2)-(4) as well as Constraints (6) and (7). This yields a mixed-integer linear programming (MILP) model for the GQAP. Since the MILP model can only be used to solve small-size GQAP instances in reasonable computational time, a heuristic algorithm is needed to solve large-size GQAP instances, which will be discussed later. Next, a combinatorial optimization problem (COP) model is presented for the GQAP.