# QAPLIB-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

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 (OPT)    (17 11 26 7 4 14 6 22 23 18 5 9 1 21 8 12 3 19 20 15 10 25 24 16 13 2)

*  Bur26c  26    5426795 (OPT)    (12 3 2 13 16 25 11 15 10 9 18 19 8 20 4 21 1 5 14 24 22 6 23 7 26 17)

*  Bur26d  26    3821225 (OPT)    (3 22 11 2 16 26 8 15 21 9 19 12 18 20 23 25 14 5 1 6 13 24 4 7 17 10)

*  Bur26e  26    5386879 (OPT)    (14 4 13 7 16 25 26 17 1 15 12 20 18 19  3 8 21 9 5 24 6 10 22 2 23 11)

*  Bur26f  26    3782044 (OPT)    (7 2 13 17 16 26 23 1 10 15 19 20 18 12 14 25 21 5 9 3 6 24 22 4 11 8)

*  Bur26g  26   10117172 (OPT)    (22 11 2 23 13 25 24 8 1 21 20 4 7 18 12 15 9 19 5 26 16 6 14 3 17 10)

*  Bur26h  26    7098658 (OPT)    (22 16 3 12 6 24 17 1 8 21 20 4 7 18 14 15 9 5 19 2 11 13 23 26 25 10)```

### 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 (OPT)     (11,3,7,23,19,27,15,14,20,17,28,9,12,4,8,2,26,24,32,13,22,25,6,18,29,10,30,21,1,5,16,31)

*  Esc32b  32   168 (OPT)     (15,31,7,8,23,24,16,32,14,10,30,26,5,6,13,9,2,1,21,22,29,25,18,17,12,27,20,11,3,19,28,4)

*  Esc32c  32   642 (OPT)     (15,12,27,13,22,8,24,23,20,19,4,2,1,7,6,3,5,18,17,21,14,29,16,32,26,11,31,30,28,10,25,9)

*  Esc32d  32   200 (OPT)     (18,29,10,2,25,32,22,20,24,17,30,9,1,26,31,21,19,23,27,16,13,6,3,11,15,7,8,5,14,4,12,28)

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)

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 (OPT)     (1,19,29,22,12,4,30,25,9,7,27,11,21,6,5,13,14,

31,10,28,8,3,23,26,17,2,32,15,24,18,20,16)

*  Esc64a  64   116 (OPT)     (1,2,9,50,3,61,4,62,5,54,64,6,7,52,56,8,55,10,63,18,11,51,12,13,14,15,20,43,16,41,17,47,23,19,24,21,53,22,28,25,26,27,29,60,30,59,31,32,33,34,35,36,37,38,39,40,42,44,45,46,48,49,57,58)

*  Esc128 128    64 (OPT)     (1,2,3,4,117,5,6,7,8,9,10,11,12,73,13,89,

14,15,16,17,18,19,20,21,22,23,24,53,25,26,102,

27,104,28,118,120,29,30,31,80,32,111,112,34,35,

36,97,98,38,39,100,40,99,41,42,43,44,45,46,47,

48,33,49,37,51,121,52,54,122,55,123,56,124,57,

125,58,126,59,127,128,81,60,61,62,63,64,113,

105,66,67,68,69,70,65,71,72,74,75,76,77,78,79,

82,83,84,85,86,87,88,90,50,91,114,92,93,94,95,

96,101,103,106,107,108,109,110,115,116,119)```

### 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

```   name   n    solution      permutation

------------------------------------------------------------------------

Had12  12   1652 (OPT)    (3,10,11,2,12,5,6,7,8,1,4,9)

Had14  14   2724 (OPT)    (8,13,10,5,12,11,2,14,3,6,7,1,9,4)

Had16  16   3720 (OPT)    (9,4,16,1,7,8,6,14,15,11,12,10,5,3,2,13)

Had18  18   5358 (OPT)    (8,15,16,6,7,18,14,11,1,10,12,5,3,13,2,17,9,4)

Had20  20   6922 (OPT)    (8,15,16,14,19,6,7,17,1,12,10,11,5,20,2,3,4,9,18,13)```

### 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)     (23,10,28,29,21,7,13,24,20,8,9,19,25,27,15,

4,22,12,6,5,16,11,3,2,17,1,30,26,18,14)

*   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   88700 (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)    (5 12 6 13 2 21 26 24 10 9 29 28 17 1 8 7 19 25 23 22 11 16 30 4 15 18 27 3 14 20)```

### 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)    109030 (SDRMS-SUM)    5.63 %
*  Sko100a  100   152002 (GEN)      143846 (SDRMS-SUM)    5.37 %
*  Sko100b  100   153890 (GEN)      145522 (SDRMS-SUM)    5.44 %
*  Sko100c  100   147862 (GEN)      139881 (SDRMS-SUM)    5.54 %
*  Sko100d  100   149576 (GEN)      141289 (SDRMS-SUM)    5.54 %
*  Sko100e  100   149150 (GEN)      140893 (SDRMS-SUM)    5.54 %
*  Sko100f  100   149036 (GEN)      140691 (SDRMS-SUM)    5.60 %```

### 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.           permutation/bound      gap

----------------------------------------------------------------------------------

*  Ste36a  36       9526 (OPT)     (35,5,6,12,11,27,26,25,24,9,4,1,13,20,14,23,21,22,2,8,10,7,28,19,32,34,33,17,18,3,15,16,29,30,31,36)

*  Ste36b  36      15852 (OPT)     (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    8239110 (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

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 and the Tai25a.

Giovannetti [Giovannetti:97] showed the optimality of Tai25b.

Drezner [Drez:06] proved the optimality of the Tai64c. Drezner’s method is branch and bound. His bound exploits the special structure of the problem.

```   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 (OPT)     (9,4,6,11,5,1,15,10,14,3,17,12,19,18,23,8,21,2,22,7,16,20,24,25,13)

*  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)     1706855 (L&P)            6.12 %

*  Tai30b    30    637117113 (OPT)     (4 8 11 15 17 20 21 5 14 30 2 13 6 29 10 26 27 24 28 22 12 9 7 23 19 18 25 16 1 3)

Tai35a    35      2422002 (Ro-TS)     2216627 (L&P)            8,48 %

*  Tai35b    35    283315445 (Ro-TS)   242172800 (SDRMS-SUM)     14.52 %

Tai40a    40      3139370 (Ro-TS)     2843274 (L&P)            9.43 %

*  Tai40b    40    637250948 (Ro-TS)   564428353 (SDRMS-SUM)     11.43 %

*  Tai50a    50      4938796 (ITS)       4390920 (L&P)           11.09 %

*  Tai50b    50    458821517 (Ro-TS)   395543467 (SDRMS-SUM)     13.79 %

*  Tai60a    60      7205962 (TS-2)      5578356 (SDRMS)           22.59 %

*  Tai60b    60    608215054 (Ro-TS)   542376603 (SDRMS-SUM)     10.82 %

Tai64c    64      1855928 (BandB)   (1,3,5,15,17,20,30,35,40,45,49,51,55,2,4,6,7,8,9,10,11,12,13,14,16,18,19,21,22,23,24,25,26,27,28,29,31,32,33,34,36,37,38,39,41,42,43,44,46,47,48,50,52,53,54,56,57,58,59,60,61,62,63,64)

*  Tai80a    80     13499184 (ITS)      10501941 (DP)            22.20 %

*  Tai80b    80    818415043 (Ro-TS)   717907288 (SDRMS-SUM)     12.28 %

*  Tai100a  100     21052466 (ITS)      15844731 (SDRMS)           24.86 %

*  Tai100b  100   1185996137 (Ro-TS)  1058131796 (SDRMS-SUM)     10.78 %
*  Tai150b  150    498896643 (GEN-3)   441786736 (SDRMS-SUM)     11.45 %
*  Tai256c  256     44759294 (ANT)      43849646 (SDRMS)          2.03 %```

### 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)     224414 (L&P)         6.69 %

*  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)    264442 (SDRMS-SUM) 3.15 %```

GO BACK TO MAIN PAGE OF QAPLIB