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
|