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	Optimal	8,017	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	Optimal	8,234	8,234	LKH
irw2802	Optimal	8,423	8,423	Keld Helsgaun
lsm2854	Optimal	8,014	8,014	LKH
dbj2924	Optimal	10,128	10,128	LKH
xva2993	Optimal	8,492	8,492	LKH
pia3056	Optimal	8,258	8,258	Hung Dinh Nguyen
dke3097	Optimal	10,539	10,539	LKH
lsn3119	Optimal	9,114	9,114	LKH
lta3140	Optimal	9,517	9,517	LKH
fdp3256	Optimal	10,008	10,008	LKH
beg3293	Optimal	9,772	9,772	LKH
dhb3386	Optimal	11,137	11,137	LKH
fjs3649	Optimal	9,272	9,272	LKH
fjr3672	Optimal	9,601	9,601	LKH
dlb3694	Optimal	10,959	10,959	LKH
ltb3729	Optimal	11,821	11,821	LKH
xqe3891	Optimal	11,995	11,995	Hung Dinh Nguyen
xua3937	Optimal	11,239	11,239	LKH
dkc3938	Optimal	12,503	12,503	LKH
dkf3954	Optimal	12,538	12,538	LKH
bgb4355	Optimal	12,723	12,723	Hung Dinh Nguyen
bgd4396	Optimal	13,009	13,009	LKH
frv4410	Optimal	10,711	10,711	LKH
bgf4475	Optimal	13,221	13,221	LKH
xqd4966	Optimal	15,316	15,316	LKH
fqm5087	Optimal	13,029	13,029	LKH
fea5557	Optimal	15,445	15,445	LKH
xsc6880	Optimal	21,535	21,535	Goldengorin, Jaeger, Molitor, Richter
bnd7168	Optimal	21,834	21,834	LKH
lap7454	Optimal	19,535	19,535	Keld Helsgaun
ida8197	Optimal	22,338	22,338	Hung Dinh Nguyen
dga9698	Optimal	27,724	27,724	LKH
xmc10150	Optimal	28,387	28,387	Hung Dinh Nguyen
xvb13584	Optimal	37,083	37,083	C. Dong, G. Jaeger, P. Molitor, D. Richter
xrb14233	0.026%	45,450	45,462	Keld Helsgaun
xia16928	0.023%	52,838	52,850	Hung Dinh Nguyen
pjh17845	0.019%	48,083	48,092	Keld Helsgaun
frh19289	0.013%	55,791	55,798	Keld Helsgaun
fnc19402	0.020%	59,275	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,087	Kazuma Honda, Yuichi Nagata, Isao Ono
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,183	Keld Helsgaun
fht47608	x.x%	xxx	125,104	Yuichi Nagata
fna52057	x.x%	xxx	147,789	C. Dong, G. Jaeger, P. Molitor, D. Richter
bna56769	x.x%	xxx	158,078	Yuichi Nagata
dan59296	x.x%	xxx	165,371	Xavier Clarist
sra104815	x.x%	xxx	251,342	Xavier Clarist
ara238025	x.x%	xxx	578,761	Xavier Clarist
lra498378	x.x%	xxx	2,168,039	Xavier Clarist
lrb744710	x.x%	xxx	1,611,232	Xavier Clarist

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.
3. To keep the challenge list up to date, on April 4, 2017, I posted optimal results for all instances under 6,000 points. Each of the 24 newly posted results was solved with Concorde (including the option to use domino-parity constraints). The total running time was under 24 hours in each instance, with the time for the branch-and-cut search ranging from a low of 133 seconds for fjs3649 to a high of 51530 seconds for fea5557. Each run was made on a single core of an Intel Xeon E5-2697 @ 2.70 GHz.

Back to TSP home.