# A Simulated Annealing Algorithm for the Generalized Quadratic Assignment Problem
## 4 Computational Results  
A set of test problems taken from [PERSON] et al. [9] is used to evaluate the performance of the proposed SA algorithm, given in Algorithm 2, using the construction algorithm presented in Algorithm 1 in Section 3. The authors labeled the GQAP instances using the notation \(M\)-\(N\)-\(U\) where \(M=\) number of facilities, \(N=\) number of locations, and \(U=\) location utilization as defined earlier. The set of test problems contain twenty-one GQAP instanceswith 20, 30, 35, 40, and 50 facilities (i.e., \(M\) = 20, 30, 35, 40, and 50) and with locations ranging from 6 to 20 (i.e., \(N\) = 6, 7, 8, 9, 10, 15, and 20). Additionally, the location utilizations, as discussed in Section 3.1, for these instances ranges between 35% and 95% (i.e., \(U\) = 35, 55, 65, 75, and 95). In all experiments, a PC (equipped with Microsoft Windows 10, an Intel Core processor i7 with a CPU speed of 2.90 GHz and 16 GB of RAM) was used to solve the test problems, and the proposed construction algorithm and SA heuristic were coded using Matlab. First, an attempt was made to solve the smaller-size test problems (e.g., 30-07-75 and 20-15-35) using the MILP model presented in Section 2.1, which consists of Objective function (5) subject to Constraints (2)-(4) as well as Constraints (6) and (7). Using the MILP model and the CPLEX 11.0 solver, the optimal solutions were not obtained for any of the test problems. More specifically, low quality, feasible solutions were obtained after running the problems for over four hours, since CPLEX uses a type of branch-and-bound algorithm which uses and stores a search tree. As the search continues over long periods of time, the search tree grows and consumes a lot of the computer's RAM. Once it uses up most of the computer's RAM, the CPLEX solver shutdowns. However, there are exact algorithms available in the literature that can solve small-size problems. For example, [PERSON] et al. [6] proposed two exact algorithms for the GQAP which uses a branch-and-bound scheme with a Lagrangean relaxation procedure over a reformulation-linearization technique. The authors were able to solve instances with up to 35 facilities in up to a few days of running time. As a result, heuristic algorithms are needed to solve medium- to large-size GQAP instances. The performance of the proposed SA heuristic for all the test problems taken from [PERSON] et al. [9] is given below in Table 2. The costs of the initial solutions obtained from the construction algorithm (Algorithm 1) are given in column 2. Since each instance was solved 50 times, the maximum (Max), average (Avg), and minimum (Min) total costs of the best solutions found are presented in columns 3-5, and the computational times (in seconds) are given in columns 7-9. The best-known solution (BKS) available in the literature for each problem instance is shown in column 6. It is important to note that since many of the state-of-the-art algorithms for the GQAP terminate their search once the BKS is found, this stopping criterion is utilized for the proposed SA algorithm. However, if the BKS is not obtained, then the proposed stopping criterion available in Algorithm 2 is used to terminate the search. Notice in Table 2 that the proposed SA algorithm obtained the BKS for all instances. However, the tightly constrained instance 30-20-95 required more computational time than all the other instances. As discussed in Section 1, several heuristic algorithms are available in the literature for solving the GQAP. The state-of-the-art algorithms are the MA presented by [PERSON] et al. [9], GRASP with path-relinking (GRASP-PR) algorithms presented by [PERSON] et al. [11], the TS algorithm presented by [PERSON] and [PERSON] [12], and the parallel memetic iterated TS (PMITS) heuristic algorithm presented by [PERSON] et al. [14]. Although the last algorithm uses more computing power by using parallel computing (a CPU with 40 cores), the proposed SA algorithm is competitive as can be seen in Table 3 below. Note, [PERSON] et al.