QAPLIB

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	1160455924	2.15%	NewtBracket
Tai150b (n = 150)	498896643	473333270	5.12%	NewtBracket
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	147971	2.65%	NewtBracket
Sko100b (n = 100)	153890	149648	2.76%	NewtBracket
Sko100c (n = 100)	147862	144168	2.50%	NewtBracket
Sko100d (n = 100)	149576	145351	2.82%	NewtBracket
Sko100e (n = 100)	149150	145249	2.62%	NewtBracket
Sko100f (n = 100)	149036	144755	2.87%	NewtBracket