Miguel Anjos, PhD, FCAE, FEUROPT, SMIEEEMiguel.F.Anjos@ed.ac.uk
Miguel.F.Anjos@ed.ac.uk
Click here to edit subtitle
QAPLIB is a Quadratic Assignment Problem Library.
Four previously unsolved QAPLIB instances have been solved to optimality in recent years: see tai30a, tai35b, tai40b, and sko42.
We present below the 28 instances that have not yet been solved to optimality; recent developments are highlighted. Have you found a better solution or bound? Send me an email!
| Thonemann and Bölte (1994) | Feasible solution | Bound | Gap |
|
Tho40 (n = 40)
|
240516
|
226490
|
5.83%
|
|
Tho150 (n = 150)
|
8133398
|
7620628
|
6.30%
|
| Wilhelm and Ward (1987) | Feasible solution | Bound | Gap |
|
Wil50 (n = 50)
|
48816
|
48121
|
1.42%
|
|
Wil100 (n = 100)
|
273038
|
268955
|
1.50%
|
| Feasible solution | Bound | Gap | Software | | | |
|
Tai35a (n = 35)
|
2422002
|
2216627
|
8.48%
|
|
|
|
|
Tai40a (n = 40)
|
3139370
|
2843274
|
9.43%
|
|
|
|
|
Tai50a (n = 50)
|
4938796
|
4390920
|
11.09%
|
|
|
|
|
Tai50b (n = 50)
|
458821517
|
431090700
|
6.04%
|
|
|
|
|
Tai60a (n = 60)
|
7205962
|
6325978
|
12.21%
|
|
|
|
|
Tai60b (n = 60)
|
608215054
|
592371800
|
2.60%
|
|
|
|
|
Tai80a (n = 80)
|
13499184
|
11657010
|
13.65%
|
|
|
|
|
Tai80b (n = 80)
|
818415043
|
786298800
|
3.92%
|
|
|
|
|
Tai100a (n = 100)
|
21044752
|
17853840
|
15.16%
|
|
|
|
|
Tai100b (n = 100)
|
1185996137
|
2.15%
|
|
|
||
|
Tai150b (n = 150)
|
498896643
|
5.12%
|
|
|
||
|
Tai256c (n = 256)
|
44759294
|
44095032
|
1.48%
|
|
|
|
| Skorin-Kapov (1990) | Feasible solution | Bound | Gap | Software |
|
Sko49 (n = 49)
|
23386
|
22650
|
3.15%
|
|
|
Sko56 (n = 56)
|
34458
|
33385
|
3.11%
|
|
|
Sko64 (n = 64)
|
48498
|
47017
|
3.05%
|
|
|
Sko72 (n = 72)
|
66256
|
64455
|
3.05%
|
|
|
Sko81 (n = 81)
|
90998
|
88359
|
2.90%
|
|
|
Sko90 (n = 90)
|
115534
|
112423
|
2.69%
|
|
|
Sko100a (n = 100)
|
152002
|
2.65%
|
||
|
Sko100b (n = 100)
|
153890
|
2.76%
|
||
|
Sko100c (n = 100)
|
147862
|
2.50%
|
||
|
Sko100d (n = 100)
|
149576
|
2.82%
|
||
|
Sko100e (n = 100)
|
149150
|
2.62%
|
||
|
Sko100f (n = 100)
|
149036
|
2.87%
|