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
tour value CPU time tour value CPU time Memory

E1k.0234818034.14234818030.151048
E1k.1230166704.42230166700.141048
E1k.2230798374.46230798370.121048
E1k.3231857753.97231857750.131048
E1k.4228121634.02228121630.131048
E1k.5232211704.05232211700.141048
E1k.6233646883.85233646880.151048
E1k.7229355454.31229355450.141048
E1k.8230888764.10230888760.151048
E1k.9233929164.03233895570.1410481.891%
E3k.04072153917.46407215390.381568
E3k.14041004717.91404100470.391568
E3k.24040860617.78404086060.401568
E3k.34072560319.87407256030.411568
E3k.44087584418.58408758440.381568
E10k.072027572107.32720275721.263216
E10k.172214968106.50722149681.223216
E10k.271970279105.74719702791.233216
E31k.0127603391457.681276032463.8884080.013%
E31k.1127776265454.361277762653.898408
E100k.02263909411951.4622639086612.3424M0.004%
E100k.12262852591981.8722628525912.2424M
E316k.04023539447748.1540235335438.8575M0.016%
E1M.071510539331484.91715104010122.90235M0.022%
E3M.0Insufficient Memory Available
E10M.0Insufficient Memory Available
C1k.01144488515.32114448850.121048
C1k.11137781112.70113778110.131048
C1k.21125718718.96112571220.1210480.015%
C1k.31189310017.80118931000.121048
C1k.41161292217.66116129220.131048
C1k.51142849115.16114284910.141048
C1k.61018856513.29101885650.131048
C1k.71087034717.11108703470.131048
C1k.81182294319.41118229430.151048
C1k.91097677920.42109767790.141048
C3k.01972003172.53197200310.401568
C3k.11921918671.19192191860.391568
C3k.21987868172.51198786810.421568
C3k.31966519470.78196651940.411568
C3k.41929261961.98192926190.411568
C10k.033491014404.87334910141.253216
C10k.133661173375.40336611051.2032160.010%
C10k.233442659364.66334426591.233216
C31k.0602125741713.81602117763.8784080.076%
C31k.1601934851798.29601932973.8784080.014%
C100k.01058048217339.3410580454412.5524M0.015%
C100k.11067013647562.4210670069112.3624M0.033%
C316k.018947782830500.6518947697639.0475M0.022%
M1k.0207894350.4820789431.544936
M1k.1216051852.2121605181.574936
M1k.2217097161.8421709711.564936
M1k.3205813660.7120581361.614936
M3k.02131612467.13213161214.8839M
M3k.12119022489.87211902215.0039M
M10k.0Insufficient Memory Available
dsj1000187295859.77187285850.1310480.548%
pr10022602933.782602930.131048
si1032928726.12928721.285200
u10602244975.332244970.151064
vm10842401135.532401130.151072
pcb1173570543.72570540.161088
d1291510724.12510720.181120
rl13042553706.962553700.171120
rl13232718295.572716360.1711283.209%
nrw1379567505.58567500.191136
fl14002026037.16202600.191144
u14321536786.351536780.181152
fl15772381715.95238170.211184
d1655623955.03623950.211208
vm174833688711.013368870.221224
u1817576645.11576550.2312480.922%
rl188931803610.363180360.231264
d21038174010.80817400.271320
u2152646995.51646990.271328
u231923468329.332346830.301368
pr23923799878.673799870.301384
pcb303813812611.731381260.381544
fl37952943245.50294320.471720
fnl446118297322.021829730.571880
rl591556987234.945698660.7022320.046%
rl593455968834.225596880.722240
pla73972332261858.73233212340.9025920.706%
rl11849926610117.699266101.453656
usa1350920034494181.04200344581.6840560.020%
brd14051471410120.294714101.724184
d151121576257197.2815762571.814440
d18512646356158.356463562.205256
pla3381066345294350.83663345354.0289361.681%
pla85900*1427780431164.731427574429.8721M2.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
tour value CPU time tour value CPU time Memory

E1k.0234818034.14234818030.661104
E1k.1230166704.42230166700.671104
E1k.2230798374.46230798370.671104
E1k.3231857753.97231857750.661104
E1k.4228121634.02228121630.671104
E1k.5232211704.05232211700.661104
E1k.6233646883.85233646880.661104
E1k.7229355454.31229355450.681104
E1k.8230888764.10230888760.671104
E1k.9233929164.03233895570.6611041.891%
E3k.04072153917.46407215392.071720
E3k.14041004717.91404100472.041720
E3k.24040860617.78404086062.041720
E3k.34072560319.87407256032.061720
E3k.44087584418.58408758442.051720
E10k.072027572107.32720275726.653656
E10k.172214968106.50722149686.623656
E10k.271970279105.74719702796.653656
E31k.0127603391457.6812760244920.7997760.083%
E31k.1127776265454.3612777626520.779776
E100k.02263909411951.4622639086666.2828M0.004%
E100k.12262852591981.8722628510466.2828M0.008%
E316k.04023539447748.15402352601205.7288M0.036%
E1M.071510539331484.91715103886650.92274M0.024%
E3M.0Insufficient Memory Available
E10M.0Insufficient Memory Available
C1k.01144488515.32114448850.661104
C1k.11137781112.70113778110.671104
C1k.21125718718.96112571220.6611040.015%
C1k.31189310017.80118931000.661104
C1k.41161292217.66116129220.671104
C1k.51142849115.16114284910.671104
C1k.61018856513.29101885650.681104
C1k.71087034717.11108703470.671104
C1k.81182294319.41118229430.671104
C1k.91097677920.42109767790.661104
C3k.01972003172.53197200312.041720
C3k.11921918671.19192191862.051720
C3k.21987868172.51198786812.051720
C3k.31966519470.78196651942.061720
C3k.41929261961.98192926192.061720
C10k.033491014404.87334910146.653656
C10k.133661173375.40336611056.6436560.010%
C10k.233442659364.66334426596.703656
C31k.0602125741713.816021166420.7397760.087%
C31k.1601934851798.296019329720.8097760.014%
C100k.01058048217339.3410580452966.5128M0.015%
C100k.11067013647562.4210670058466.3828M0.038%
C316k.018947782830500.65189476542206.5388M0.033%
M1k.0207894350.4820789432.104992
M1k.1216051852.2121605182.114992
M1k.2217097161.8421709712.074992
M1k.3205813660.7120581362.084992
M3k.02131612467.13213161216.6839M
M3k.12119022489.87211902216.7339M
M10k.0Insufficient Memory Available
dsj1000187295859.77187285850.6611040.548%
pr10022602933.782602930.681104
si1032928726.12928721.845256
u10602244975.332244970.721120
vm10842401135.532401130.701128
pcb1173570543.72570540.771152
d1291510724.12510720.841184
rl13042553706.962553700.821192
rl13232718295.572716360.8512003.209%
nrw1379567505.58567500.931208
fl14002026037.16202600.911216
u14321536786.351536780.921224
fl15772381715.95238171.021264
d1655623955.03623911.0612880.473%
vm174833688711.013368871.141312
u1817576645.11576551.1813360.922%
rl188931803610.363180361.281352
d21038174010.80817401.341416
u2152646995.51646991.361432
u231923468329.332346831.541480
pr23923799878.673799871.551496
pcb303813812611.731381261.971680
fl37952943245.50294322.351896
fnl446118297322.021829732.872088
rl591556987234.945698663.7724960.046%
rl593455968834.225596883.762505
pla73972332261858.73233201154.6629201.276%
rl11849926610117.699266107.474176
usa1350920034494181.04200344588.8246480.020%
brd14051471410120.294714108.964800
d151121576257197.2815762579.865104
d18512646356158.3564635611.916064
pla3381066345294350.836633382122.1010M1.793%
pla85900*1427780431164.7314275744252.4625M2.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=56.49 mem=28M)


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

E1k.0234818034.14234818033.761272
E1k.1230166704.42230166703.731272
E1k.2230798374.46230798373.681272
E1k.3231857753.97231857753.751272
E1k.4228121634.02228121633.651272
E1k.5232211704.05232211703.711272
E1k.6233646883.85233646883.721272
E1k.7229355454.31229355453.721272
E1k.8230888764.10230888763.701272
E1k.9233929164.03233895573.7212721.891%
E3k.04072153917.464072153911.711920
E3k.14041004717.914041004711.681920
E3k.24040860617.784040860611.671920
E3k.34072560319.874072560311.681920
E3k.44087584418.584087584411.701920
E10k.072027572107.327202757236.834144
E10k.172214968106.507221496836.854144
E10k.271970279105.747197027936.804144
E31k.0127603391457.68127602449116.3811M0.083%
E31k.1127776265454.36127776265116.2511M
E100k.02263909411951.46226390866369.2333M0.004%
E100k.12262852591981.87226285104369.4833M0.008%
E316k.04023539447748.154023525311172.18102M0.037%
E1M.071510539331484.91715103854*3707.77*281M*0.024%*
E3M.0Insufficient Memory Available
E10M.0Insufficient Memory Available
C1k.01144488515.32114448853.701272
C1k.11137781112.70113778113.691272
C1k.21125718718.96112571223.7012720.015%
C1k.31189310017.80118931003.711272
C1k.41161292217.66116129223.711272
C1k.51142849115.16114284913.731272
C1k.61018856513.29101885653.701272
C1k.71087034717.11108703473.701272
C1k.81182294319.41118229433.711272
C1k.91097677920.42109767793.721272
C3k.01972003172.531972003111.731920
C3k.11921918671.191921918611.681920
C3k.21987868172.511987868111.811920
C3k.31966519470.781966519411.721920
C3k.41929261961.981929261911.751920
C10k.033491014404.873349101436.824144
C10k.133661173375.403366110536.8241440.010%
C10k.233442659364.663344265936.884144
C31k.0602125741713.8160211510117.2211M0.102%
C31k.1601934851798.2960193297117.1411M0.014%
C100k.01058048217339.34105804427371.9433M0.021%
C100k.11067013647562.42106700436372.1633M0.046%
C316k.018947782830500.651894764641175.14102M0.035%
M1k.0207894350.4820789435.105160
M1k.1216051852.2121605185.085160
M1k.2217097161.8421709715.155160
M1k.3205813660.7120581365.115160
M3k.02131612467.13213161226.335160
M3k.12119022489.87211902226.435160
M10k.0Insufficient Memory Available
dsj1000187295859.77187285853.7112720.548%
pr10022602933.782602933.701272
si1032928726.12928724.855242
u10602244975.332244973.921288
vm10842401135.532401134.011288
pcb1173570543.72570544.251312
d1291510724.12510724.641344
rl13042553706.962553704.701344
rl13232718295.572716364.7613523.209%
nrw1379567505.58567505.081368
fl14002026037.16202605.141368
u14321536786.351536785.251376
fl15772381715.95238175.731416
d1655623955.03623906.0014320.591%
vm174833688711.013368876.281456
u1817576645.11576556.5914800.922%
rl188931803610.363180326.8014960.063%
d21038174010.80817377.4615680.123%
u2152646995.51646967.8215840.357%
u231923468329.332346838.571640
pr23923799878.673799878.821664
pcb303813812611.7313812611.141872
fl37952943245.502943213.512120
fnl446118297322.0218297316.392344
rl591556987234.9456986620.8028160.046%
rl593455968834.2255968821.022824
pla73972332261858.732331940326.8632961.639%
rl11849926610117.6992661042.394752
usa1350920034494181.042003445850.0952880.020%
brd14051471410120.2947141051.585472
d151121576257197.28157625755.905816
d18512646356158.3564635667.916920
pla3381066345294350.8366333382122.8412M1.862%
pla859001427780431164.73142757442313.8528M2.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.