# dp8.txt # # Running Times for Dynamic Programming Routine (k=8) 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.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% *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=56.49 mem=28M) +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.)