Tabu Search and Simulated Annealing for Solving 

Large Quadratic Assignment Problem

by Mohamed Saifullah Hussin and Thomas Stützle

July 2010

to be submitted

This page contains all supplementary information that, for the sake of conciseness, was not included in the paper.

Table of Contents
  1. Paper Abstract
  2. Benchmark Instances
  3. Instance Characteristics
  4. Additional Results

Paper Abstract

Performance comparisons between algorithms have a long tradition in metaheuristic research since the very initial
research efforts.  An early example, are comparisons between Tabu Search (TS) and Simulated Annealing (SA)
algorithms for tackling the Quadratic Assignment Problem (QAP). The result of these existing comparison is, even
for only two types of algorithms, to a certain extent inconclusive. While earlier comparisons of SA and TS algorithms
focused on rather small-sized instances, here we examine specifically the dependence of the relative performance
between SA and TS in dependence of instance size. In particular, our experimental results show that the assertion
whether one algorithm is better than the other can depend strongly on the QAP instance size.

Keywords: Tabu Search, Simulated Annealing, Quadratic Assignment Problem


Benchmark Instances

Benchmark instances that were generated for this article can be downloaded below. The format of these instances:

        n
        b
        A
        B

where n is the instance size, b is the best known solution (we put a dummy value 1000). A is the distance matrix,
and B is the flow matrix. Instances are grouped as "*.tar.gz" files, where each file contains 30 instances. The files
are named using this format:

        in-sp

where i is the instance class, n is the instance size, and sp is the sparsity.


Euclidean Structured Instances
es20-0.00     es20-0.25     es20-0.67     es20-0.90     es20-0.97
es30-0.00     es30-0.25     es30-0.67     es30-0.90     es30-0.97
es40-0.00     es40-0.25     es40-0.67     es40-0.90     es40-0.97
es50-0.00     es50-0.25     es50-0.67     es50-0.90     es50-0.97
es60-0.00     es60-0.25     es60-0.67     es60-0.90     es60-0.97
es80-0.00     es80-0.25     es80-0.67     es80-0.90     es80-0.97
es100-0.00   es100-0.25   es100-0.67   es100-0.90   es100-0.97
es200-0.00   es200-0.25   es200-0.67   es200-0.90   es200-0.97
es300-0.00   es300-0.25   es300-0.67   es300-0.90   es300-0.97
es500-0.00   es500-0.25   es500-0.67   es500-0.90   es500-0.97


Random Random Instances
rr20-0.00     rr30-0.00       rr40-0.00     rr50-0.00      rr60-0.00
rr80-0.00     rr100-0.00     rr200-0.00   rr300-0.00    rr500-0.00


Grid Random Instances
gr20-0.00    gr30-0.00      gr40-0.00     gr50-0.00     gr60-0.00
gr80-0.00    gr100-0.00    gr200-0.00   gr300-0.00   gr500-0.00

Instance Characteristics

Instance         size      dd          fd            sp
ES.20.0.00     20     45.39     168.18     0.07
ES.20.0.25     20     45.89     195.29     0.27
ES.20.0.67     20     45.13     287.90     0.63
ES.20.0.90     20     45.08     556.38     0.90
ES.20.0.97     20     45.16     849.93     0.97
ES.30.0.00     30     45.78     169.25     0.06
ES.30.0.25     30     45.28     195.10     0.24
ES.30.0.67     30     46.02     293.58     0.64
ES.30.0.90     30     45.79     547.48     0.89
ES.30.0.97     30     45.95   1084.19     0.97
ES.40.0.00     40     46.05     171.98     0.05
ES.40.0.25     40     45.82     195.67     0.24
ES.40.0.67     40     45.86     296.39     0.62
ES.40.0.90     40     46.45     563.55     0.90
ES.40.0.97     40     45.96   1061.96     0.97
ES.50.0.00     50     46.31     169.39     0.04
ES.50.0.25     50     46.43     198.36     0.25
ES.50.0.67     50     46.46     304.57     0.63
ES.50.0.90     50     46.49     583.01     0.89
ES.50.0.97     50     46.73   1073.21     0.97
ES.60.0.00     60     46.46     169.68     0.04
ES.60.0.25     60     46.55     198.41     0.24
ES.60.0.67     60     46.63     299.98     0.62
ES.60.0.90     60     46.48     564.96     0.89
ES.60.0.97     60     46.43   1068.70     0.97
ES.80.0.00     80     46.61     171.25     0.04
ES.80.0.25     80     46.78     199.99     0.24
ES.80.0.67     80     46.90     299.31     0.62
ES.80.0.90     80     46.42     573.57     0.89
ES.80.0.97     80     46.60   1070.56     0.97
ES.100.0.00 100     46.63     171.96     0.03
ES.100.0.25 100     46.77     198.57     0.23
ES.100.0.67 100     46.82     300.68     0.62
ES.100.0.90 100     46.67     583.77     0.89
ES.100.0.97 100     46.86   1097.32     0.97
ES.200.0.00 200     46.88     172.01     0.03
ES.200.0.25 200     46.84     199.97     0.23
ES.200.0.67 200     47.00     302.97     0.62
ES.200.0.90 200     46.87     584.80     0.89
ES.200.0.97 200     47.05   1093.56     0.97
ES.300.0.00 300     47.02     171.86     0.03
ES.300.0.25 300     46.99     200.06     0.23
ES.300.0.67 300     46.97     303.16     0.62
ES.300.0.90 300     46.94     585.41     0.89
ES.300.0.97 300     47.02   1100.61     0.97
ES.500.0.00 500     47.01     172.09     0.03
ES.500.0.25 500     47.09     200.95     0.23
ES.500.0.67 500     47.06     303.43     0.62
ES.500.0.90 500     47.11     584.92     0.89
ES.500.0.97 500     47.04   1101.81     0.97

Table 1: Basic statistics on all ES instances from the benchmark set. Given are the distance
dominance (dd), the flow dominance (fd), and the sparsity of the flow matrix (sp).


Instance    size        dd          fd           sp
RR20         20       56.61     56.05     0.06
RR30         30       57.27     56.92     0.04
RR40         40       57.47     57.66     0.04
RR50         50       57.83     58.12     0.03
RR60         60       57.57     57.76     0.03
RR80         80       57.80     57.82     0.02
RR100     100       57.81     57.91     0.02
RR200     200       58.05     58.07     0.01
RR300     300       58.03     58.14     0.01
RR500     500       58.16     58.16     0.01

Table 2: Basic statistics on all RR instances from the benchmark set. Given are the distance
dominance (dd), the flow dominance (fd), and the sparsity of the flow matrix (sp).


Instance    size         dd          fd          sp
GR20         20       46.61     56.05     0.06
GR30         30       47.73     56.92     0.04
GR40         40       48.13     57.66     0.04
GR50         50       48.94     58.12     0.03
GR60         60       49.06     57.76     0.03
GR80         80       50.64     57.82     0.02
GR100     100       49.25     57.91     0.02
GR200     200       52.34     58.07     0.01
GR300     300       55.66     58.14     0.01
GR500     500       50.16     58.16     0.01

Table 3: Basic statistics on all GR instances from the benchmark set. Given are the distance
dominance (dd), the flow dominance (fd), and the sparsity of the flow matrix (sp).

Additional Results

Instance    Sparsity     RoTS     RTS     SAC     SAR
20             0.00           0.00        0.00     0.04      0.46
20             0.25           0.00        0.00     0.15      0.79
20             0.67           0.00        0.00     0.09      3.01
20             0.90           0.00        0.07     4.30    17.58
20             0.97           0.02        0.00     2.99    38.62
30             0.00           0.00        0.03     0.12      0.06
30             0.25           0.00        0.05     0.36      0.10
30             0.67           0.00        0.10     0.60      1.15
30             0.90           0.00        0.64     3.93      8.46
30             0.97           0.34        0.00     18.33  37.62
40             0.00           0.00        0.12     0.38      0.08
40             0.25           0.00        0.16     0.22      0.05
40             0.67           0.00        0.13     0.77      0.20
40             0.90           0.00        1.00     3.33      2.43
40             0.97           0.72        0.00   14.99      2.09
50             0.00           0.00        0.19     0.21      0.04
50             0.25           0.00        0.17     0.25      0.03
50             0.67           0.08        0.42     0.52      0.00
50             0.90           1.81        3.84     3.78      0.00
50             0.97           0.78        0.00     8.12      6.84
60             0.00           0.01        0.15     0.15      0.00
60             0.25           0.00        0.19     0.28      0.01
60             0.67           0.26        0.36     0.54      0.00
60             0.90           1.09        4.69     0.85      0.00
60             0.97           2.73        1.42     5.66      0.00
80             0.00           0.00        0.09     0.10      0.04
80             0.25           0.00        0.15     0.09      0.00
80             0.67           0.19        0.95     0.59      0.00
80             0.90           1.14        5.07     1.59      0.00
80             0.97           7.48        8.94     7.48      0.00
100           0.00           0.00        0.07     0.04      0.01
100           0.25           0.00        0.17     0.13      0.01
100           0.67           0.19        0.95     0.59      0.00
100           0.90           1.13        4.39     1.61      0.00
100           0.97           8.64      10.05     2.36      0.00
200           0.00           0.00        0.13     0.04      0.02
200           0.25           0.00        0.13     0.03      0.00
200           0.67           0.12        0.63     0.60      0.00
200           0.90           0.48        7.30     2.16      0.00
200           0.97         10.52      15.00     0.00      3.13
300           0.00           1.52        0.00     1.58      1.53
300           0.25           0.14        0.00     0.28      0.14
300           0.67           0.16        1.19     0.84      0.00
300           0.90           0.65      13.92     4.12      0.00
300           0.97           3.00        3.44     2.45      0.00
500           0.00           4.43        0.00     4.47      4.45
500           0.25           2.24        0.00     2.27      2.23
500           0.67           0.53        0.00     1.25      0.41
500           0.90           1.18        9.63     6.47      0.00
500           0.97           9.49      14.64     6.52      0.00

Table 4: Comparison of RoTS, RTS, SAC, and SAR on instance size 20, 30, 40, 50, 60, 80, 100, 200, 300, and 500.
Entries are distance from best found across 30 instances at 10000n. The lowest average values are printed in bold.


Instance     RoTS     RTS     SAC     SAR
RR20         0.00       0.00     0.08      0.33
RR30         0.04       0.00     1.21      1.00
RR40         0.14       0.00     1.31      1.27
RR50         0.17       0.00     1.46      1.36
RR60         0.59       0.00     1.59      1.69
RR80         0.32       0.00     1.06      1.39
RR100       0.45       0.00     0.82      1.47
RR200       0.49       0.00     0.48      0.42
RR300       0.15       0.00     0.23      1.01
RR500       0.06       0.00     0.15      0.82

Table 5: Comparison of RoTS, RTS, SAC, and SAR on RR instances size 20, 30, 40, 50, 60, 80, 100, 200, 300, and 500.
Entries are distance from best found across 30 instances at 10000n. Statistically significant worse performance is indicated
in italics font, while the best solutions are in bold font.


Instance         RoTS     RTS     SAC     SAR
GR20            0.00        0.00     0.00      0.00
GR30            0.00        0.00     0.02      0.01
GR40            0.02        0.00     0.09      0.05
GR50            0.01        0.00     0.06      0.03
GR60            0.01        0.00     0.16      0.03
GR80            0.00        0.00     0.02      0.02
GR100          0.00        0.00     0.01      0.03
GR200          0.00        0.03     0.01      0.02
GR300          0.55        0.00     0.56      0.56
GR500          1.41        0.00     1.40      1.41
 
Table 6: Comparison of RoTS, RTS, SAC, and SAR on GR instances size 20, 30, 40, 50, 60, 80, 100, 200, 300, and 500.
Entries are distance from best found across 30 instances at 10000n. Statistically significant worse performance is indicated
in italics font, while the best solutions are in bold font.