Running Times for Dynamic Programming Routine on complex.gsia.cmu.edu; A Sun Ultra 60 with two 360 MHz UltraSPARC-II processors, 4 MB cache, and 512 MB main memory.

Starting solutions were obtained using the Lin-Kernighan routine from the CONCORDE website, with default parameter settings except the random seed, which was set to 1.

Per cent of Held-Karp gap closed is calculated as: (LKtour - DPtour)/(LKtour - HKbound)

Times in CPU seconds, memory in kilobyes unless specified.

Results for DP6, DP8, DP10.

problem	Chained Lin-Kernighan		Our Improvements (k=6)			% of HK gap closed
problem	tour value	CPU time	tour value	CPU time	Memory	% of HK gap closed

E1k.0	23481803	4.14	23481803	0.15	1048
E1k.1	23016670	4.42	23016670	0.14	1048
E1k.2	23079837	4.46	23079837	0.12	1048
E1k.3	23185775	3.97	23185775	0.13	1048
E1k.4	22812163	4.02	22812163	0.13	1048
E1k.5	23221170	4.05	23221170	0.14	1048
E1k.6	23364688	3.85	23364688	0.15	1048
E1k.7	22935545	4.31	22935545	0.14	1048
E1k.8	23088876	4.10	23088876	0.15	1048
E1k.9	23392916	4.03	23389557	0.14	1048	1.891%
E3k.0	40721539	17.46	40721539	0.38	1568
E3k.1	40410047	17.91	40410047	0.39	1568
E3k.2	40408606	17.78	40408606	0.40	1568
E3k.3	40725603	19.87	40725603	0.41	1568
E3k.4	40875844	18.58	40875844	0.38	1568
E10k.0	72027572	107.32	72027572	1.26	3216
E10k.1	72214968	106.50	72214968	1.22	3216
E10k.2	71970279	105.74	71970279	1.23	3216
E31k.0	127603391	457.68	127603246	3.88	8408	0.013%
E31k.1	127776265	454.36	127776265	3.89	8408
E100k.0	226390941	1951.46	226390866	12.34	24M	0.004%
E100k.1	226285259	1981.87	226285259	12.24	24M
E316k.0	402353944	7748.15	402353354	38.85	75M	0.016%
E1M.0	715105393	31484.91	715104010	122.90	235M	0.022%
E3M.0	Insufficient Memory Available
E10M.0	Insufficient Memory Available
C1k.0	11444885	15.32	11444885	0.12	1048
C1k.1	11377811	12.70	11377811	0.13	1048
C1k.2	11257187	18.96	11257122	0.12	1048	0.015%
C1k.3	11893100	17.80	11893100	0.12	1048
C1k.4	11612922	17.66	11612922	0.13	1048
C1k.5	11428491	15.16	11428491	0.14	1048
C1k.6	10188565	13.29	10188565	0.13	1048
C1k.7	10870347	17.11	10870347	0.13	1048
C1k.8	11822943	19.41	11822943	0.15	1048
C1k.9	10976779	20.42	10976779	0.14	1048
C3k.0	19720031	72.53	19720031	0.40	1568
C3k.1	19219186	71.19	19219186	0.39	1568
C3k.2	19878681	72.51	19878681	0.42	1568
C3k.3	19665194	70.78	19665194	0.41	1568
C3k.4	19292619	61.98	19292619	0.41	1568
C10k.0	33491014	404.87	33491014	1.25	3216
C10k.1	33661173	375.40	33661105	1.20	3216	0.010%
C10k.2	33442659	364.66	33442659	1.23	3216
C31k.0	60212574	1713.81	60211776	3.87	8408	0.076%
C31k.1	60193485	1798.29	60193297	3.87	8408	0.014%
C100k.0	105804821	7339.34	105804544	12.55	24M	0.015%
C100k.1	106701364	7562.42	106700691	12.36	24M	0.033%
C316k.0	189477828	30500.65	189476976	39.04	75M	0.022%
M1k.0	2078943	50.48	2078943	1.54	4936
M1k.1	2160518	52.21	2160518	1.57	4936
M1k.2	2170971	61.84	2170971	1.56	4936
M1k.3	2058136	60.71	2058136	1.61	4936
M3k.0	2131612	467.13	2131612	14.88	39M
M3k.1	2119022	489.87	2119022	15.00	39M
M10k.0	Insufficient Memory Available
dsj1000	18729585	9.77	18728585	0.13	1048	0.548%
pr1002	260293	3.78	260293	0.13	1048
si1032	92872	6.12	92872	1.28	5200
u1060	224497	5.33	224497	0.15	1064
vm1084	240113	5.53	240113	0.15	1072
pcb1173	57054	3.72	57054	0.16	1088
d1291	51072	4.12	51072	0.18	1120
rl1304	255370	6.96	255370	0.17	1120
rl1323	271829	5.57	271636	0.17	1128	3.209%
nrw1379	56750	5.58	56750	0.19	1136
fl1400	20260	37.16	20260	0.19	1144
u1432	153678	6.35	153678	0.18	1152
fl1577	23817	15.95	23817	0.21	1184
d1655	62395	5.03	62395	0.21	1208
vm1748	336887	11.01	336887	0.22	1224
u1817	57664	5.11	57655	0.23	1248	0.922%
rl1889	318036	10.36	318036	0.23	1264
d2103	81740	10.80	81740	0.27	1320
u2152	64699	5.51	64699	0.27	1328
u2319	234683	29.33	234683	0.30	1368
pr2392	379987	8.67	379987	0.30	1384
pcb3038	138126	11.73	138126	0.38	1544
fl3795	29432	45.50	29432	0.47	1720
fnl4461	182973	22.02	182973	0.57	1880
rl5915	569872	34.94	569866	0.70	2232	0.046%
rl5934	559688	34.22	559688	0.72	2240
pla7397	23322618	58.73	23321234	0.90	2592	0.706%
rl11849	926610	117.69	926610	1.45	3656
usa13509	20034494	181.04	20034458	1.68	4056	0.020%
brd14051	471410	120.29	471410	1.72	4184
d15112	1576257	197.28	1576257	1.81	4440
d18512	646356	158.35	646356	2.20	5256
pla33810	66345294	350.83	66334535	4.02	8936	1.681%
pla85900*	142778043	1164.73	142757442	9.87	21M	2.120%

*The default value of h = 5k could not generate the tour for pla85900, only the cost of the optimal tour subject to the dynamic programming restrictions was found. When h was increased to 8k, the tour could be generated. (time=10.60 mem=24M)

problem	Chained Lin-Kernighan		Our Improvements (k=8)			% of HK gap closed
problem	tour value	CPU time	tour value	CPU time	Memory	% of HK gap closed

E1k.0	23481803	4.14	23481803	0.66	1104
E1k.1	23016670	4.42	23016670	0.67	1104
E1k.2	23079837	4.46	23079837	0.67	1104
E1k.3	23185775	3.97	23185775	0.66	1104
E1k.4	22812163	4.02	22812163	0.67	1104
E1k.5	23221170	4.05	23221170	0.66	1104
E1k.6	23364688	3.85	23364688	0.66	1104
E1k.7	22935545	4.31	22935545	0.68	1104
E1k.8	23088876	4.10	23088876	0.67	1104
E1k.9	23392916	4.03	23389557	0.66	1104	1.891%
E3k.0	40721539	17.46	40721539	2.07	1720
E3k.1	40410047	17.91	40410047	2.04	1720
E3k.2	40408606	17.78	40408606	2.04	1720
E3k.3	40725603	19.87	40725603	2.06	1720
E3k.4	40875844	18.58	40875844	2.05	1720
E10k.0	72027572	107.32	72027572	6.65	3656
E10k.1	72214968	106.50	72214968	6.62	3656
E10k.2	71970279	105.74	71970279	6.65	3656
E31k.0	127603391	457.68	127602449	20.79	9776	0.083%
E31k.1	127776265	454.36	127776265	20.77	9776
E100k.0	226390941	1951.46	226390866	66.28	28M	0.004%
E100k.1	226285259	1981.87	226285104	66.28	28M	0.008%
E316k.0	402353944	7748.15	402352601	205.72	88M	0.036%
E1M.0	715105393	31484.91	715103886	650.92	274M	0.024%
E3M.0	Insufficient Memory Available
E10M.0	Insufficient Memory Available
C1k.0	11444885	15.32	11444885	0.66	1104
C1k.1	11377811	12.70	11377811	0.67	1104
C1k.2	11257187	18.96	11257122	0.66	1104	0.015%
C1k.3	11893100	17.80	11893100	0.66	1104
C1k.4	11612922	17.66	11612922	0.67	1104
C1k.5	11428491	15.16	11428491	0.67	1104
C1k.6	10188565	13.29	10188565	0.68	1104
C1k.7	10870347	17.11	10870347	0.67	1104
C1k.8	11822943	19.41	11822943	0.67	1104
C1k.9	10976779	20.42	10976779	0.66	1104
C3k.0	19720031	72.53	19720031	2.04	1720
C3k.1	19219186	71.19	19219186	2.05	1720
C3k.2	19878681	72.51	19878681	2.05	1720
C3k.3	19665194	70.78	19665194	2.06	1720
C3k.4	19292619	61.98	19292619	2.06	1720
C10k.0	33491014	404.87	33491014	6.65	3656
C10k.1	33661173	375.40	33661105	6.64	3656	0.010%
C10k.2	33442659	364.66	33442659	6.70	3656
C31k.0	60212574	1713.81	60211664	20.73	9776	0.087%
C31k.1	60193485	1798.29	60193297	20.80	9776	0.014%
C100k.0	105804821	7339.34	105804529	66.51	28M	0.015%
C100k.1	106701364	7562.42	106700584	66.38	28M	0.038%
C316k.0	189477828	30500.65	189476542	206.53	88M	0.033%
M1k.0	2078943	50.48	2078943	2.10	4992
M1k.1	2160518	52.21	2160518	2.11	4992
M1k.2	2170971	61.84	2170971	2.07	4992
M1k.3	2058136	60.71	2058136	2.08	4992
M3k.0	2131612	467.13	2131612	16.68	39M
M3k.1	2119022	489.87	2119022	16.73	39M
M10k.0	Insufficient Memory Available
dsj1000	18729585	9.77	18728585	0.66	1104	0.548%
pr1002	260293	3.78	260293	0.68	1104
si1032	92872	6.12	92872	1.84	5256
u1060	224497	5.33	224497	0.72	1120
vm1084	240113	5.53	240113	0.70	1128
pcb1173	57054	3.72	57054	0.77	1152
d1291	51072	4.12	51072	0.84	1184
rl1304	255370	6.96	255370	0.82	1192
rl1323	271829	5.57	271636	0.85	1200	3.209%
nrw1379	56750	5.58	56750	0.93	1208
fl1400	20260	37.16	20260	0.91	1216
u1432	153678	6.35	153678	0.92	1224
fl1577	23817	15.95	23817	1.02	1264
d1655	62395	5.03	62391	1.06	1288	0.473%
vm1748	336887	11.01	336887	1.14	1312
u1817	57664	5.11	57655	1.18	1336	0.922%
rl1889	318036	10.36	318036	1.28	1352
d2103	81740	10.80	81740	1.34	1416
u2152	64699	5.51	64699	1.36	1432
u2319	234683	29.33	234683	1.54	1480
pr2392	379987	8.67	379987	1.55	1496
pcb3038	138126	11.73	138126	1.97	1680
fl3795	29432	45.50	29432	2.35	1896
fnl4461	182973	22.02	182973	2.87	2088
rl5915	569872	34.94	569866	3.77	2496	0.046%
rl5934	559688	34.22	559688	3.76	2505
pla7397	23322618	58.73	23320115	4.66	2920	1.276%
rl11849	926610	117.69	926610	7.47	4176
usa13509	20034494	181.04	20034458	8.82	4648	0.020%
brd14051	471410	120.29	471410	8.96	4800
d15112	1576257	197.28	1576257	9.86	5104
d18512	646356	158.35	646356	11.91	6064
pla33810	66345294	350.83	66333821	22.10	10M	1.793%
pla85900*	142778043	1164.73	142757442	52.46	25M	2.120%

problem	Chained Lin-Kernighan		Our Improvements (k=10)			% of HK gap closed
problem	tour value	CPU time	tour value	CPU time	Memory	% of HK gap closed

E1k.0	23481803	4.14	23481803	3.76	1272
E1k.1	23016670	4.42	23016670	3.73	1272
E1k.2	23079837	4.46	23079837	3.68	1272
E1k.3	23185775	3.97	23185775	3.75	1272
E1k.4	22812163	4.02	22812163	3.65	1272
E1k.5	23221170	4.05	23221170	3.71	1272
E1k.6	23364688	3.85	23364688	3.72	1272
E1k.7	22935545	4.31	22935545	3.72	1272
E1k.8	23088876	4.10	23088876	3.70	1272
E1k.9	23392916	4.03	23389557	3.72	1272	1.891%
E3k.0	40721539	17.46	40721539	11.71	1920
E3k.1	40410047	17.91	40410047	11.68	1920
E3k.2	40408606	17.78	40408606	11.67	1920
E3k.3	40725603	19.87	40725603	11.68	1920
E3k.4	40875844	18.58	40875844	11.70	1920
E10k.0	72027572	107.32	72027572	36.83	4144
E10k.1	72214968	106.50	72214968	36.85	4144
E10k.2	71970279	105.74	71970279	36.80	4144
E31k.0	127603391	457.68	127602449	116.38	11M	0.083%
E31k.1	127776265	454.36	127776265	116.25	11M
E100k.0	226390941	1951.46	226390866	369.23	33M	0.004%
E100k.1	226285259	1981.87	226285104	369.48	33M	0.008%
E316k.0	402353944	7748.15	402352531	1172.18	102M	0.037%
E1M.0	715105393	31484.91	715103854*	3707.77*	281M*	0.024%*
E3M.0	Insufficient Memory Available
E10M.0	Insufficient Memory Available
C1k.0	11444885	15.32	11444885	3.70	1272
C1k.1	11377811	12.70	11377811	3.69	1272
C1k.2	11257187	18.96	11257122	3.70	1272	0.015%
C1k.3	11893100	17.80	11893100	3.71	1272
C1k.4	11612922	17.66	11612922	3.71	1272
C1k.5	11428491	15.16	11428491	3.73	1272
C1k.6	10188565	13.29	10188565	3.70	1272
C1k.7	10870347	17.11	10870347	3.70	1272
C1k.8	11822943	19.41	11822943	3.71	1272
C1k.9	10976779	20.42	10976779	3.72	1272
C3k.0	19720031	72.53	19720031	11.73	1920
C3k.1	19219186	71.19	19219186	11.68	1920
C3k.2	19878681	72.51	19878681	11.81	1920
C3k.3	19665194	70.78	19665194	11.72	1920
C3k.4	19292619	61.98	19292619	11.75	1920
C10k.0	33491014	404.87	33491014	36.82	4144
C10k.1	33661173	375.40	33661105	36.82	4144	0.010%
C10k.2	33442659	364.66	33442659	36.88	4144
C31k.0	60212574	1713.81	60211510	117.22	11M	0.102%
C31k.1	60193485	1798.29	60193297	117.14	11M	0.014%
C100k.0	105804821	7339.34	105804427	371.94	33M	0.021%
C100k.1	106701364	7562.42	106700436	372.16	33M	0.046%
C316k.0	189477828	30500.65	189476464	1175.14	102M	0.035%
M1k.0	2078943	50.48	2078943	5.10	5160
M1k.1	2160518	52.21	2160518	5.08	5160
M1k.2	2170971	61.84	2170971	5.15	5160
M1k.3	2058136	60.71	2058136	5.11	5160
M3k.0	2131612	467.13	2131612	26.33	5160
M3k.1	2119022	489.87	2119022	26.43	5160
M10k.0	Insufficient Memory Available
dsj1000	18729585	9.77	18728585	3.71	1272	0.548%
pr1002	260293	3.78	260293	3.70	1272
si1032	92872	6.12	92872	4.85	5242
u1060	224497	5.33	224497	3.92	1288
vm1084	240113	5.53	240113	4.01	1288
pcb1173	57054	3.72	57054	4.25	1312
d1291	51072	4.12	51072	4.64	1344
rl1304	255370	6.96	255370	4.70	1344
rl1323	271829	5.57	271636	4.76	1352	3.209%
nrw1379	56750	5.58	56750	5.08	1368
fl1400	20260	37.16	20260	5.14	1368
u1432	153678	6.35	153678	5.25	1376
fl1577	23817	15.95	23817	5.73	1416
d1655	62395	5.03	62390	6.00	1432	0.591%
vm1748	336887	11.01	336887	6.28	1456
u1817	57664	5.11	57655	6.59	1480	0.922%
rl1889	318036	10.36	318032	6.80	1496	0.063%
d2103	81740	10.80	81737	7.46	1568	0.123%
u2152	64699	5.51	64696	7.82	1584	0.357%
u2319	234683	29.33	234683	8.57	1640
pr2392	379987	8.67	379987	8.82	1664
pcb3038	138126	11.73	138126	11.14	1872
fl3795	29432	45.50	29432	13.51	2120
fnl4461	182973	22.02	182973	16.39	2344
rl5915	569872	34.94	569866	20.80	2816	0.046%
rl5934	559688	34.22	559688	21.02	2824
pla7397	23322618	58.73	23319403	26.86	3296	1.639%
rl11849	926610	117.69	926610	42.39	4752
usa13509	20034494	181.04	20034458	50.09	5288	0.020%
brd14051	471410	120.29	471410	51.58	5472
d15112	1576257	197.28	1576257	55.90	5816
d18512	646356	158.35	646356	67.91	6920
pla33810	66345294	350.83	66333382	122.84	12M	1.862%
pla85900	142778043	1164.73	142757442	313.85	28M	2.120%

*For E1M.0, there was not sufficient memory to use the default value of h = 5k. However, the code was able to run with h = 3k, which was sufficient to generate the tour, and these results are placed here.