16 Oct 2026 ==================================
LKHcats and Hexaly on ATSPs
==================================
Hans Mittelmann
<mittelmann@asu.edu>
The forthcoming hybrid solver LKHcats and the general purpose code Hexaly are applied to asymmetric traveling salesperson problems from
here and here. LKHcats encompasses the exact ATSP solver CCatsp and the heuristic LKHatsp. It is built on Concorde and LKH-2. CCatsp uses CPLEX as LP solver and LKHatsp has QSopt.
On the problems up to size 999 CCatsp is applied and on the larger ones LKHatsp unless CCatsp solved them optimally in the given time. Listed are the optimal objectives respectively the best known solutions, the gaps for Hexaly and the times it was run; next the times for LKHcats and the objectives achieved as well as the gaps.
Platform: AMD Ryzen 9 5900X (12 cores, 128GB); Random seed 99; Logfiles at: plato.asu.edu/ftp/atsp_logs/
============================================================================= instance size opt/BKS Hexaly gap time LKHcats obj gap ----------------------------------------------------------------------------- amz0000 119 80953 81109 0.19 10 4.50 opt 0.00 amz0001 106 81929 81929 0.00 10 0.35 amz0002 128 117884 117951 0.06 10 2.80 amz0003 142 104821 104821 0.00 10 0.32 amz0004 155 142426 142426 0.00 10 0.36 amz0005 190 134175 134901 0.54 10 0.96 amz0006 161 142825 142825 0.00 10 0.81 amz0007 155 147824 147824 0.00 10 0.48 amz0008 177 120133 120186 0.04 10 3.08 amz0009 59 54062 54062 0.00 10 0.13 amz0010 129 70600 70892 0.41 10 0.67 amz0011 185 136061 136244 0.13 10 0.91 amz0012 173 122351 122351 0.00 10 1.38 ---------------- amz0013 161 81289 81523 0.29 10 0.34 | These problems | amz0014 130 120045 120045 0.00 10 0.26 | | amz0015 176 93420 93618 0.21 10 1.18 | solved EXACTLY | amz0016 78 55860 55860 0.00 10 0.4| | | amz0017 145 113461 113461 0.00 10 0.52 | with CCatsp | amz0018 153 130737 130737 0.00 10 0.66 ---------------- amz0019 157 74222 74848 0.84 10 0.37 bk_n500_0001 101679 102234 0.55 20 1.35 bk_n500_0002 98644 98850 0.21 20 1.44 bk_n500_0003 135663 135751 0.06 20 1.40 bk_n500_0004 115415 115864 0.39 20 15.2 bk_n500_0005 89041 89185 0.16 20 2.76 bk_n500_0006 113294 113666 0.33 20 2.99 bk_n500_0007 110499 111087 0.53 20 3.11 bk_n500_0008 117736 118209 0.40 20 10.6 bk_n500_0009 114216 114542 0.29 20 3.86 bk_n500_0010 113402 114176 0.68 20 6.81 bk_n500_0011 119165 119165 0.00 20 0.55 bk_n500_0012 110291 110564 0.25 20 15.1 bk_n500_0013 95178 95500 0.34 20 3.12 bk_n500_0014 108797 109376 0.53 20 3.87 bk_n500_0015 135990 135990 0.00 20 0.87 bk_n500_0016 133896 134780 0.66 20 1.50 bk_n500_0017 132989 133391 0.30 20 1.95 bk_n500_0018 137392 137405 0.01 20 1.16 bk_n500_0019 110257 110493 0.21 20 1.15 dc932 479900 480216 0.07 50 50 amat1000.20 1675979 1675979 0.00 300 4.58 disk1000.20 46662510 55457400 18.8 300 2.41 ran1000.0 7897 9820 24.4 300 1.14 shop1000.20 1269796 1304450 2.73 300 17.2 super1000.20 5518 5693 3.17 300 4.75 tmat1000.20 1608953 1608950 0.66 300 2.76 amat3162.30 1635473 1635473 0.00 600 76.3 disk3162.30 90201591 90201600 0.00 600 41.0 shop3162.30 3810766 4205020 10.3 600 350 super3162.30 14313 14894 4.06 600 73.3 tmat3162.30 1570241 1724080 9.80 600 67.7 opt 0.00 ----------------------------------------------------------------------------- atex8 39982 40881 2.25 300 25.2 40055 0.18 coin1000.20 101560 102780 1.20 300 23.1 101920 0.35 crane1000.20 21992010 22460800 2.13 300 10.8 21992010 0.00 rect1000.20 29224170 29509700 0.98 300 24.9 29310722 0.30 rtilt1000.20 29224170 29862000 2.18 300 25.8 29241870 0.06 stilt1000.20 45917180 47715300 3.92 300 17.8 46009198 0.20 td1000.20 1242183 1242310 0.01 300 32.4 1242183 0.00 ----------------------------------------------------------------------------- coin3162.30 319340B 325120 1.81 600 500 320160 0.26 crane3162.30 38579543B 40422600 4.78 600 192 38579543 0.00 dk5325 814206 825017 1.33 600 600 817341 0.39 lawson5821 2588331B 2617270 1.12 600 600 2589633 0.05 rect3162.30 51178464B 51943800 1.50 600 502 51419128 0.47 rtilt3162.30 51176324B 54091900 5.70 600 507 51360210 0.36 stilt3162.30 81195160B 84310304 3.84 600 275 81481851 0.35 ----------------------------------------------------------------------------- Hexaly puts out 6 significant digits in floating point. They were filled with zeros in the above integers.
