# dp6.txt # # Running Times for Dynamic Programming Routine (k=6) 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 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 = 5*k 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 8*k, the tour could be generated. (time=10.60 mem=24M) +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.)