# dp10.txt # # Running Times for Dynamic Programming Routine (k=10) 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. Chained Lin-Kernighan Our Improvements % of HK problem tour value CPU time tour value CPU time Memory 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 = 5*k. However, the code was able to run with h = 3*k, which was sufficient to generate the tour, and these results are placed here. +The Lin-Kernighan routine had insufficient memory to generate a tour for E3M.0, E10M.0, and M10k.0, and our algorithm also had insufficient memory when given a starting tour from a different source. (For M10k.0, the data itself requires 400M of memory and at most this machine had 350M available.)