# QAPLIB - A Quadratic Assignment Problem Library

## Problem Instances and Solutions

### Compressed Data and Solutions

Data: qapdata.tar.gz (453187 KB). Solutions: qapsoln.tar.gz (9836 KB).
("gunzip qapxxxx.tar.gz" and "tar xf qapxxxx.tar". This should result in 136 instances and 111 solutions.)

### Description

The instances are listed in alphabetical order by the names of their authors. We shortly characterize the examples by indicating their generation. All the instances in the current version are pure quadratic. If not stated otherwise the examples are symmetric.

The format of the problem data is

n
A
B
where n is the size of the instance, and A and B are either flow or distance matrix. This corresponds to a QAP of the form
```            ---  ---
\    \
min   /    /    a    b
p    ---  ---   ij   p(i),p(j)
i    j
```
where p is a permutation.

We quote the filename under which it is stored in the library and report the size of the problem. Then the objective function value of the best known feasible solution is given. In parentheses we indicate whether this solution is optimal or derived by a heuristic. The heuristics that are used are

If available we give a link to a solution for the instances. The format of these files is
```       n    sol
p
```
where n gives the size of the instance, sol is the objective function value and p a corresponding permutation, i.e.
```             ---  ---
\    \
sol =  /    /    a    b         .
---  ---   ij   p(i),p(j)
i    j
```

For optimal solutions we enclose the optimal permutation while for nonoptimal solutions lower bounds are given. We also give explicit reference who solved hard instances of size n>15 first. The lower bounds given in the tables are

• the Gilmore-Lawler bound: (GLB) [Gilmore:62,Lawler:63],
• the elimination bound: (ELI) [HaReWo:92],
• an interior point based linear programming bound: (IPLP) [ReRaDr:94]
• a triangle decomposition bound: (TDB) [KaRe:95a],
• a semidefinite programming bound: (SDP) [ZhKaReWo:96],
• a bound based on a dual procedure: (DP) [HaGr:95],
• a bound based on a cutting plane approach: (CUT) [Kaibel:97], and
• a dual framework based bound: (DFB) [KaCeClEs:98].
When lower bounds are included we also give the relative gap between best feasible soltion and best known lower bound in percent, i.e. gap = (solution - bound)/(solution)*100 %.

### R.E. Burkard and J. Offermann [BuOf:77]

The data of the first matrix correspond to the typing-time of an average stenotypist, while the second matrix describes the frequency of pairs of letters in different languages taken over 100,000 pairs for examples a-f and over 187,778 pairs for examples g-h. (Note that the solutions are not scaled for a flow matrix of 100,000 pairs anymore.) One also distinguishes between two types of typewriter keyboards. The instances are asymmetric.

```   name    n     feas. solution         bound         gap
---------------------------------------------------------
*  Bur26a  26    5426670 (OPT)    (26 15 11 7 4 12 13 2 6 18 1 5 9 21 8 14 3 20 19 25 17 10 16 24 23 22)
*  Bur26b  26    3817852 (GRASP)    3753198 (DFB)     1.69 %
*  Bur26c  26    5426795 (GRASP)    5361204 (DFB)     1.21 %
*  Bur26d  26    3821225 (GRASP)    3758687 (DFB)     1.64 %
*  Bur26e  26    5386879 (GRASP)    5334780 (DFB)     0.97 %
*  Bur26f  26    3782044 (GRASP)    3733941 (DFB)     1.27 %
*  Bur26g  26   10117172 (GRASP)   10055637 (DFB)     0.61 %
*  Bur26h  26    7098658 (GRASP)    7045690 (DFB)     0.75 %
```

### N. Christofides and E. Benavent [ChBe:89]

One matrix is the adjacency matrix of a weighted tree the other that of a complete graph.

```   name    n      solution      permutation
----------------------------------------------------------------------------------------------------
Chr12a  12     9552 (OPT)    (7,5,12,2,1,3,9,11,10,6,8,4)
Chr12b  12     9742 (OPT)    (5,7,1,10,11,3,4,2,9,6,12,8)
Chr12c  12    11156 (OPT)    (7,5,1,3,10,4,8,6,9,11,2,12)
Chr15a  15     9896 (OPT)    (5,10,8,13,12,11,14,2,4,6,7,15,3,1,9)
Chr15b  15     7990 (OPT)    (4,13,15,1,9,2,5,12,6,14,7,3,10,11,8)
Chr15c  15     9504 (OPT)    (13,2,5,7,8,1,14,6,4,3,15,9,12,11,10)
Chr18a  18    11098 (OPT)    (3,13,6,4,18,12,10,5,1,11,8,7,17,14,9,16,15,2)
Chr18b  18     1534 (OPT)    (1,2,4,3,5,6,8,9,7,12,10,11,13,14,16,15,17,18)
Chr20a  20     2192 (OPT)    (3,20,7,18,9,12,19,4,10,11,1,6,15,8,2,5,14,16,13,17)
Chr20b  20     2298 (OPT)    (20,3,9,7,1,12,16,6,8,14,10,4,5,13,17,2,18,11,19,15)
Chr20c  20    14142 (OPT)    (12,6,9,2,10,11,3,4,15,18,7,13,16,5,14,17,19,1,8,20)
Chr22a  22     6156 (OPT)    (15,2,21,8,16,1,7,18,14,13,5,17,6,11,3,4,20,19,9,22,10,12)
Chr22b  22     6194 (OPT)    (10,19,3,1,20,2,6,4,7,8,17,12,11,15,21,13,9,5,22,14,18,16)
Chr25a  25     3796 (OPT)    (25,12,5,3,18,4,16,8,20,10,14,6,15,23,24,19,13,1,21,11,17,2,22,7,9)
```

### A.N. Elshafei [Elshafei:77]

The data describe the distances of 19 different facilities of a hospital and the flow of patients between those locations. The optimal solution was first found by [Mautor:92].

```   name    n     solution        permutation
-------------------------------------------------------------------------------
Els19   19   17212548 (OPT)   (9,10,7,18,14,19,13,17,6,11,4,5,12,8,15,16,1,2,3)
```

### B. Eschermann and H.J. Wunderlich [EsWu:90]

These examples stem from an application in computer science, from the testing of self-testable sequential circuits. The amount of additional hardware for the testing should be minimized. The optimal solutions are due to [ClPe:94] (n=16) and [BrClMaPe:96] (n=32).
```   name    n    feas.sol.     permutation/bound      gap
------------------------------------------------------------------------------
Esc16a  16    68 (OPT)     (2,14,10,16,5,3,7,8,4,6,12,11,15,13,9,1)
Esc16b  16   292 (OPT)     (6,3,7,5,13,1,15,2,4,11,9,14,10,12,8,16)
Esc16c  16   160 (OPT)     (11,14,10,16,12,8,9,3,13,6,5,7,15,2,1,4)
Esc16d  16    16 (OPT)     (14,2,12,5,6,16,8,10,3,9,13,7,11,15,4,1)
Esc16e  16    28 (OPT)     (16,7,8,15,9,12,14,10,11,2,6,5,13,4,3,1)
Esc16f  16     0 (OPT)     (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16)
Esc16g  16    26 (OPT)     (8,11,9,12,15,16,14,10,7,6,2,5,13,4,3,1)
Esc16h  16   996 (OPT)     (13,9,10,15,3,11,4,16,12,7,8,5,6,2,1,14)
Esc16i  16    14 (OPT)     (13,9,11,3,7,5,6,2,1,15,4,14,12,10,8,16)
Esc16j  16     8 (OPT)     (8,3,16,14,2,12,10,6,9,5,13,11,4,7,15,1)
*  Esc32a  32   130 (Ro-TS)     88 (CUT)            32.31 %
*  Esc32b  32   168 (Ro-TS)    100 (CUT)            40.48 %
*  Esc32c  32   642 (SIM-1)    506 (CUT)            21.18 %
*  Esc32d  32   200 (Ro-TS)    152 (CUT)            24.00 %
Esc32e  32     2 (OPT)     (1,2,5,6,8,16,13,19,9,32,7,22,24,20,4,12,3,
17,29,21,11,25,27,18,30,31,23,28,14,15,26,10)
Esc32f  32     2 (OPT)     (1,2,5,6,8,16,10,7,9,28,30,4,32,31,22,12,3,
17,26,18,13,25,29,21,23,24,19,20,14,15,27,11)
Esc32g  32     6 (OPT)     (14,15,16,12,11,26,30,10,25,8,29,22,31,28,
13,1,19,9,17,32,24,18,4,2,20,5,21,3,7,6,23,27)
*  Esc32h  32   438 (Ro-TS)    352 (CUT)            21.00 %
Esc64a  64   116 (SIM-1)     47 (GLB)            59.49 %
Esc128 128    64 (GRASP)      2 (GLB)            96.86 %
```

### S.W. Hadley, F. Rendl and H. Wolkowicz [HaReWo:92]

The first matrix represents Manhattan distances of a connected cellular complex in the plane while the entries in the flow matrix are drawn uniformly from the interval [1,n]. The proof of optimality of the solution for n=16 is due to [HaGrHa:96], for n=18 and n=20 due to [BrClMaPe:96]

```   name   n    solution      permutation
------------------------------------------------------------------------
```

### J. Krarup and P.M. Pruzan [KrPr:78]

The instances contain real world data and were used to plan the Klinikum Regensburg in Germany.
```   name    n    feas. solution       permutation/bound        gap
---------------------------------------------------------
*  Kra30a  30   88900 (OPT)     (26,24,23,16,20,19,6,10,11,2,22,18,7,30,15,
21,25,29,12,9,5,17,1,8,13,28,14,3,4,27)
*   Kra30b  30   91420 (OPT)    (23,26,19,25,20,22,11,8,9,14,27,30,12,6,28,
24,21,18,1,7,10,29,13,5,2,17,3,15,4,16)
*   Kra32  32   88900 (OPT)    (31,23,18,21,22,19,10,11,15,9,30,29,14,12,17,26,
27,28,1,7,6,25,5,3,8,24,32,13,2,20,4,16)
```

### Y. Li and P.M. Pardalos [LiPa:92]

These instances come from problem generators described in [LiPa:92]. The generators provide asymmetric instances with known optimal solutions.

```   name     n      solution
---------------------------
Lipa20a  20      3683 (OPT)
Lipa20b  20     27076 (OPT)
Lipa30a  30     13178 (OPT)
Lipa30b  30    151426 (OPT)
Lipa40a  40     31538 (OPT)
Lipa40b  40    476581 (OPT)
Lipa50a  50     62093 (OPT)
Lipa50b  50   1210244 (OPT)
Lipa60a  60    107218 (OPT)
Lipa60b  60   2520135 (OPT)
Lipa70a  70    169755 (OPT)
Lipa70b  70   4603200 (OPT)
Lipa80a  80    253195 (OPT)
Lipa80b  80   7763962 (OPT)
Lipa90a  90    360630 (OPT)
Lipa90b  90  12490441 (OPT)
```

### C.E. Nugent, T.E. Vollmann and J. Ruml [NuVoRu:68]

The following problem instances are probably the most used. The distance matrix contains Manhattan distances of rectangular grids. The instances of size n = {14,16,17,18,21,22,24,25} were constructed out of the larger instances by deleting certain rows and columns, see Clausen and Perregaard [ClPe:94]. The optimal solutions are also due to [ClPe:94]. For Nug21 and Nug22 optimality was proved by [BrClMaPe:96], for Nug24 by [CEKPT:96]. The instances of size n =27 and n =28 were constructed out of the instance of size n =30 by deleting the three or two last facilities, respectively, and were solved by Anstreicher, Brixius, Goux, and Linderoth. Aslo Nug 30 was solved by these authors. The solution was found by applying a branch and bound algorithm, see Anstreicher and Brixius [AnBr2:00]. The involved bound was based on convex quadratic programming, see Anstreicher and Brixius [AnBr1:00].
```   name    n    feas.sol.     permutation/bound      gap
------------------------------------------------------------------------------------------
Nug12   12    578 (OPT)    (12,7,9,3,4,8,11,1,5,6,10,2)
Nug14   14   1014 (OPT)    (9,8,13,2,1,11,7,14,3,4,12,5,6,10)
Nug15   15   1150 (OPT)    (1,2,13,8,9,4,3,14,7,11,10,15,6,5,12)
Nug16a  16   1610 (OPT)    (9,14,2,15,16,3,10,12,8,11,6,5,7,1,4,13)
Nug16b  16   1240 (OPT)    (16,12,13,8,4,2,9,11,15,10,7,3,14,6,1,5)
Nug17   17   1732 (OPT)    (16,15,2,14,9,11,8,12,10,3,4,1,7,6,13,17,5)
Nug18   18   1930 (OPT)    (10,3,14,2,18,6,7,12,15,4,5,1,11,8,17,13,9,16)
Nug20   20   2570 (OPT)    (18,14,10,3,9,4,2,12,11,16,19,15,20,8,13,17,5,7,1,6)
Nug21   21   2438 (OPT)    (4,21,3,9,13,2,5,14,18,11,16,10,6,15,20,19,8,7,1,12,17)
Nug22   22   3596 (OPT)    (2,21,9,10,7,3,1,19,8,20,17,5,13,6,12,16,11,22,18,14,15)
Nug24   24   3488 (OPT)    (17,8,11,23,4,20,15,19,22,18,3,14,1,10,7,9,16,21,24,12,6,13,5,2)
Nug25   25   3744 (OPT)    (5,11,20,15,22,2,25,8,9,1,18,16,3,6,19,24,21,14,7,10,17,12,4,23,13)
*  Nug27   27   5234 (OPT)    (23,18,3,1,27,17,5,12,7,15,4,26,8,19,20,2,24,21,14,10,9,13,22,25,6,16,11)
*  Nug28   28   5166 (OPT)    (18,21,9,1,28,20,11,3,13,12,10,19,14,22,15,2,25,16,4,23,7,17,24,26,5,27,8,6)
*  Nug30   30   6124 (OPT)    (14,5,28,24,1,3,16,15,10,9,21,2,4,29,25,22,13,26,17,30,6,20,19,8,18,7,27,12,11,23)
```

### C. Roucairol [Roucairol:87]

The entries of the matrices are chosen from the interval [1,100].

```   name   n     feas.sol.       permutation
---------------------------------------------------------------------------
Rou12  12   235528 (OPT)     (6,5,11,9,2,8,3,1,12,7,4,10)
Rou15  15   354210 (OPT)     (12,6,8,13,5,3,15,2,7,1,9,10,4,14,11)
Rou20  20   725522 (OPT)     (1,19,2,14,10,16,11,20,9,5,7,4,8,18,15,3,12,17,13,6)
```

### M. Scriabin and R.C. Vergin [ScVe:75]

The distances of these problems are rectangular. The optimal solution for the instanze of size n=20 was found by [Mautor:92].

```   name   n      solution      permutation
-------------------------------------------------------------------------------
Scr12  12    31410 (OPT)   (8,6,3,2,10,1,5,9,4,7,12,11)
Scr15  15    51140 (OPT)   (15,7,11,8,1,4,3,2,12,6,13,5,14,10,9)
Scr20  20   110030 (OPT)   (20,7,12,6,4,8,3,2,14,11,18,9,19,15,16,17,13,5,10,1)
```

### J. Skorin-Kapov [Skorin:90]

The distances of these problems are rectangular and the entries in flow matrices are pseudorandom numbers.

```   name      n       feas.sol.         bound        gap
-------------------------------------------------------
Sko42     42    15812 (Ro-TS)     14934 (TDB)    5.56 %
Sko49     49    23386 (Ro-TS)     22004 (TDB)    5.91 %
Sko56     56    34458 (Ro-TS)     32610 (TDB)    5.37 %
Sko64     64    48498 (Ro-TS)     45736 (TDB)    5.70 %
Sko72     72    66256 (Ro-TS)     62691 (TDB)    5.38 %
Sko81     81    90998 (GEN)       86072 (TDB)    5.41 %
Sko90     90   115534 (Ro-TS)    108493 (TDB)    6.10 %
Sko100a  100   152002 (GEN)      142668 (TDB)    6.14 %
Sko100b  100   153890 (GEN)      143872 (TDB)    6.51 %
Sko100c  100   147862 (GEN)      139402 (TDB)    5.73 %
Sko100d  100   149576 (GEN)      139898 (TDB)    6.47 %
Sko100e  100   149150 (GEN)      140105 (TDB)    6.07 %
Sko100f  100   149036 (GEN)      139452 (TDB)    6.43 %
```

### L. Steinberg [Steinberg:61]

The three instances model the backboard wiring problem. The distances in the first one are Manhattan, in the second squared Euclidean, and in the third one Euclidean distances (multiplied by 1000).

```   name    n       feas.sol.         bound          gap
-------------------------------------------------------
*  Ste36a  36    9526    (OPT)
(12,19,30,11,2,3,22,20,10,21,5,4,13,15,31,32,28,29,24,14,17,18,16,9,8,7,6,23,33,34,25,35,27,26,1,36)
*   Ste36b  36
15852    (OPT)    8653
(35,31,30,29,28,1,15,9,16,33,34,32,19,20,7,10,18,17,26,25,23,14,12,13,4,8,2,24,22,21,27,11,6,5,3,36)
*  Ste36c  36    8239.11 (OPT)
(3,19,29,21,30,31,13,20,2,12,32,23,22,24,4,1,10,11,15,14,26,27,25,36,35,34,33,5,6,7,8,16,18,17,28,9)
```

### E.D. Taillard [Taillard:91,Taillard:94]

The instances Taixxa are uniformly generated and were proposed in [Taillard:91]. The other problems were introduced in [Taillard:94]. Problems Taixxb are asymmetric and randomly generated. Instances Taixxc occur in the generation of grey patterns. The optimality of the solutions for Tai17a and Tai20a was proved by [BrClMaPe:96], while the method of [HaGrHa:96] proved optimality of Tai20b. Giovannetti [Giovannetti:97] showed the optimality of Tai25b.

```   name      n         feas.sol.           permutation/bound      gap
----------------------------------------------------------------------------------
Tai12a    12       224416 (OPT)     (8,1,6,2,11,10,3,5,9,7,12,4)
Tai12b    12     39464925 (OPT)     (9,4,6,3,11,7,12,2,8,10,1,5)
Tai15a    15       388214 (OPT)     (5,10,4,13,2,9,1,11,12,14,7,15,3,8,6)
Tai15b    15     51765268 (OPT)     (1,9,4,6,8,15,7,11,3,5,2,14,13,12,10)
Tai17a    17       491812 (OPT)     (12,2,6,7,4,8,14,5,11,3,16,13,17,9,1,10,15)
Tai20a    20       703482 (OPT)     (10,9,12,20,19,3,14,6,17,11,5,7,15,16,18,2,4,8,13,1)
*  Tai20b    20    122455319 (OPT)     (8,16,14,17,4,11,3,19,7,9,1,15,6,13,10,2,5,20,18,12)
*  Tai25a    25      1167256 (Ro-TS)     1016213 (DFB)           12.94 %
*  Tai25b    25    344355646 (OPT)     (4,15,10,9,13,5,25,19,7,3,17,6,18,20,16,2,22,23,8,11,21,24,14,12,1)
Tai30a    30      1818146 (Ro-TS)     1529135 (SDP)           15.90 %
Tai30b    30    637117113 (Ro-TS)    40947945 (GLB)           93.58 %
Tai35a    35      2422002 (Ro-TS)     1951207 (GLB)           19.44 %
Tai35b    35    283315445 (Ro-TS)    32611838 (GLB)           88.49 %
Tai40a    40      3139370 (Re-TS)     2492850 (GLB)           20.60 %
Tai40b    40    637250948 (Ro-TS)    46143753 (GLB)           92.77 %
Tai50a    50      4941410 (GEN)       3854359 (GLB)           22.00 %
Tai50b    50    458821517 (Ro-TS)    40296004 (GLB)           91.23 %
Tai60a    60      7208572 (Ro-TS)     5555095 (GLB)           22.94 %
Tai60b    60    608215054 (Ro-TS)    50113782 (GLB)           91.77 %
Tai64c    64      1855928 (Ro-TS)      896398 (ELI)           51.71 %
Tai80a    80     13557864 (Ro-TS)    10329674 (GLB)           23.82 %
Tai80b    80    818415043 (Ro-TS)    89169828 (GLB)           89.11 %
Tai100a  100     21125314 (Re-TS)    15824355 (GLB)           25.10 %
Tai100b  100   1185996137 (Ro-TS)   174687926 (GLB)           86.28 %
*  Tai150b  150    498896643 (GEN-3)    63007151 (GLB)           87.37 %
*  Tai256c  256     44759294 (ANT)      41291996 (ELI)            7.75 %
```

### U.W. Thonemann and A. Bölte [ThBo:94]

The distances of these instances are rectangular.

```   name     n       feas.sol.         bound         gap
-------------------------------------------------------
*   Tho30    30    149936 (OPT)  (8,6,20,17,19,12,29,15,1,2,30,11,13,28,23,
27,16,22,10,21,25,24,26,18,3,14,7,5,9,4)
Tho40    40    240516 (SIM-2)    214218 (TDB)   10.94 %
*  Tho150  150   8133398 (SIM-3)    7620628 (TDB)    6.30 %
```

### M.R. Wilhelm and T.L. Ward [WiWa:87]

The distances of these problems are rectangular.

```   name     n       feas.sol.         bound         gap
-------------------------------------------------------
Wil50    50    48816 (SIM-2)    47098 (TDB)      3.52 %
Wil100  100   273038 (GEN)     263909 (TDB)      3.35 %

```

GO BACK TO MAIN PAGE OF QAPLIB