Solving TSPLIB Instances
The file tspSolver/src/main/Main.java contains code that will run your solver on instances from the TSPLIB database. The main method of this class begins with
public static void main(String[] args) {
String[] problemNames = new String[]{"bier127","eil51","brd14051","ch130","ch150","d198", "d493","d657", "d1291","fl1400"};
String problemName = problemNames[1];
//...
Here the elements of problemNames are files in the directory sampleData/TSPLIB/ that existing code will parse for you into a problem instance. The number in the file name refers to the number of cities in the problem. You can adjust which problem is attempted by assigning a different value to problemName (by changing the index used to access problemNames, or if you prefer, typing in a file name manually). Try running your solver on a few different instances (start with smaller ones).
Performance degrades pretty quickly on larger problems. On my machine, d493 took over 6700 seconds to solve, and created over 370,000 nodes in branch and bound!
Interpreting CPLEX Output
When running the solver, the output generated by CPLEX is directed is printed out to the console. A complete explanation of what all of the output means can be found in the user manual here. We will explain the output as needed to motivate improvements to our TSP solver. Here is some sample output from d493.
Reading file d493... complete!
Building problem... complete!
Solving TSP...Lazy constraint(s) or lazy constraint callback is present.
Disabling dual reductions (CPX_PARAM_REDUCE) in presolve.
Disabling non-linear reductions (CPX_PARAM_PRELINEAR) in presolve.
Tried aggregator 1 time.
Presolve time = 0.10 sec. (61.44 ticks)
Warning: Control callbacks may disable some MIP features.
Probing time = 0.09 sec. (20.82 ticks)
MIP emphasis: balance optimality and feasibility.
MIP search method: traditional branch-and-cut.
Parallel mode: none, using 1 thread.
Root relaxation solution time = 0.11 sec. (90.76 ticks)
Nodes Cuts/
Node Left Objective IInf Best Integer Best Bound ItCnt Gap Variable B NodeID Parent Depth
0 0 32657.5000 90 32657.5000 804
0 0 32735.5000 72 Cuts: 29 861
0 0 32799.7500 74 Cuts: 19 892
0 0 32840.7500 93 Cuts: 19 916
0 0 32934.7500 103 Cuts: 21 954
0 0 32983.5000 87 ZeroHalf: 14 976
0 0 32998.0714 77 Cuts: 13 1005
0 0 33010.2000 103 Cuts: 7 1024
0 0 33011.7000 82 ZeroHalf: 5 1029
0 0 33011.8667 105 Cuts: 5 1033
0 0 33012.2000 93 ZeroHalf: 5 1049
0 0 33013.9222 94 Cuts: 5 1061
* 0+ 0 444886.0000 33013.9222 1061 92.58%
0 2 34654.1667 92 444886.0000 34661.6667 1061 92.21% 0 0
Elapsed time = 9.57 sec. (8450.32 ticks, tree = 0.00 MB, solutions = 1)
1 3 34661.6667 82 444886.0000 34662.6667 1063 92.21% x10596 U 1 0 1
3 5 34680.6667 76 444886.0000 34665.6667 1077 92.21% x140429 D 3 1 2
6 8 34703.1667 89 444886.0000 34665.6667 1098 92.21% x125223 U 6 5 5
10 12 34719.1667 87 444886.0000 34665.6667 1108 92.21% x169905 D 10 8 7
15 17 34723.6667 87 444886.0000 34665.6667 1118 92.21% x111476 D 15 14 12
19 21 34734.6667 87 444886.0000 34665.6667 1137 92.21% x235509 U 19 17 15
20 22 34743.6667 103 444886.0000 34665.6667 1145 92.21% x111610 D 20 19 16
25 27 34752.6667 109 444886.0000 34665.6667 1158 92.21% x71447 U 25 24 21
30 32 34761.6667 109 444886.0000 34665.6667 1166 92.21% x95237 D 30 29 26
48 50 34796.5000 50 444886.0000 34665.6667 1200 92.21% x101539 D 48 47 44
Elapsed time = 12.18 sec. (11998.79 ticks, tree = 1.96 MB, solutions = 1)
60 62 34838.2500 53 444886.0000 34665.6667 1233 92.21% x46240 D 60 59 55
79 81 34853.0000 54 444886.0000 34665.6667 1292 92.21% x46370 D 79 78 71
90 92 35103.0000 60 444886.0000 34665.6667 1308 92.21% x190044 D 90 89 82
100 102 35139.0000 62 444886.0000 34665.6667 1423 92.21% x83787 D 100 99 90
111 113 35312.2500 151 444886.0000 34665.6667 1524 92.21% x99125 U 111 109 100
120 122 35353.0000 61 444886.0000 34665.6667 1559 92.21% x54508 D 120 119 108
134 136 35363.1667 47 444886.0000 34665.6667 1618 92.21% x111729 D 134 133 120
144 146 35430.1667 67 444886.0000 34665.6667 1654 92.21% x15786 D 144 142 129
160 162 35442.5000 58 444886.0000 34665.6667 1692 92.21% x67378 D 160 159 144
176 178 35482.0000 58 444886.0000 34665.6667 1762 92.21% x145825 D 176 175 158
Elapsed time = 20.58 sec. (22475.92 ticks, tree = 8.60 MB, solutions = 1)
193 195 35525.5000 50 444886.0000 34665.6667 1796 92.21% x75047 D 193 192 174
202 204 35649.5000 75 444886.0000 34665.6667 1841 92.21% x58597 D 202 200 182
212 214 35634.2500 86 444886.0000 34665.6667 1921 92.21% x201915 U 212 210 189
229 231 35636.0000 36 444886.0000 34665.6667 1961 92.21% x89990 U 229 228 205
244 246 35676.0000 36 444886.0000 34665.6667 1997 92.21% x73429 U 244 242 218
260 262 35655.5000 54 444886.0000 34665.6667 2029 92.21% x115032 U 260 259 233
274 276 35672.5000 52 444886.0000 34665.6667 2057 92.21% x75046 U 274 273 247
290 292 35693.0000 46 444886.0000 34665.6667 2084 92.21% x17586 U 290 289 263
306 308 35722.0000 69 444886.0000 34665.6667 2143 92.21% x152012 D 306 305 276
316 318 35730.1250 120 444886.0000 34665.6667 2190 92.21% x23451 D 316 315 284
Elapsed time = 29.01 sec. (33260.54 ticks, tree = 16.24 MB, solutions = 1)
331 333 35954.0000 12 444886.0000 34665.6667 2303 92.21% x144170 D 331 330 297
346 348 35957.0000 18 444886.0000 34665.6667 2365 92.21% x66422 U 346 344 308
363 365 35968.5000 14 444886.0000 34665.6667 2423 92.21% x141633 D 363 362 323
380 382 35981.0000 14 444886.0000 34665.6667 2456 92.21% x203623 D 380 379 340
396 398 35994.0000 6 444886.0000 34665.6667 2497 92.21% x42012 D 396 395 355
412 414 36010.0000 6 444886.0000 34665.6667 2556 92.21% x60417 U 412 411 367
427 429 36042.0000 8 444886.0000 34665.6667 2606 92.21% x48189 D 427 426 378
442 444 36122.2500 65 444886.0000 34665.6667 2653 92.21% x119762 U 442 441 390
457 459 36277.5357 85 444886.0000 34665.6667 2756 92.21% x104189 D 457 456 404
478 480 36299.1250 55 444886.0000 34665.6667 2803 92.21% x61567 D 478 477 424
Elapsed time = 36.35 sec. (43155.02 ticks, tree = 25.13 MB, solutions = 1)
494 496 36315.5000 8 444886.0000 34665.6667 2859 92.21% x218809 U 494 493 438
510 512 36328.0000 8 444886.0000 34665.6667 2902 92.21% x119801 D 510 509 454
528 530 36492.0750 96 444886.0000 34665.6667 2956 92.21% x213855 D 528 527 471
539 541 36586.2500 64 444886.0000 34665.6667 3097 92.21% x220720 D 539 538 481
552 554 36749.5000 14 444886.0000 34665.6667 3168 92.21% x158876 D 552 551 492
565 567 36795.5000 68 444886.0000 34665.6667 3211 92.21% x132702 U 565 564 505
576 578 36801.0000 20 444886.0000 34665.6667 3248 92.21% x125998 U 576 575 515
590 592 36815.0000 18 444886.0000 34665.6667 3311 92.21% x205526 D 590 589 528
600 602 36824.6250 57 444886.0000 34665.6667 3355 92.21% x41827 D 600 599 537
616 618 36839.5000 10 444886.0000 34665.6667 3404 92.21% x44826 U 616 615 550
Elapsed time = 45.10 sec. (53518.53 ticks, tree = 32.82 MB, solutions = 1)
* 626 624 integral 0 36846.0000 34665.6667 3429 5.92% x189266 U 626 625 560
642 635 34906.0000 106 36846.0000 34675.6667 3606 5.89% x190487 U 642 640 11
659 652 34966.5000 116 36846.0000 34675.6667 3661 5.89% x74699 D 659 658 24
679 672 35025.5000 76 36846.0000 34675.6667 3709 5.89% x115407 D 679 678 43
694 687 35051.0000 76 36846.0000 34675.6667 3736 5.89% x75049 D 694 693 57
713 706 35076.5000 78 36846.0000 34675.6667 3759 5.89% x89990 U 713 712 76
726 719 35090.0000 74 36846.0000 34675.6667 3782 5.89% x204311 U 726 725 88
744 737 35167.5000 76 36846.0000 34675.6667 3894 5.89% x175305 D 744 743 100
760 753 35313.0000 78 36846.0000 34675.6667 3962 5.89% x32760 D 760 759 111
775 768 35372.5000 80 36846.0000 34675.6667 4027 5.89% x153203 D 775 774 121
Elapsed time = 53.05 sec. (63263.44 ticks, tree = 41.12 MB, solutions = 2)
787 780 35389.7500 139 36846.0000 34675.6667 4083 5.89% x3341 D 787 786 132
800 793 35412.0000 76 36846.0000 34675.6667 4123 5.89% x196405 D 800 798 142
813 806 35456.5000 76 36846.0000 34675.6667 4144 5.89% x191445 D 813 812 155
828 821 35470.5000 68 36846.0000 34675.6667 4176 5.89% x169002 D 828 827 168
841 834 35499.0000 66 36846.0000 34675.6667 4244 5.89% x161773 N 841 840 179
855 848 35530.0000 58 36846.0000 34675.6667 4292 5.89% x105681 D 855 854 189
869 862 35556.0000 60 36846.0000 34675.6667 4319 5.89% x104285 D 869 868 202
887 880 35597.0000 60 36846.0000 34675.6667 4344 5.89% x115032 U 887 886 220
903 896 35656.0000 62 36846.0000 34675.6667 4399 5.89% x232481 D 903 902 234
920 913 35694.0000 68 36846.0000 34675.6667 4437 5.89% x110909 D 920 919 251
Elapsed time = 61.12 sec. (73402.21 ticks, tree = 49.16 MB, solutions = 2)
937 930 35744.5000 72 36846.0000 34675.6667 4495 5.89% x145825 D 937 936 266
952 945 35769.0000 28 36846.0000 34675.6667 4555 5.89% x120432 U 952 950 279
966 953 34846.1667 136 36846.0000 34693.6667 4933 5.84% x199952 D 966 3 3
988 975 34945.5000 76 36846.0000 34705.1667 5130 5.81% x239030 U 988 986 21
1000 987 34981.5000 66 36846.0000 34705.1667 5183 5.81% x196405 U 1000 999 32
1017 1004 34918.5000 101 36846.0000 34710.6667 5392 5.80% x140346 D 1017 1016 21
1039 1026 34986.2500 80 36846.0000 34710.6667 5476 5.80% x132517 D 1039 1038 43
1060 1047 35121.0000 68 36846.0000 34710.6667 5559 5.80% x103685 U 1060 1059 64
1079 1066 35267.0000 66 36846.0000 34710.6667 5610 5.80% x175196 D 1079 1078 83
1093 1080 35290.5000 66 36846.0000 34710.6667 5683 5.80% x222350 D 1093 1092 97
Elapsed time = 69.56 sec. (84056.13 ticks, tree = 58.47 MB, solutions = 2)
1120 1107 35324.0000 6 36846.0000 34710.6667 5758 5.80% x221565 D 1120 1119 124
1133 1120 35408.1667 81 36846.0000 34710.6667 5795 5.80% x124438 D 1133 1132 137
1147 1134 35492.8333 75 36846.0000 34710.6667 5831 5.80% x54197 D 1147 1146 151
1163 1150 35627.6667 58 36846.0000 34710.6667 5899 5.80% x115615 D 1163 1162 167
1176 1163 35646.6667 58 36846.0000 34710.6667 5939 5.80% x144691 U 1176 1175 180
1193 1180 35690.6667 66 36846.0000 34710.6667 6004 5.80% x30487 D 1193 1192 197
1202 1189 34874.9167 137 36846.0000 34711.1667 6121 5.79% x30507 D 1202 7 6
1219 1206 34973.5000 96 36846.0000 34711.1667 6172 5.79% x105757 U 1219 1218 23
1235 1222 35082.1667 131 36846.0000 34711.1667 6262 5.79% x190448 D 1235 1234 39
1252 1239 35142.5000 68 36846.0000 34711.1667 6361 5.79% x93205 U 1252 1251 56
Elapsed time = 77.56 sec. (94034.81 ticks, tree = 67.37 MB, solutions = 2)
1277 1264 35247.5000 71 36846.0000 34711.1667 6445 5.79% x120432 D 1277 1276 81
...
...
374553 50385 cutoff 35002.0000 34998.0000 1922800 0.01% x180185 D 374553 374551 47
375000 50465 34998.5000 66 35002.0000 34998.0000 1924163 0.01% x121871 U 375000 374999 15
375404 50195 cutoff 35002.0000 34998.0000 1925424 0.01% x230899 U 375404 375402 34
375787 49842 cutoff 35002.0000 34998.0833 1926461 0.01% x41269 U 375787 165893 23
376158 49688 35000.0000 14 35002.0000 34998.2500 1927532 0.01% x11502 U 376158 376157 49
376558 49350 cutoff 35002.0000 34998.2500 1928948 0.01% x230899 D 376558 376557 31
Elapsed time = 6732.91 sec. (12435290.54 ticks, tree = 2690.91 MB, solutions = 15)
Nodefile size = 2560.74 MB (1100.24 MB after compression)
376932 49032 34998.5000 64 35002.0000 34998.3333 1930143 0.01% x102312 N 376932 161414 29
Cover cuts applied: 6
Zero-half cuts applied: 89
User cuts applied: 742
Root node processing (before b&c):
Real time = 13.13 sec. (11373.68 ticks)
Sequential b&c:
Real time = 6735.83 sec. (12525783.50 ticks)
------------
Total (root+branch&cut) = 6748.96 sec. (12537157.18 ticks)
complete!
opt is: 35002.0