Weak LP Relaxation - Best Bound Does Not Improve

I'm working on an Asymmetric Traveling Salesman Problem (ATSPP) variant where the objective is to minimize the total revisit span rather than travel time. The problem involves visiting nodes (start terminal > ‘link clusters’ > end terminal) on a street network, where some link cluster nodes form pairs on opposite sides of the same street. The revisit span measures the time difference between visiting the link cluster pairs.

These are the basic TSP constraints that I am using:

Besides these basic constraints, I have implemented arrival time propagation constraints using arc-specific bigMs as well as the linearisation of the revisit span.

which is notated in mathematical formulation as (where Ei is the earliest arrival time, Li the latest arrival time):

If i run this on a 30 node problem, the best bound does not improve anymore. I have added the output logs at the end of this message. Which parameter settings are recommended to improve this? And are there any other formulations possible to improve this?

Set parameter TimeLimit to value 900
Gurobi Optimizer version 12.0.3 build v12.0.3rc0 (win64 - Windows 11+.0 (26200.2))

CPU model: Intel(R) Core(TM) i7-8650U CPU @ 1.90GHz, instruction set [SSE2|AVX|AVX2]
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads

Non-default parameters:
TimeLimit 900

Optimize a model with 3021 rows, 1075 columns and 10819 nonzeros
Model fingerprint: 0x67f3d9f2
Model has 8 simple general constraints
8 ABS
Variable types: 82 continuous, 993 integer (993 binary)
Coefficient statistics:
Matrix range [1e+00, 9e+03]
Objective range [1e+00, 1e+00]
Bounds range [1e+00, 1e+04]
RHS range [1e+00, 1e+04]
Presolve added 0 rows and 20 columns
Presolve removed 14 rows and 0 columns
Presolve time: 0.06s
Presolved: 3007 rows, 1095 columns, 10714 nonzeros
Variable types: 95 continuous, 1000 integer (1000 binary)
Found heuristic solution: objective 4114.0000000
Found heuristic solution: objective 3330.0000000

Root relaxation: objective 8.020000e+02, 404 iterations, 0.01 seconds (0.01 work units)

0 0 802.00000 0 23 3330.00000 802.00000 75.9% - 0s
0 0 802.00000 0 75 3330.00000 802.00000 75.9% - 0s
0 0 802.00000 0 64 3330.00000 802.00000 75.9% - 0s
H 0 0 3129.0000000 802.00000 74.4% - 0s
0 0 802.00000 0 22 3129.00000 802.00000 74.4% - 0s
0 0 802.00000 0 24 3129.00000 802.00000 74.4% - 0s
H 0 0 3076.0000000 802.00000 73.9% - 0s
0 0 802.00000 0 26 3076.00000 802.00000 73.9% - 1s
0 0 802.00000 0 23 3076.00000 802.00000 73.9% - 1s
0 0 802.00000 0 21 3076.00000 802.00000 73.9% - 1s
H 0 0 3129.0000000 802.00000 74.4% - 0s
0 0 802.00000 0 22 3129.00000 802.00000 74.4% - 0s
0 0 802.00000 0 24 3129.00000 802.00000 74.4% - 0s
H 0 0 3129.0000000 802.00000 74.4% - 0s
0 0 802.00000 0 22 3129.00000 802.00000 74.4% - 0s
0 0 802.00000 0 24 3129.00000 802.00000 74.4% - 0s
H 0 0 3129.0000000 802.00000 74.4% - 0s
0 0 802.00000 0 22 3129.00000 802.00000 74.4% - 0s
H 0 0 3129.0000000 802.00000 74.4% - 0s
H 0 0 3129.0000000 802.00000 74.4% - 0s
0 0 802.00000 0 22 3129.00000 802.00000 74.4% - 0s
0 0 802.00000 0 24 3129.00000 802.00000 74.4% - 0s
H 0 0 3076.0000000 802.00000 73.9% - 0s
0 0 802.00000 0 26 3076.00000 802.00000 73.9% - 1s
0 0 802.00000 0 23 3076.00000 802.00000 73.9% - 1s
0 0 802.00000 0 21 3076.00000 802.00000 73.9% - 1s
0 0 802.00000 0 51 3076.00000 802.00000 73.9% - 1s
0 0 802.00000 0 25 3076.00000 802.00000 73.9% - 1s
0 0 802.00000 0 24 3076.00000 802.00000 73.9% - 1s
0 0 802.00000 0 23 3076.00000 802.00000 73.9% - 1s
0 0 802.00000 0 23 3076.00000 802.00000 73.9% - 1s
H 0 0 2643.0000000 802.00000 69.7% - 2s
0 2 802.00000 0 22 2643.00000 802.00000 69.7% - 2s
0 0 802.00000 0 23 3076.00000 802.00000 73.9% - 1s
0 0 802.00000 0 23 3076.00000 802.00000 73.9% - 1s
H 0 0 2643.0000000 802.00000 69.7% - 2s
0 2 802.00000 0 22 2643.00000 802.00000 69.7% - 2s
H 172 173 2009.0000000 802.00000 60.1% 41.7 2s
H 249 324 1763.0000000 802.00000 54.5% 34.1 3s
H 354 324 1726.0000000 802.00000 53.5% 29.6 3s
1089 955 802.00000 61 51 1726.00000 802.00000 53.5% 27.5 5s
1644 967 1419.00000 53 25 1726.00000 802.00000 53.5% 25.5 10s
H 1645 919 1427.0000000 802.00000 43.8% 25.5 11s
1769 1010 802.00000 22 29 1427.00000 802.00000 43.8% 41.0 15s
2159 2007 802.00000 45 38 1427.00000 802.00000 43.8% 41.5 21s
1089 955 802.00000 61 51 1726.00000 802.00000 53.5% 27.5 5s
1644 967 1419.00000 53 25 1726.00000 802.00000 53.5% 25.5 10s
1089 955 802.00000 61 51 1726.00000 802.00000 53.5% 27.5 5s
1644 967 1419.00000 53 25 1726.00000 802.00000 53.5% 25.5 10s
H 1645 919 1427.0000000 802.00000 43.8% 25.5 11s
H 1645 919 1427.0000000 802.00000 43.8% 25.5 11s
1769 1010 802.00000 22 29 1427.00000 802.00000 43.8% 41.0 15s
2159 2007 802.00000 45 38 1427.00000 802.00000 43.8% 41.5 21s
3186 1763 821.00000 65 34 1427.00000 802.00000 43.8% 43.6 25s
H 3307 2246 1421.0000000 802.00000 43.6% 43.4 26s
H 3893 1961 1181.0000000 802.00000 32.1% 42.2 26s
5319 3327 802.00000 112 27 1181.00000 802.00000 32.1% 38.8 30s
12048 6942 infeasible 205 1181.00000 802.00000 32.1% 26.8 35s
14913 8902 802.00000 47 39 1181.00000 802.00000 32.1% 25.1 40s
H17495 8017 950.0000000 802.00000 15.6% 23.6 41s
19403 9122 infeasible 156 950.00000 802.00000 15.6% 22.7 45s
H19405 8274 883.0000000 802.00000 9.17% 22.7 45s
24734 10677 802.00000 81 34 883.00000 802.00000 9.17% 21.4 50s
29301 13414 802.00000 172 31 883.00000 802.00000 9.17% 20.4 63s
29933 14280 infeasible 113 883.00000 802.00000 9.17% 20.5 65s
33764 14354 802.00000 117 32 883.00000 802.00000 9.17% 19.8 70s
39249 15943 802.00000 170 50 883.00000 802.00000 9.17% 19.1 75s
44218 18243 802.00000 133 26 883.00000 802.00000 9.17% 18.6 81s
53084 18614 802.00000 137 33 883.00000 802.00000 9.17% 17.7 85s
56575 19897 802.00000 122 27 883.00000 802.00000 9.17% 17.7 90s
57214 20184 872.00000 158 26 883.00000 802.00000 9.17% 18.0 95s
63604 22777 823.00000 69 20 883.00000 802.00000 9.17% 17.6 100s
70591 24404 infeasible 102 883.00000 802.00000 9.17% 17.4 105s
70736 24536 802.00000 93 37 883.00000 802.00000 9.17% 17.5 110s
74192 25488 815.00000 113 25 883.00000 802.00000 9.17% 17.6 116s
74192 25488 815.00000 113 25 883.00000 802.00000 9.17% 17.6 116s
74696 25663 infeasible 106 883.00000 802.00000 9.17% 17.7 122s
75430 27095 802.00000 134 27 883.00000 802.00000 9.17% 18.0 125s
88372 27810 infeasible 131 883.00000 802.00000 9.17% 17.2 130s
96491 28367 infeasible 134 883.00000 802.00000 9.17% 16.9 135s
H96757 28174 877.0000000 802.00000 8.55% 17.0 136s
99297 29792 802.00000 94 29 877.00000 802.00000 8.55% 17.1 140s
103305 32725 802.00000 133 26 877.00000 802.00000 8.55% 17.0 146s
111916 33941 802.00000 184 33 877.00000 802.00000 8.55% 16.8 150s
117327 35673 802.00000 107 28 877.00000 802.00000 8.55% 16.5 155s
123521 36996 802.00000 162 28 877.00000 802.00000 8.55% 16.3 160s
123805 37067 802.00000 171 23 877.00000 802.00000 8.55% 16.4 165s
127833 38353 802.00000 86 23 877.00000 802.00000 8.55% 16.4 170s
133306 39081 infeasible 109 877.00000 802.00000 8.55% 16.3 175s
137448 39621 802.00000 72 33 877.00000 802.00000 8.55% 16.2 180s
139143 39839 infeasible 129 877.00000 802.00000 8.55% 16.3 185s
143301 40537 802.00000 129 30 877.00000 802.00000 8.55% 16.3 190s
147683 41744 833.12619 145 26 877.00000 802.00000 8.55% 16.3 195s
149386 42851 802.00000 70 29 877.00000 802.00000 8.55% 16.2 201s
158137 43952 802.00000 76 27 877.00000 802.00000 8.55% 16.3 205s
162175 44834 infeasible 84 877.00000 802.00000 8.55% 16.3 210s
165343 46271 infeasible 114 877.00000 802.00000 8.55% 16.3 217s
173532 46280 cutoff 96 877.00000 802.00000 8.55% 16.2 220s
173678 46291 802.00000 110 35 877.00000 802.00000 8.55% 16.2 225s
173916 46285 808.00000 116 28 877.00000 802.00000 8.55% 16.2 230s
174675 46555 802.00000 79 25 877.00000 802.00000 8.55% 16.3 235s
176961 47685 841.00000 129 17 877.00000 802.00000 8.55% 16.4 240s
180308 49498 infeasible 102 877.00000 802.00000 8.55% 16.4 247s
188613 49459 infeasible 115 877.00000 802.00000 8.55% 16.2 250s
191321 49978 802.00000 93 26 877.00000 802.00000 8.55% 16.2 255s
194368 50751 infeasible 133 877.00000 802.00000 8.55% 16.2 260s
199497 51864 infeasible 125 877.00000 802.00000 8.55% 16.2 265s
205203 53417 802.00000 135 24 877.00000 802.00000 8.55% 16.2 270s
209851 54780 802.00000 145 20 877.00000 802.00000 8.55% 16.2 275s
217180 55989 infeasible 146 877.00000 802.00000 8.55% 16.1 280s
222511 57566 infeasible 142 877.00000 802.00000 8.55% 16.1 285s
223053 57972 833.00000 136 30 877.00000 802.00000 8.55% 16.2 290s
231877 59870 infeasible 122 877.00000 802.00000 8.55% 16.2 295s
235249 60685 802.00000 99 25 877.00000 802.00000 8.55% 16.2 300s
239619 62528 802.00000 151 25 877.00000 802.00000 8.55% 16.3 306s
247090 63032 809.00000 165 27 877.00000 802.00000 8.55% 16.3 310s
252029 63680 802.00000 124 31 877.00000 802.00000 8.55% 16.3 315s
253152 63770 802.00000 133 27 877.00000 802.00000 8.55% 16.4 320s
259423 64098 802.00000 145 29 877.00000 802.00000 8.55% 16.4 325s
264632 66008 802.00000 103 27 877.00000 802.00000 8.55% 16.4 330s
269779 67520 infeasible 130 877.00000 802.00000 8.55% 16.3 337s
276578 67508 infeasible 125 877.00000 802.00000 8.55% 16.2 340s
276799 67505 802.00000 84 31 877.00000 802.00000 8.55% 16.2 345s
277769 67524 802.00000 98 24 877.00000 802.00000 8.55% 16.3 350s
278559 67979 848.00000 139 24 877.00000 802.00000 8.55% 16.4 355s
284290 68312 infeasible 94 877.00000 802.00000 8.55% 16.3 360s
292474 68997 817.00000 82 24 877.00000 802.00000 8.55% 16.2 365s
296754 69553 802.00000 115 24 877.00000 802.00000 8.55% 16.2 370s
299566 70951 802.00000 105 32 877.00000 802.00000 8.55% 16.3 377s
306832 70914 infeasible 107 877.00000 802.00000 8.55% 16.1 380s
311375 71633 802.00000 80 28 877.00000 802.00000 8.55% 16.1 385s
316068 72023 802.00000 105 27 877.00000 802.00000 8.55% 16.1 390s
319620 72647 802.00000 78 28 877.00000 802.00000 8.55% 16.1 395s
322432 73198 804.00000 88 27 877.00000 802.00000 8.55% 16.1 400s
326572 74025 infeasible 100 877.00000 802.00000 8.55% 16.1 405s
326950 74091 802.00000 124 27 877.00000 802.00000 8.55% 16.2 410s
328501 74586 802.00000 90 29 877.00000 802.00000 8.55% 16.2 438s
333954 75956 848.00000 122 22 877.00000 802.00000 8.55% 16.5 443s
341937 75959 802.00000 93 24 877.00000 802.00000 8.55% 16.4 445s
342008 76202 802.00000 93 28 877.00000 802.00000 8.55% 16.4 450s
347666 76757 802.00000 86 29 877.00000 802.00000 8.55% 16.3 455s
352731 77419 infeasible 92 877.00000 802.00000 8.55% 16.3 460s
356438 78168 802.00000 90 24 877.00000 802.00000 8.55% 16.3 465s
358032 78828 802.00000 79 34 877.00000 802.00000 8.55% 16.3 470s
363299 79180 802.00000 94 28 877.00000 802.00000 8.55% 16.3 475s
368270 79966 infeasible 103 877.00000 802.00000 8.55% 16.3 480s
371661 80905 802.00000 85 28 877.00000 802.00000 8.55% 16.3 485s
376609 81449 802.00000 112 24 877.00000 802.00000 8.55% 16.2 490s
380376 82081 infeasible 110 877.00000 802.00000 8.55% 16.2 495s
385448 83370 802.00000 122 28 877.00000 802.00000 8.55% 16.2 500s
388056 83826 infeasible 117 877.00000 802.00000 8.55% 16.2 513s
395910 83974 802.00000 78 27 877.00000 802.00000 8.55% 16.3 515s
402832 84908 infeasible 139 877.00000 802.00000 8.55% 16.2 520s
402999 85218 802.00000 108 28 877.00000 802.00000 8.55% 16.2 525s
409695 85519 802.00000 71 34 877.00000 802.00000 8.55% 16.2 530s
412813 86417 802.00000 101 22 877.00000 802.00000 8.55% 16.2 535s
418145 87542 infeasible 106 877.00000 802.00000 8.55% 16.2 540s
425232 89100 infeasible 128 877.00000 802.00000 8.55% 16.1 545s
430303 90407 infeasible 84 877.00000 802.00000 8.55% 16.1 550s
432825 91949 802.00000 135 23 877.00000 802.00000 8.55% 16.2 556s
440455 91918 infeasible 137 877.00000 802.00000 8.55% 16.1 560s
442241 92156 infeasible 134 877.00000 802.00000 8.55% 16.1 565s
444469 92833 infeasible 93 877.00000 802.00000 8.55% 16.2 570s
444570 92841 802.00000 128 32 877.00000 802.00000 8.55% 16.2 575s
444896 92918 infeasible 103 877.00000 802.00000 8.55% 16.2 580s
445944 93056 845.00000 130 29 877.00000 802.00000 8.55% 16.3 585s
448364 94456 802.00000 86 23 877.00000 802.00000 8.55% 16.3 590s
455547 94426 infeasible 90 877.00000 802.00000 8.55% 16.2 595s
457785 95093 802.00000 94 30 877.00000 802.00000 8.55% 16.3 600s
462515 96256 infeasible 116 877.00000 802.00000 8.55% 16.3 605s
467745 96854 802.00000 97 24 877.00000 802.00000 8.55% 16.2 610s
473370 98790 813.00000 140 25 877.00000 802.00000 8.55% 16.3 615s
477953 99681 infeasible 141 877.00000 802.00000 8.55% 16.3 620s
483985 101231 802.00000 138 22 877.00000 802.00000 8.55% 16.2 625s
488551 101778 infeasible 137 877.00000 802.00000 8.55% 16.2 630s
490189 102329 802.00000 123 26 877.00000 802.00000 8.55% 16.3 635s
495057 104410 infeasible 107 877.00000 802.00000 8.55% 16.2 640s
498719 105675 infeasible 145 877.00000 802.00000 8.55% 16.2 645s
503454 106913 802.00000 118 28 877.00000 802.00000 8.55% 16.2 650s
509628 108034 infeasible 106 877.00000 802.00000 8.55% 16.2 655s
513281 109153 874.00000 81 17 877.00000 802.00000 8.55% 16.2 660s
516694 110000 802.00000 102 24 877.00000 802.00000 8.55% 16.2 665s
519450 110244 802.00000 96 28 877.00000 802.00000 8.55% 16.2 670s
522141 110947 infeasible 108 877.00000 802.00000 8.55% 16.2 675s
527703 112773 802.00000 111 30 877.00000 802.00000 8.55% 16.1 680s
532414 113908 802.00000 120 32 877.00000 802.00000 8.55% 16.2 685s
536203 114795 infeasible 124 877.00000 802.00000 8.55% 16.2 690s
537942 115734 802.00000 93 24 877.00000 802.00000 8.55% 16.2 695s
544987 115766 infeasible 96 877.00000 802.00000 8.55% 16.1 700s
545660 115809 802.00000 102 25 877.00000 802.00000 8.55% 16.2 705s
548992 116457 802.00000 85 22 877.00000 802.00000 8.55% 16.2 710s
552692 117540 848.00000 116 23 877.00000 802.00000 8.55% 16.2 717s
559612 117473 802.00000 79 29 877.00000 802.00000 8.55% 16.1 720s
560083 117644 802.00000 79 35 877.00000 802.00000 8.55% 16.1 725s
563477 118358 802.00000 115 31 877.00000 802.00000 8.55% 16.1 731s
563560 118395 802.00000 120 26 877.00000 802.00000 8.55% 16.1 735s
563773 118421 802.00000 122 31 877.00000 802.00000 8.55% 16.2 740s
564499 118664 802.00000 89 28 877.00000 802.00000 8.55% 16.2 745s
567394 119306 infeasible 98 877.00000 802.00000 8.55% 16.2 750s
572981 120558 802.00000 113 26 877.00000 802.00000 8.55% 16.2 755s
577119 121572 cutoff 114 877.00000 802.00000 8.55% 16.1 760s
582010 122018 infeasible 138 877.00000 802.00000 8.55% 16.1 765s
582162 122319 802.00000 58 43 877.00000 802.00000 8.55% 16.1 770s
588586 123053 802.00000 79 30 877.00000 802.00000 8.55% 16.1 775s
594002 124108 802.00000 77 33 877.00000 802.00000 8.55% 16.1 780s
597420 124764 802.00000 87 26 877.00000 802.00000 8.55% 16.1 785s
598844 124865 802.00000 85 25 877.00000 802.00000 8.55% 16.1 790s
599155 125018 802.00000 92 33 877.00000 802.00000 8.55% 16.1 795s
602455 126718 802.00000 82 27 877.00000 802.00000 8.55% 16.2 800s
608127 128274 infeasible 157 877.00000 802.00000 8.55% 16.2 805s
612788 129339 infeasible 199 877.00000 802.00000 8.55% 16.2 811s
613002 129346 infeasible 185 877.00000 802.00000 8.55% 16.2 815s
613011 129338 802.00000 154 28 877.00000 802.00000 8.55% 16.2 820s
613034 129369 802.00995 155 30 877.00000 802.00000 8.55% 16.2 827s
613826 129433 842.00000 165 20 877.00000 802.00000 8.55% 16.2 834s
615039 130428 802.00000 153 34 877.00000 802.00000 8.55% 16.3 840s
621355 130417 814.00000 146 28 877.00000 802.00000 8.55% 16.3 846s
624815 131447 802.00000 178 23 877.00000 802.00000 8.55% 16.3 850s
627513 131568 802.00000 153 30 877.00000 802.00000 8.55% 16.3 856s
631497 131628 infeasible 151 877.00000 802.00000 8.55% 16.4 860s
632196 132172 808.00000 140 24 877.00000 802.00000 8.55% 16.4 866s
637904 132556 808.01896 170 26 877.00000 802.00000 8.55% 16.4 871s
642526 132770 infeasible 204 877.00000 802.00000 8.55% 16.4 876s
642753 133574 802.00000 172 27 877.00000 802.00000 8.55% 16.4 880s
651543 133488 860.93667 178 14 877.00000 802.00000 8.55% 16.4 885s
653944 133571 infeasible 140 877.00000 802.00000 8.55% 16.4 890s
656837 133675 infeasible 142 877.00000 802.00000 8.55% 16.5 895s
658368 134301 infeasible 150 877.00000 802.00000 8.55% 16.5 900s

Cutting planes:
Gomory: 3
Implied bound: 13
Projected implied bound: 2
Mixing: 1
Flow cover: 18
RLT: 1
Relax-and-lift: 4

Explored 664235 nodes (10932573 simplex iterations) in 900.60 seconds (574.73 work units)
Thread count was 8 (of 8 available processors)

Solution count 10: 877 883 950 ... 2643

Weak LP Relaxation - Best Bound Does Not Improve

Comments

Didn't find what you were looking for?