We present below a summary of the solution status of the 102 VLSI TSP instances. In the table, we list the length of the best reported solution for each of the instances, and also the best reported lower bounds, that is, values for which it has been verified that there is no tour for the instance of length less than the specified number. The "Gap" column gives the % difference between the best tour and the best bound.

Name	Gap	Bound	Tour	Source of Tour
xqf131	Optimal	564	564	Concorde
xqg237	Optimal	1,019	1,019	Concorde
pma343	Optimal	1,368	1,368	Concorde
pka379	Optimal	1,332	1,332	Concorde
bcl380	Optimal	1,621	1,621	Concorde
pbl395	Optimal	1,281	1,281	Concorde
pbk411	Optimal	1,343	1,343	Concorde
pbn423	Optimal	1,365	1,365	Concorde
pbm436	Optimal	1,443	1,443	Concorde
xql662	Optimal	2,513	2,513	Concorde
rbx711	Optimal	3,115	3,115	Concorde
rbu737	Optimal	3,314	3,314	Concorde
dkg813	Optimal	3,199	3,199	Concorde
lim963	Optimal	2,789	2,789	Concorde
pbd984	Optimal	2,797	2,797	Concorde
xit1083	Optimal	3,558	3,558	Concorde
dka1376	Optimal	4,666	4,666	Concorde
dca1389	Optimal	5,085	5,085	Concorde
dja1436	Optimal	5,257	5,257	Concorde
icw1483	Optimal	4,416	4,416	Concorde
fra1488	Optimal	4,264	4,264	Concorde
rbv1583	Optimal	5,387	5,387	Concorde
rby1599	Optimal	5,533	5,533	Concorde
fnb1615	Optimal	4,956	4,956	Concorde
djc1785	Optimal	6,115	6,115	Concorde
dcc1911	Optimal	6,396	6,396	Concorde
dkd1973	Optimal	6,421	6,421	Concorde
djb2036	Optimal	6,197	6,197	Concorde
dcb2086	Optimal	6,600	6,600	Concorde
bva2144	Optimal	6,304	6,304	Concorde
xqc2175	Optimal	6,830	6,830	Keld Helsgaun
bck2217	Optimal	6,764	6,764	Concorde
xpr2308	Optimal	7,219	7,219	LKH
ley2323	Optimal	8,352	8,352	LKH
dea2382	x.x%	xxx	8,017	LKH
rbw2481	Optimal	7,724	7,724	LKH
pds2566	Optimal	7,643	7,643	LKH
mlt2597	Optimal	8,071	8,071	LKH
bch2762	x.x%	xxx	8,234	LKH
irw2802	Optimal	8,423	8,423	Keld Helsgaun
lsm2854	x.x%	xxx	8,014	LKH
dbj2924	Optimal	10,128	10,128	LKH
xva2993	x.x%	xxx	8,492	LKH
pia3056	x.x%	xxx	8,258	Hung Dinh Nguyen
dke3097	x.x%	xxx	10,539	LKH
lsn3119	x.x%	xxx	9,114	LKH
lta3140	x.x%	xxx	9,517	LKH
fdp3256	x.x%	xxx	10,008	LKH
beg3293	x.x%	xxx	9,772	LKH
dhb3386	x.x%	xxx	11,137	LKH
fjs3649	x.x%	xxx	9,272	LKH
fjr3672	x.x%	xxx	9,601	LKH
dlb3694	Optimal	10,959	10,959	LKH
ltb3729	x.x%	xxx	11,821	LKH
xqe3891	x.x%	xxx	11,995	Hung Dinh Nguyen
xua3937	x.x%	xxx	11,239	LKH
dkc3938	x.x%	xxx	12,503	LKH
dkf3954	x.x%	xxx	12,538	LKH
bgb4355	x.x%	xxx	12,723	Hung Dinh Nguyen
bgd4396	x.x%	xxx	13,009	LKH
frv4410	Optimal	10,711	10,711	LKH
bgf4475	x.x%	xxx	13,221	LKH
xqd4966	x.x%	xxx	15,316	LKH
fqm5087	x.x%	xxx	13,029	LKH
fea5557	x.x%	xxx	15,445	LKH
xsc6880	x.x%	xxx	21,535	Goldengorin, Jaeger, Molitor, Richter
bnd7168	x.x%	xxx	21,834	LKH
lap7454	x.x%	xxx	19,535	Keld Helsgaun
ida8197	x.x%	xxx	22,338	Hung Dinh Nguyen
dga9698	x.x%	xxx	27,724	LKH
xmc10150	x.x%	xxx	28,387	Hung Dinh Nguyen
xvb13584	x.x%	xxx	37,083	C. Dong, G. Jaeger, P. Molitor, D. Richter
xrb14233	x.x%	xxx	45,462	Keld Helsgaun
xia16928	x.x%	xxx	52,850	Hung Dinh Nguyen
pjh17845	x.x%	xxx	48,092	Keld Helsgaun
frh19289	x.x%	xxx	55,798	Keld Helsgaun
fnc19402	x.x%	xxx	59,287	C. Dong, G. Jaeger, P. Molitor, D. Richter
ido21215	0.028%	63,501	63,517	C. Dong, G. Jaeger, P. Molitor, D. Richter
fma21553	x.x%	xxx	66,527	Keld Helsgaun
lsb22777	x.x%	xxx	60,977	Keld Helsgaun
xrh24104	x.x%	xxx	69,294	Keld Helsgaun
bbz25234	x.x%	xxx	69,335	Keld Helsgaun
irx28268	x.x%	xxx	72,607	Keld Helsgaun
fyg28534	x.x%	xxx	78,562	C. Dong, G. Jaeger, P. Molitor, D. Richter
icx28698	x.x%	xxx	78,089	Keld Helsgaun
boa28924	x.x%	xxx	79,622	C. Dong, G. Jaeger, P. Molitor, D. Richter
ird29514	x.x%	xxx	80,353	Keld Helsgaun
pbh30440	x.x%	xxx	88,313	Keld Helsgaun
xib32892	x.x%	xxx	96,757	C. Dong, G. Jaeger, P. Molitor, D. Richter
fry33203	x.x%	xxx	97,240	Keld Helsgaun
bby34656	x.x%	xxx	99,159	C. Dong, G. Jaeger, P. Molitor, D. Richter
pba38478	x.x%	xxx	108,318	C. Dong, G. Jaeger, P. Molitor, D. Richter
ics39603	x.x%	xxx	106,819	Keld Helsgaun
rbz43748	x.x%	xxx	125,184	Masafumi Kuroda
fht47608	x.x%	xxx	125,106	Keld Helsgaun
fna52057	x.x%	xxx	147,789	C. Dong, G. Jaeger, P. Molitor, D. Richter
bna56769	x.x%	xxx	158,082	Keld Helsgaun
dan59296	x.x%	xxx	165,372	Keld Helsgaun
sra104815	x.x%	xxx	251,345	Keld Helsgaun
ara238025	x.x%	xxx	578,775	Keld Helsgaun
lra498378	x.x%	xxx	2,168,067	Keld Helsgaun
lrb744710	x.x%	xxx	1,611,276	Keld Helsgaun

Notes

1. All lower bounds were found by Concorde, our linear-programming based TSP solver.

2. LKH is Keld Helsgaun's powerful implementation of the Lin-Kernighan heuristic.

Back to TSP home.