The format of the problem data is
nwhere 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
A
B
--- --- \ \ min / / a b p --- --- ij p(i),p(j) i jwhere 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
n sol pwhere 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
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)
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)
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)
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)
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)
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)
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)
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)
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)
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)
name n feas.sol. bound gap ------------------------------------------------------- Sko42 42 15812 (Ro-TS) 15332 (BBCPOP) 3.04 % Sko49 49 23386 (Ro-TS) 22650 (BBCPOP) 3.15 % Sko56 56 34458 (Ro-TS) 33385 (BBCPOP) 3.11 % Sko64 64 48498 (Ro-TS) 47017 (BBCPOP) 3.05 % Sko72 72 66256 (Ro-TS) 64455 (BBCPOP) 3.05 % Sko81 81 90998 (GEN) 88359 (BBCPOP) 2.90 % * Sko90 90 115534 (Ro-TS) 112423 (BBCPOP) 2.69 % * 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 %
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)
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) 269532400 (BBCPOP) 4.86 % Tai40a 40 3139370 (Ro-TS) 2843274 (L&P) 9.43 % * Tai40b 40 637250948 (Ro-TS) 608808400 (BBCPOP) 4.46 % * Tai50a 50 4938796 (ITS) 4390920 (L&P) 11.09 % * Tai50b 50 458821517 (Ro-TS) 431090700 (BBCPOP) 6.04 % * Tai60a 60 7205962 (TS-2) 6325978 (BBCPOP) 12.21 % * Tai60b 60 608215054 (Ro-TS) 592371800 (BBCPOP) 2.60 % 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) 11657010 (BBCPOP) 13.65 % * Tai80b 80 818415043 (Ro-TS) 786298800 (BBCPOP) 3.92 % * Tai100a 100 21044752 (ITS) 17853840 (BBCPOP) 15.16 % * Tai100b 100 1185996137 (Ro-TS) 1151591000 (BBCPOP) 2.90 % * Tai150b 150 498896643 (GEN-3) 441786736 (SDRMS-SUM) 11.45 % * Tai256c 256 44759294 (ANT) 44095032 (NDQCR) 1.48 %
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) 226490 (BBCPOP) 5.83 % * Tho150 150 8133398 (SIM-3) 7620628 (TDB) 6.30 %
name n feas.sol. bound gap ------------------------------------------------------- Wil50 50 48816 (SIM-2) 48121 (BBCPOP) 1.42 % * Wil100 100 273038 (GEN) 268955 (BBCPOP) 1.50 %