Miguel Anjos, PhD, FCAE, FEUROPT, SMIEEE
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%
Taillard (1991, 1995)
 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%