# A Simulated Annealing Algorithm for the Generalized Quadratic Assignment Problem
## 3 Methods
### Construction Algorithm  
The flowchart and the pseudo-code for the construction algorithm (CA) are presented below for the GQAP in Figure 2 and Algorithm 1, respectively. This algorithm uses only the capacities of the locations (\(C_{k}\)) and the space requirement for each facility (\(r_{i}\)) as input data as well as the solution representation defined in Equation (8) to construct a feasible solution \(S\). In other words, the proposed CA does not attempt to construct solutions with respect to minimizing total cost but to construct feasible solutions for all situations, including tightly constrained GQAPs which may occur often in the real world. A GQAP instance is defined as tightly constrained when location utilization is high (i.e., more than 70%). In contrast, if the location utilization is low, say under 40%, the GQAP instance is defined as loosely constrained. Consider the illustrative example given above in Table 1. Since the facilities assigned to locations utilizes 81.8% (i.e., (90/110) \(\times\) 100%) of total location capacity, this problem is considered to be tightly constrained. Again, in the development of CA, the goal was to ensure that initial feasible solutions are constructed for all types of GQAPs especially for tightly constrained problems. To achieve this goal, CA attempts to assign facilities requiring more space to the first location. However, if there is not enough space at the location, the next largest facility is considered and facilities are assigned until no other facility can be assigned to the location. Then, the largest facility that had not been assigned yet is assigned to the second location. This process is continued until all facilities are assigned to locations. The details of the algorithm are given below, but first, the definitions of the CA algorithm parameters are provided. The additional notation used in CA are as follows. _Cap(\(k\))_ = the remaining capacity of location \(k\). _SetOfFac_ = vector of facilities sorted in descending order based on \(r_{i}\). _SetOfFac(\(p\))_ = facility in the \(p\)-position of the vector _SetOfFac_. _s(\(i\))_ = location assigned to facility \(i\). _Remove(\(i\))_ = function used to remove \(i\) from the vector _SetOfFac_. Figure 1: Optimal Assignment for Small GQAP Illustrative Example. Figure 2: Flowchart of the construction algorithm. To illustrate CA in Algorithm 1 for the illustrative example presented in Table 1, the input arguments are initialized (line 1) where \(r_{i}\) = {20, 10, 30, 10, 20} and \(C_{k}\) = {30, 30, 50}. Next, the vector _SetOfFac_ = {3, 1, 5, 2, 4} is generated (line 2). As stated previously, the facility which requires the most space (i.e., \(r_{3}\) = 30) is put in first. After putting facility 3 in the first position, notice the next largest space requirement is 20 for facilities 1 and 5. Priority is given to the lower number facility; therefore, facilities 1 and 5 are put in the second and third positions, respectively. Then, facilities 2 and 4. Once the vector _SetOfFac_ is obtained, facilities are assigned to locations based on their order in this set (lines 3-18). More specifically, first facility \(i\) in the first position (\(p\) = 1) in _SetOfFac_ is assigned to location \(k\) (\(k\) = 1), \(s(3)\) = 1, since there is enough capacity (lines 3-10). Then, the capacity of the location is updated, \(Cap(1)\) = 30-30 = (line 11), and facility 3 is removed from the set where _SetOfFac_ = {1, 5, 2, 4} (line 12). Since \(Cap(1)\) = \(0<10=r_{4}\) (line 16), the next location, \(k\) = 2, is considered (line 17). At the next iteration (iteration 2), the first facility \(i\) in the first position (\(p\) = 1) in _SetOfFac_ is assigned to location 2, \(s(1)\) = 2, since there is enough capacity (lines 5-10). The capacity for location 2 is updated, \(Cap(2)\) = 30 \(-\) 20 = 10 (line 11) and facility 1 is removed where _SetOfFac_ = {5, 2, 4} (line 12).