R.E. BURKARD, E. ÇELA, S.E. KARISCH and F. RENDL
Complete List
- R.E. Burkard and J. Offermann
- N. Christofides and E. Benavent
- A.N. Elshafei
- B. Eschermann and H.J. Wunderlich
- S.W. Hadley, F. Rendl and H. Wolkowicz
- J. Krarup and P.M. Pruzan
- Y. Li and P.M. Pardalos
- C.E. Nugent, T.E. Vollmann and J. Ruml
- C. Roucairol
- M. Scriabin and R.C. Vergin
- J. Skorin-Kapov
- L. Steinberg
- E.D. Taillard
- U.W. Thonemann and A. Bölte
- M.R. Wilhelm and T.L. Ward
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
- ant systems: (ANT) [Stuetzle:97].
- genetic hybrids: (GEN) [FlFe:94],(GEN-2) [OsRu:96],(GEN-3) [TaGa:97], and (GEN-4) [Mise:04].
- a greedy randomized adaptive search procedure: (GRASP) [LiPaRe:94],
- scatter search: (ScS) [CuMaMiTa:97],
- simulated annealing: (SIM-1) [BuRe:84],(SIM-2)[ThBo:94] and(SIM-3) [Mise:03], and
- simulated jumping: (SIMJ) [Amin:98].
- tabu search:parallel adaptive tabu search (PA-TS)[TaHaGe:97],reactive tabu search (Re-TS) [BaTe:94],robust tabu search (Ro-TS) [Taillard:91,Taillard:94],strict tabu search (S-TS) [Skorin:90], (TS-1) [Iriyama:97], (TS-2) [Mise:05] and (ITS) [Mise:08]
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],
- a dual framework based bound: (DFB)[KaCeClEs:98],
- a lift-and-project relaxation bound: (L&P)[http://www.optimization-online.org/DB_HTML/2004/06/890.html],
- a level-2 RLT bound: (RLT2)[HHJGSR:01],
- a semidefinite programming bound: (SDP1)[DKSo:07], and
- a semidefinite relaxation-matrix splitting bound: (SDRMS)[http://www.optimization-online.org/DB_HTML/2009/02/2220.html],
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
20 April 2012 – Peter Hahn ()
and Miguel Anjos ()