Miguel Anjos, PhD, FCAE, FEUROPT, SMIEEE
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 | Software |
---|---|---|---|---|
Tho40 (n = 40) | 240516 | 5.17% | ||
Tho150 (n = 150) | 8133398 | 3.42% |
Wilhelm and Ward (1987) | Feasible solution | Bound | Gap | Software |
---|---|---|---|---|
Wil50 (n = 50) | 48816 | 1.17% | ||
Wil100 (n = 100) | 273038 | 1.50% |
Feasible solution | Bound | Gap | Software | |
---|---|---|---|---|
Tai35a (n = 35) | 2422002 | 7.58% | ||
Tai40a (n = 40) | 3139370 | 8.62% | ||
Tai50a (n = 50) | 4938796 | 10.28% | ||
Tai50b (n = 50) | 458821517 | 4.16% | ||
Tai60a (n = 60) | 7205962 | 11.58% | ||
Tai60b (n = 60) | 608215054 | 2.05% | ||
Tai80a (n = 80) | 13499184 | 13.10% | ||
Tai80b (n = 80) | 818415043 | 3.47% | ||
Tai100a (n = 100) | 21044752 | 15.16% | ||
Tai100b (n = 100) | 1185996137 | 2.15% | ||
Tai150b (n = 150) | 498896643 | 5.12% | ||
Tai256c (n = 256) | 44759294 | 1.36% |
Skorin-Kapov (1990) | Feasible solution | Bound | Gap | Software |
---|---|---|---|---|
Sko49 (n = 49) | 23386 | 2.70% | ||
Sko56 (n = 56) | 34458 | 2.92% | ||
Sko64 (n = 64) | 48498 | 2.93% | ||
Sko72 (n = 72) | 66256 | 2.43% | ||
Sko81 (n = 81) | 90998 | 2.64% | ||
Sko90 (n = 90) | 115534 | 2.69% | ||
Sko100a (n = 100) | 152002 | 2.65% | ||
Sko100b (n = 100) | 153890 | 2.74% | ||
Sko100c (n = 100) | 147862 | 2.50% | ||
Sko100d (n = 100) | 149576 | 2.82% | ||
Sko100e (n = 100) | 149150 | 2.62% | ||
Sko100f (n = 100) | 149036 | 2.87% |