Optimization Performance - Capacitated Vehicle Routing Problem
AnsweredGood Day,
I am currently in the process of modeling a multi-depot location routing problem.
Following is the objective function
Constraints:
Short Variable Explanation:
I have successfully implemented the model using gurobipy in a jupyter notebook environment. For testing purposes I initially used the actual Distances/Travel Times for Cij and Tij in meters/seconds instead of multiplying with a cost-factor before optimization.
When using actual Distances/Travel Times, which are between 0-10.000 meters and 0-700 seconds, the model can be optimized within a few minutes for small instances (25 Customers/ 2 Potential DCs). However once I multiply the Distances/Travel Times with an appropriate cost-factor of e.g. 0.004$ per second of travel time and 0.00025$ per meter of distance the model will get stuck at a large %-Gap for an identical configuration (I have verified this behavior by running the model numerous times).
For reference here are two identical instances of the optimization process
- Using Actual Distances/Travel Times without multiplying by the cost factor before optimization
Gurobi 9.1.2 (win64) logging started Thu Oct 28 15:09:44 2021
Changed value of parameter LogFile to gurobi_log50.log
Prev: Default:
Changed value of parameter MIPGap to 0.1
Prev: 0.0001 Min: 0.0 Max: inf Default: 0.0001
Gurobi Optimizer version 9.1.2 build v9.1.2rc0 (win64)
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 2064 rows, 2314 columns and 21814 nonzeros
Model fingerprint: 0x949f7f1d
Variable types: 75 continuous, 2239 integer (2239 binary)
Coefficient statistics:
Matrix range [1e+00, 1e+02]
Objective range [6e+01, 2e+04]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 8e+01]
Presolve removed 0 rows and 81 columns
Presolve time: 0.02s
Presolved: 2064 rows, 2233 columns, 21514 nonzeros
Variable types: 75 continuous, 2158 integer (2158 binary)
Root relaxation: objective 4.632260e+04, 145 iterations, 0.00 seconds
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 46322.6000 0 54 - 46322.6000 - - 0s
0 0 47063.4520 0 57 - 47063.4520 - - 0s
0 0 53244.6000 0 63 - 53244.6000 - - 0s
0 0 53244.6000 0 63 - 53244.6000 - - 0s
0 0 61707.1496 0 71 - 61707.1496 - - 0s
0 0 62562.1000 0 52 - 62562.1000 - - 0s
0 0 62562.1000 0 52 - 62562.1000 - - 0s
H 0 0 100723.80000 62562.1000 37.9% - 0s
0 0 62562.1000 0 52 100723.800 62562.1000 37.9% - 0s
H 0 0 99338.300000 62562.1000 37.0% - 0s
H 0 0 92926.900000 62562.1000 32.7% - 0s
H 0 0 92892.900000 62562.1000 32.7% - 0s
0 0 62562.1000 0 52 92892.9000 62562.1000 32.7% - 0s
0 0 62562.1000 0 42 92892.9000 62562.1000 32.7% - 0s
H 0 2 91902.400000 62647.1860 31.8% - 0s
0 2 62647.1860 0 42 91902.4000 62647.1860 31.8% - 0s
H 111 114 88943.400000 62916.1000 29.3% 17.3 0s
H 112 114 87610.500000 62916.1000 28.2% 17.3 0s
H 114 118 82040.300000 62916.1000 23.3% 17.2 1s
H 1051 861 81085.600000 62942.1800 22.4% 13.7 2s
H 1051 818 80569.100000 62942.1800 21.9% 13.7 2s
H 1062 783 78972.000000 63300.0300 19.8% 13.6 3s
H 1063 745 78657.200000 63373.5656 19.4% 13.5 3s
H 1067 710 76784.800000 63441.0000 17.4% 13.5 3s
H 1069 675 76738.400000 63569.7000 17.2% 13.5 4s
1084 685 67741.6000 35 104 76738.4000 65368.2655 14.8% 13.3 5s
1133 718 72944.3313 76 190 76738.4000 66137.1520 13.8% 12.7 10s
1173 749 66286.8255 31 157 76738.4000 66286.8255 13.6% 25.2 15s
H 1336 814 76290.000000 66371.7585 13.0% 31.2 16s
4188 2109 71280.0240 68 25 76290.0000 66665.7227 12.6% 32.4 20s
7428 4251 67738.2593 50 43 76290.0000 66798.2880 12.4% 32.3 25s
11607 6935 67923.8839 55 119 76290.0000 66896.1911 12.3% 33.4 30s
15746 9498 69828.7851 51 50 76290.0000 66973.7249 12.2% 33.2 35s
19100 11625 67443.5028 53 83 76290.0000 67012.3180 12.2% 33.2 40s
20836 12338 74188.1803 51 42 76290.0000 67030.0280 12.1% 33.0 48s
20851 12348 70360.9796 69 168 76290.0000 67030.0280 12.1% 33.0 50s
20864 12357 75970.3429 77 166 76290.0000 67030.0280 12.1% 33.0 55s
20874 12363 67465.4804 39 173 76290.0000 67030.0280 12.1% 32.9 60s
20886 12371 70774.2440 59 61 76290.0000 67030.0280 12.1% 32.9 65s
H20948 11795 76016.400000 67030.0280 11.8% 33.5 68s
21330 11956 67030.0280 61 57 76016.4000 67030.0280 11.8% 33.4 70s
23862 13021 73877.2209 166 81 76016.4000 67030.0280 11.8% 32.4 75s
28631 15134 73081.7545 156 95 76016.4000 67030.4837 11.8% 30.9 80s
H33860 16574 76016.399976 67176.6455 11.6% 29.3 84s
33907 16810 cutoff 156 76016.4000 67185.6275 11.6% 29.2 85s
H34730 16379 76016.399387 67221.5602 11.6% 29.1 86s
H34854 15806 76016.399238 67221.7200 11.6% 29.0 86s
38839 17737 74129.2171 92 51 76016.3992 67307.9572 11.5% 28.4 90s
44847 19729 cutoff 148 76016.3992 67409.4294 11.3% 27.7 95s
*48468 20166 97 75744.500000 67458.7118 10.9% 27.3 97s
*50098 20763 125 75577.200000 67482.5964 10.7% 27.1 99s
H50527 19595 74536.700000 67490.6780 9.45% 27.1 99s
Cutting planes:
Gomory: 46
Cover: 11
Clique: 1
MIR: 56
Flow cover: 269
Inf proof: 17
Zero half: 77
Mod-K: 1
RLT: 104
Explored 50684 nodes (1374021 simplex iterations) in 99.46 seconds
Thread count was 8 (of 8 available processors)
Solution count 10: 74536.7 75577.2 75744.5 ... 80569.1
Optimal solution found (tolerance 1.00e-01)
Best objective 7.453670000000e+04, best bound 6.749356000000e+04, gap 9.4492%
- Distances/Travel Times multiplied with the appropriate cost factor
Gurobi 9.1.2 (win64) logging started Thu Oct 28 14:57:08 2021
Changed value of parameter LogFile to gurobi_log50.log
Prev: Default:
Changed value of parameter MIPGap to 0.1
Prev: 0.0001 Min: 0.0 Max: inf Default: 0.0001
Gurobi Optimizer version 9.1.2 build v9.1.2rc0 (win64)
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 2064 rows, 2314 columns and 21814 nonzeros
Model fingerprint: 0x533110bb
Variable types: 75 continuous, 2239 integer (2239 binary)
Coefficient statistics:
Matrix range [1e+00, 1e+02]
Objective range [5e+00, 2e+02]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 8e+01]
Presolve removed 0 rows and 81 columns
Presolve time: 0.02s
Presolved: 2064 rows, 2233 columns, 21514 nonzeros
Variable types: 75 continuous, 2158 integer (2158 binary)
Root relaxation: objective 1.513410e+02, 146 iterations, 0.00 seconds
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 151.34100 0 50 - 151.34100 - - 0s
0 0 151.59112 0 53 - 151.59112 - - 0s
0 0 154.46750 0 50 - 154.46750 - - 0s
0 0 159.46300 0 50 - 159.46300 - - 0s
0 0 159.46300 0 50 - 159.46300 - - 0s
0 0 159.46300 0 50 - 159.46300 - - 0s
H 0 0 2201.9120000 159.46300 92.8% - 0s
0 0 159.46300 0 50 2201.91200 159.46300 92.8% - 0s
0 0 159.46300 0 50 2201.91200 159.46300 92.8% - 0s
H 0 2 2191.7760000 159.49900 92.7% - 0s
0 2 159.49900 0 50 2191.77600 159.49900 92.7% - 0s
H 29 34 2177.2390000 159.49900 92.7% 20.0 0s
H 31 34 2177.0600000 159.49900 92.7% 20.3 0s
H 32 34 2170.7900000 159.55596 92.6% 19.8 0s
H 391 366 2143.5560000 159.58214 92.6% 18.7 1s
H 407 370 2142.4290000 159.58214 92.6% 18.6 1s
H 409 370 2136.1350000 159.58214 92.5% 18.6 1s
H 410 384 2115.8420000 159.58214 92.5% 18.6 1s
H 417 384 2110.4620000 159.58214 92.4% 18.6 1s
H 436 384 2091.0830000 159.58214 92.4% 17.9 1s
H 708 612 2085.9630000 159.58475 92.3% 17.7 1s
H 710 612 2074.2910000 159.58475 92.3% 17.7 1s
H 711 612 2072.9260000 159.58475 92.3% 17.7 1s
H 1048 847 2071.5300000 159.58475 92.3% 17.3 2s
H 1053 807 2071.0740000 159.58475 92.3% 17.3 2s
H 1053 767 2070.1840000 159.58475 92.3% 17.3 2s
H 1063 735 2069.5240000 160.00450 92.3% 17.1 3s
H 1067 700 2067.7230000 160.16344 92.3% 17.0 3s
H 1082 674 2067.7150000 160.75656 92.2% 16.8 3s
H 1091 645 2061.8550000 160.96948 92.2% 16.7 4s
H 1092 613 2060.8220000 160.97580 92.2% 16.7 4s
H 1097 584 2060.4560000 160.98737 92.2% 16.6 4s
1101 587 163.09191 56 89 2060.45600 160.98928 92.2% 16.5 5s
H 1122 572 2058.8180000 161.09683 92.2% 21.7 6s
H 1133 550 2057.9650000 161.09683 92.2% 21.5 7s
1158 567 165.55247 48 90 2057.96500 161.13243 92.2% 21.0 10s
H 1192 562 2057.4780000 161.13500 92.2% 24.8 11s
H 1223 558 2057.0010000 161.13500 92.2% 24.9 11s
H 1225 531 2056.9080000 161.13500 92.2% 24.9 11s
H 1754 765 2055.8770000 161.13514 92.2% 23.5 12s
H 3341 1828 2055.6730000 161.13805 92.2% 22.3 13s
4621 2832 1853.90833 187 18 2055.67300 161.14796 92.2% 21.1 15s
H 4622 2832 2055.6380000 161.14796 92.2% 21.1 15s
12023 9165 862.57916 117 10 2055.63800 161.16991 92.2% 19.5 20s
18727 14647 171.71013 170 56 2055.63800 161.17872 92.2% 19.0 25s
21147 16105 1233.05272 125 50 2055.63800 161.18387 92.2% 18.7 31s
21167 16118 167.15636 85 65 2055.63800 161.18387 92.2% 18.7 35s
21788 16571 1014.97056 134 27 2055.63800 161.18387 92.2% 19.1 40s
28169 19846 172.75833 206 32 2055.63800 161.27895 92.2% 18.6 45s
40738 24992 165.02141 77 20 2055.63800 161.34233 92.2% 17.6 50s
51209 30381 315.14872 121 37 2055.63800 161.36360 92.2% 16.8 55s
63146 36115 171.13904 115 16 2055.63800 161.37944 92.1% 16.3 60s
73824 42020 162.33726 65 46 2055.63800 161.39099 92.1% 16.0 65s
H87811 53572 2055.6379425 161.40051 92.1% 15.7 70s
99703 63614 161.98704 70 44 2055.63794 161.40973 92.1% 15.6 75s
110454 72182 163.31504 102 18 2055.63794 161.41622 92.1% 15.4 80s
H117937 78482 2055.6375572 161.42022 92.1% 15.3 83s
121684 82194 161.52045 75 18 2055.63756 161.42437 92.1% 15.3 85s
131036 90187 165.29900 109 33 2055.63756 161.42923 92.1% 15.1 90s
142975 99765 168.81857 171 32 2055.63756 161.43775 92.1% 15.1 95s
155188 110191 168.53298 110 31 2055.63756 161.44455 92.1% 15.1 100s
165640 119166 162.67060 78 20 2055.63756 161.45043 92.1% 15.0 105s
177491 128572 161.76003 75 48 2055.63756 161.45711 92.1% 15.0 110s
H184117 134450 2055.6373979 161.46100 92.1% 15.0 113s
188351 138046 177.33022 203 22 2055.63740 161.46300 92.1% 15.0 115s
197667 145697 164.19525 97 27 2055.63740 161.46826 92.1% 15.0 120s
206760 153541 161.57296 68 41 2055.63740 161.47495 92.1% 14.9 125s
217341 162606 163.63732 70 40 2055.63740 161.47950 92.1% 14.9 130s
226602 170148 168.88089 234 31 2055.63740 161.48316 92.1% 14.9 135s
236835 178946 876.77114 172 14 2055.63740 161.48699 92.1% 14.9 140s
246931 187843 162.45224 107 37 2055.63740 161.49079 92.1% 14.8 145s
257677 196691 1476.75268 129 15 2055.63740 161.49404 92.1% 14.8 150s
H266199 203519 2055.6372921 161.49620 92.1% 14.8 154s
266641 204225 162.60827 72 35 2055.63729 161.49640 92.1% 14.8 155s
H267735 204861 2055.6372855 161.49645 92.1% 14.8 155s
H267736 204861 2055.6372809 161.49645 92.1% 14.8 155s
H270334 207416 2055.6372756 161.49816 92.1% 14.8 156s
277332 213602 162.68395 80 38 2055.63728 161.50103 92.1% 14.8 160s
H280948 215964 2055.6372690 161.50211 92.1% 14.8 161s
287018 221092 165.44332 81 23 2055.63727 161.50447 92.1% 14.8 165s
H298734 231401 2055.6372636 161.50797 92.1% 14.8 169s
298952 232149 1834.60102 158 21 2055.63726 161.50808 92.1% 14.8 170s
309754 240891 162.70614 101 19 2055.63726 161.51154 92.1% 14.8 175s
H312301 242521 2055.6372589 161.51209 92.1% 14.8 177s
317332 247103 177.07874 218 44 2055.63726 161.51306 92.1% 14.8 180s
327839 255840 442.15676 96 25 2055.63726 161.51588 92.1% 14.8 185s
338504 265310 162.00403 68 63 2055.63726 161.51908 92.1% 14.8 190s
348482 273227 163.36103 105 22 2055.63726 161.52188 92.1% 14.8 195s
358394 282421 164.51267 84 48 2055.63726 161.52448 92.1% 14.8 200s
371093 293009 162.50844 93 38 2055.63726 161.52734 92.1% 14.7 205s
H377673 298532 2055.6366280 161.52851 92.1% 14.7 207s
H379540 299917 2055.6366234 161.52933 92.1% 14.7 208s
382422 303027 163.12208 84 55 2055.63662 161.53050 92.1% 14.7 210s
H388797 307894 2055.6366094 161.53155 92.1% 14.7 213s
392225 311338 162.74509 91 13 2055.63661 161.53260 92.1% 14.7 215s
H393996 312465 2055.6365855 161.53297 92.1% 14.7 215s
H394711 312997 2055.6365684 161.53302 92.1% 14.7 216s
H399067 317029 2055.6365624 161.53392 92.1% 14.7 218s
403522 320475 172.44849 222 42 2055.63656 161.53495 92.1% 14.7 220s
412241 328022 166.05774 128 38 2055.63656 161.53670 92.1% 14.7 225s
H414253 329656 2055.6365578 161.53715 92.1% 14.7 226s
420548 335041 162.12642 76 37 2055.63656 161.53820 92.1% 14.7 230s
430244 344112 163.87863 116 39 2055.63656 161.54080 92.1% 14.7 235s
H431886 344993 2055.6365553 161.54109 92.1% 14.7 236s
437329 350284 167.23065 161 30 2055.63656 161.54235 92.1% 14.7 240s
444999 359635 227.09496 269 19 2055.63656 161.54362 92.1% 14.7 245s
458777 368666 165.55925 112 28 2055.63656 161.54624 92.1% 14.7 250s
467045 375485 162.23243 96 34 2055.63656 161.54794 92.1% 14.7 255s
474385 382149 162.85396 73 31 2055.63656 161.55017 92.1% 14.6 260s
484367 390558 162.05352 82 50 2055.63656 161.55215 92.1% 14.6 265s
H490343 395277 2055.6365511 161.55317 92.1% 14.6 268s
494383 399237 161.71400 56 48 2055.63655 161.55362 92.1% 14.6 270s
504702 408060 164.32263 114 34 2055.63655 161.55598 92.1% 14.6 275s
513848 416021 164.70865 100 41 2055.63655 161.55728 92.1% 14.6 280s
523837 424926 484.28899 251 47 2055.63655 161.55891 92.1% 14.6 285s
533665 433191 165.68886 172 40 2055.63655 161.56056 92.1% 14.6 290s
539583 441182 167.72850 139 33 2055.63655 161.56166 92.1% 14.6 295s
H544587 442026 2055.4180000 161.56241 92.1% 14.6 296s
552410 449365 161.70075 58 16 2055.41800 161.56428 92.1% 14.6 300s
562721 457977 163.87431 60 28 2055.41800 161.56640 92.1% 14.6 305s
572735 466641 1314.04818 187 28 2055.41800 161.56779 92.1% 14.6 310s
H579341 471993 2055.4173530 161.56868 92.1% 14.6 313s
582548 475136 infeasible 166 2055.41735 161.56916 92.1% 14.6 315s
H584764 476481 2055.4173436 161.56945 92.1% 14.6 317s
589735 481243 166.33139 80 35 2055.41734 161.57033 92.1% 14.6 320s
599443 489795 796.51875 361 26 2055.41734 161.57145 92.1% 14.6 325s
609488 498601 177.38183 171 31 2055.41734 161.57330 92.1% 14.6 330s
619090 506653 930.13932 307 24 2055.41734 161.57466 92.1% 14.6 335s
626292 513296 infeasible 374 2055.41734 161.57570 92.1% 14.6 340s
635624 520967 164.18047 94 20 2055.41734 161.57760 92.1% 14.6 345s
H644237 528565 2055.4173390 161.57868 92.1% 14.6 349s
644286 530424 931.38807 169 33 2055.41734 161.57872 92.1% 14.6 350s
654830 537845 386.48561 274 67 2055.41734 161.58031 92.1% 14.6 355s
663741 545720 164.47919 109 23 2055.41734 161.58143 92.1% 14.6 360s
H670569 551030 2055.4171828 161.58200 92.1% 14.6 363s
674310 554440 1164.90860 219 4 2055.41718 161.58208 92.1% 14.6 366s
681917 560828 164.84017 89 29 2055.41718 161.58314 92.1% 14.6 370s
691273 569621 165.05781 149 37 2055.41718 161.58444 92.1% 14.6 375s
699777 576899 171.22688 81 22 2055.41718 161.58557 92.1% 14.6 380s
706934 583166 170.21033 192 41 2055.41718 161.58706 92.1% 14.6 385s
716896 591638 infeasible 75 2055.41718 161.58867 92.1% 14.6 390s
725777 599400 165.48256 100 8 2055.41718 161.58978 92.1% 14.6 395s
736004 608052 166.79177 104 30 2055.41718 161.59109 92.1% 14.6 400s
743949 615049 162.58218 77 65 2055.41718 161.59176 92.1% 14.6 405s
750407 622631 171.06983 205 32 2055.41718 161.59241 92.1% 14.6 410s
759245 628565 infeasible 366 2055.41718 161.59351 92.1% 14.6 415s
768126 635956 1328.32016 133 20 2055.41718 161.59448 92.1% 14.6 420s
777704 644411 165.87108 109 30 2055.41718 161.59576 92.1% 14.6 425s
787218 652340 177.49446 114 16 2055.41718 161.59727 92.1% 14.6 430s
796520 660761 175.42104 202 32 2055.41718 161.59829 92.1% 14.6 435s
804937 668055 169.02891 93 26 2055.41718 161.59926 92.1% 14.6 440s
813133 675066 162.76846 88 37 2055.41718 161.60038 92.1% 14.6 445s
H818426 679117 2055.4171557 161.60073 92.1% 14.6 448s
821497 681907 206.45676 231 41 2055.41716 161.60101 92.1% 14.6 450s
830145 689362 171.41738 263 49 2055.41716 161.60200 92.1% 14.6 455s
839332 697752 166.82683 81 26 2055.41716 161.60347 92.1% 14.6 460s
848031 704684 163.93917 110 38 2055.41716 161.60443 92.1% 14.6 465s
856457 715463 701.81485 93 23 2055.41716 161.60530 92.1% 14.6 472s
864553 719710 163.15800 86 19 2055.41716 161.60592 92.1% 14.6 475s
873964 727776 166.41396 160 26 2055.41716 161.60680 92.1% 14.6 480s
881198 734261 1016.83724 294 23 2055.41716 161.60757 92.1% 14.6 485s
889273 741286 infeasible 250 2055.41716 161.60832 92.1% 14.6 490s
899504 749351 170.11788 163 37 2055.41716 161.60945 92.1% 14.6 495s
906534 756121 162.40036 66 25 2055.41716 161.61016 92.1% 14.6 500s
916310 764552 2018.47949 228 21 2055.41716 161.61109 92.1% 14.5 505s
923397 770976 163.35501 81 47 2055.41716 161.61194 92.1% 14.6 510s
932653 778576 166.55707 101 20 2055.41716 161.61287 92.1% 14.6 515s
939618 784965 474.07421 131 28 2055.41716 161.61331 92.1% 14.6 520s
947129 791544 169.22215 313 51 2055.41716 161.61412 92.1% 14.6 525s
956057 799102 1758.01026 126 17 2055.41716 161.61444 92.1% 14.6 530s
961768 804264 931.92622 263 34 2055.41716 161.61528 92.1% 14.6 535s
970677 811954 162.76078 71 43 2055.41716 161.61608 92.1% 14.6 540s
977787 818306 164.89217 142 35 2055.41716 161.61689 92.1% 14.6 545s
986236 825787 2030.31506 216 12 2055.41716 161.61780 92.1% 14.6 550s
993515 831530 infeasible 240 2055.41716 161.61842 92.1% 14.6 555s
998267 836191 165.02860 141 35 2055.41716 161.61888 92.1% 14.6 560s
1006297 843399 165.45426 80 22 2055.41716 161.61936 92.1% 14.6 565s
1013022 849195 174.78513 144 17 2055.41716 161.62000 92.1% 14.6 570s
1021527 856222 1162.41420 112 20 2055.41716 161.62085 92.1% 14.6 575s
1028426 862945 570.96816 123 11 2055.41716 161.62162 92.1% 14.6 580s
1034810 868566 163.54808 134 23 2055.41716 161.62226 92.1% 14.6 585s
1042349 875159 171.93425 238 25 2055.41716 161.62296 92.1% 14.6 590s
1050326 881633 164.96012 143 30 2055.41716 161.62368 92.1% 14.6 595s
1057866 888158 164.33183 90 25 2055.41716 161.62431 92.1% 14.6 600s
1063666 893834 506.82984 223 16 2055.41716 161.62465 92.1% 14.6 605s
1070782 900185 164.53156 101 34 2055.41716 161.62511 92.1% 14.5 610s
1078681 907107 176.12850 262 37 2055.41716 161.62591 92.1% 14.5 615s
1086984 914332 162.75296 90 38 2055.41716 161.62680 92.1% 14.5 620s
1092310 919221 166.32282 220 58 2055.41716 161.62725 92.1% 14.5 625s
1100390 925925 165.03860 92 14 2055.41716 161.62816 92.1% 14.5 630s
1107782 932142 169.61636 99 14 2055.41716 161.62876 92.1% 14.5 635s
1115312 939054 166.53453 138 44 2055.41716 161.62936 92.1% 14.5 640s
1121844 944805 165.36534 123 25 2055.41716 161.63011 92.1% 14.5 645s
1129830 951606 165.00354 153 72 2055.41716 161.63058 92.1% 14.5 650s
1134853 956020 166.75998 215 47 2055.41716 161.63116 92.1% 14.5 655s
1141508 961533 infeasible 308 2055.41716 161.63188 92.1% 14.5 660s
1149640 968823 1223.29540 150 15 2055.41716 161.63247 92.1% 14.5 665s
I'm not sure why there is such a large difference in performance across the two processes. I have already tried running the automatic tuning tool but even with the suggested parameters the optimization performance was not significantly better.
Any suggestions as to why I'm experiencing these issues would be appreciated. If further information is needed just let me know and I'll try to provide it.
Kind Regards,
Michael Renner
-
Hi Michael,
In general, small changes of the model can have a huge effect on the performance, we observe this behavior regularly.
Do you have an idea whether the optimal value for the second model is nearer to the bound of 161 or nearer to the current incumbent of 2055? If you re-compute the objective value of your first solution based on the cost factors, what is the value you get? The question is whether a good solution to the second model is also a good solution to the first model, or whether they have a completely different structure.
If it is nearer to 161, Gurobi might not be able to find good heuristic solutions with the modified objective coefficients. What happens if you use the solution of your first model as a MIP start to your second model?
Usually, it is preferable (for a good performance) to have similar coefficients in the objective function for all involved variables. Coefficients that differ by several orders of magnitudes might lead to numerical issues. Could it be that due to the cost factors the coefficients differ now significantly?
Best regards,
Mario1 -
Hello Mario,
first of, thank you for your timely response.
Do you have an idea whether the optimal value for the second model is nearer to the bound of 161 or nearer to the current incumbent of 2055? If you re-compute the objective value of your first solution based on the cost factors, what is the value you get?
If I would use appropriate cost factors for the given solution of the first model the objective value would be 4853.252$. The bound of 161 in model 2 does not make sense since the fixed cost of opening at least one Distribution Center, which is required to do the subsequent routing, is already 1.500$.
Usually, it is preferable (for a good performance) to have similar coefficients in the objective function for all involved variables. Coefficients that differ by several orders of magnitudes might lead to numerical issues. Could it be that due to the cost factors the coefficients differ now significantly?
The cost for distance/travel time is small in comparison to other cost factors in model 2, whereas in model 1 specifically the coefficient for distance is by far the largest. For reference this is how the coefficients change from model 1 to model 2 (for the same solution):
- Cij (Distance/Transportation Cost): 64895.4 meters in model 1 to 16.2$ in model 2
- Tij (Time based Cost): 5513 seconds in model 1 to 22.05$ in model 2
- Fixed Costs for Depots: 3000$ same for both models
- Variable Depot Cost: 1680$ same for both models
- Fixed Vehicle Cost: 135$ same for both models
So yes, you are right the coefficients now differ significiantly. If that is the reason I'm running into the performance issues, how can I tackle that problem?
What happens if you use the solution of your first model as a MIP start to your second model?
I'm not yet familiar with setting MIP starts but will read up and try to do that.
Best regards,
Michael Renner
0 -
Hi Michael,
If the dual bound of 161 is weak, you might think of improving your model. The fact that you have to open at least one DC could be directly added as constraint, i.e., sum_i y_i >= 1. Additionally, you might force the y variables up by the x variables, e.g., sum_{j \in J} x_{ijk} <= y_i, for all i \in I, k \in K.
The coefficient changes might have lead to a shift of focus from solutions with low routing costs (in first model) to solutions with low depot costs (in second model). So, you need to take care that the depot variables are tightly linked in the model. You might also think of additional constraints to push up the z variables?
Best regards,
Mario1 -
Hi Mario,
thank you for your suggestions. As you might have noticed I am just beginning to learn about mixed integer linear programming, so I am grateful for the pointers.
The fact that you have to open at least one DC could be directly added as constraint, i.e., sum_i y_i >= 1. Additionally, you might force the y variables up by the x variables, e.g., sum_{j \in J} x_{ijk} <= y_i, for all i \in I, k \in K.
I have added both those constraints and while the bound is now reasonable the optimization performance is still not improving.
The coefficient changes might have lead to a shift of focus from solutions with low routing costs (in first model) to solutions with low depot costs (in second model)
That certainly seems to be the case. I'm still struggling to understand as to why the performance seems to be worse in the routing part of the optimization, since model 2 struggles even when only one possible depot is given (so the focus of the optimization should theoretically be on the routing cost?). Could it be that the solver struggles because the routing coefficients are now much closer together (in absolute terms)? The solver finds a reasonable bound and subsequently just stays within a few 0.01$ of that bound.
Do you have any recommendations on how I could deal with these problems, which seem to be mostly numerical?
So, you need to take care that the depot variables are tightly linked in the model. You might also think of additional constraints to push up the z variables?
I'm not sure if I understand what you mean by tightly linked. How would you go about pushing up the z variables?
I'll post the implementation of my constraints just to rule out any mistakes in this step of the optimization.
for j in J:
m.addConstr(quicksum(x[i,j,k] for i in [*I,*J] for k in K if i!=j) == 1)
for k in K:
m.addConstr(quicksum(set_of_all_customers.loc[j].Demand_C * x[i,j,k] for i in [*I,*J] for j in J if i!=j) <= set_of_all_vehicles.loc[k].capacity_V)
for l in J:
for j in J:
if l!=j:
for k in K:
m.addConstr(u[l,k] - u[j,k] + (len(set_of_all_customers) * x[l,j,k]) <= len(set_of_all_customers) -1)
for i in [*I,*J]:
for k in K:
m.addConstr(quicksum(x[i,j,k] for j in [*I,*J] if i!=j) - quicksum(x[j,i,k] for j in [*I,*J] if i!=j) == 0)
for k in K:
m.addConstr(quicksum(x[i,j,k] for i in I for j in J) <= 1)
for i in I:
m.addConstr(quicksum(z[i,j] * set_of_all_customers.loc[j].Demand_C for j in J) - (set_of_all_DC.loc[i].capacity_DC * y[i]) <= 0)
for i in I:
for j in J:
for k in K:
m.addConstr(quicksum(x[i,u,k] + x[u,j,k] for u in [*I,*J]) - z[i,j] <= 1)
for j in J:
m.addConstr(quicksum(x[i,j,k] for i in I for k in K) <= y[i])
m.addConstr(quicksum(y[i] for i in I) >= 1)Best regards,
Michael Renner
0 -
Hi Michael,
Could you please post the solver log of the model including the newly added constraints? Often this helps to understand what is going on and which Gurobi parameters might be beneficial.
Sometimes, the performance differences of two similar models are not easy to understand, this is a typical phenomenon for modern MIP solvers. The solver might take a completely different path during the optimization, just because of different objective coefficients. Additionally, VRPs are very hard to solve, as you can probably see in the literature.
Regarding tightly linking the z-variables: In an LP relaxation to your model it could happen that many x_ijk variables have, e.g., value 0.5. Then, in constraints (8) it might be feasible to leave the z-variables at zero and still satisfy all the constraints.
The additional constraints I mentioned for linking the y-variables are not necessary for the integer feasibility of your model, but they can strengthen the bounds obtained from the LP relaxation (by avoiding such cases as above) which in turn helps to close the optimality gap.
For the z-variables it is less obvious how to find good additional constraints, here are some examples:- You know that each customer has to be served from some depot, so "sum_i z_ij = 1, for all j \in J".
- At least for the customers directly connected to a depot in a route, you can set tight links, i.e., "sum_k x_ijk <= z_ij, for all i \in I, j \in J".
Let's see whether those can help.
Mario
0 -
Hello Mario,
I revisited the lp file of my model and noticed I made a mistake when adding one of your constraints:
sum_{j \in J} x_{ijk} <= y_i, for all i \in I, k \in K.
After correctly implementing this one and the rest of your recommended constraints the model now runs faster than ever. In fact, the optimization is so quick I'm not sure whether I can trust the solution. I played around with multiple cost factors to see if there is any weird performance impact, and there was none yet.
Following is an instance with 75 Customers and 3 possible Depots, which normally would have taken me upwards of 16 hours to get within this level of optimality (with the faulty distance/time coefficients)
Gurobi 9.1.2 (win64) logging started Wed Nov 3 11:43:14 2021
Changed value of parameter LogFile to gurobi_log50.log
Prev: Default:
Changed value of parameter MIPGap to 0.1
Prev: 0.0001 Min: 0.0 Max: inf Default: 0.0001
Gurobi Optimizer version 9.1.2 build v9.1.2rc0 (win64)
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 17953 rows, 18705 columns and 228651 nonzeros
Model fingerprint: 0x6bff7982
Variable types: 225 continuous, 18480 integer (18480 binary)
Coefficient statistics:
Matrix range [1e+00, 2e+02]
Objective range [1e+00, 1e+02]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 1e+02]
Presolve removed 0 rows and 234 columns
Presolve time: 0.25s
Presolved: 17953 rows, 18471 columns, 227301 nonzeros
Variable types: 225 continuous, 18246 integer (18246 binary)
Deterministic concurrent LP optimizer: primal and dual simplex
Showing first log only...
Concurrent spin time: 0.00s
Solved with dual simplex
Root relaxation: objective 4.926199e+02, 644 iterations, 0.11 seconds
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 492.61986 0 153 - 492.61986 - - 0s
0 0 500.15822 0 180 - 500.15822 - - 3s
0 0 501.55832 0 201 - 501.55832 - - 4s
0 0 503.07794 0 214 - 503.07794 - - 4s
0 0 503.34102 0 196 - 503.34102 - - 4s
0 0 503.34102 0 193 - 503.34102 - - 5s
0 0 507.61986 0 310 - 507.61986 - - 6s
0 0 507.61986 0 264 - 507.61986 - - 6s
0 0 507.61986 0 310 - 507.61986 - - 7s
0 0 507.61986 0 309 - 507.61986 - - 7s
0 0 507.61986 0 213 - 507.61986 - - 9s
0 0 507.61986 0 248 - 507.61986 - - 9s
0 0 507.61986 0 253 - 507.61986 - - 9s
0 0 507.61986 0 263 - 507.61986 - - 9s
0 0 507.61986 0 272 - 507.61986 - - 10s
0 0 507.61986 0 276 - 507.61986 - - 10s
0 0 507.61986 0 182 - 507.61986 - - 11s
0 0 507.61986 0 214 - 507.61986 - - 11s
H 0 0 635.4093000 507.61986 20.1% - 11s
0 0 546.33107 0 182 635.40930 546.33107 14.0% - 12s
H 0 0 634.9966400 546.33107 14.0% - 18s
H 0 0 625.4411100 546.33107 12.6% - 18s
0 0 546.33107 0 238 625.44111 546.33107 12.6% - 18s
0 0 546.33107 0 264 625.44111 546.33107 12.6% - 18s
0 0 546.33107 0 264 625.44111 546.33107 12.6% - 19s
0 0 546.33239 0 189 625.44111 546.33239 12.6% - 19s
0 0 546.33239 0 188 625.44111 546.33239 12.6% - 20s
0 2 546.59621 0 188 625.44111 546.59621 12.6% - 22s
19 22 546.59621 6 255 625.44111 546.59621 12.6% 212 25s
H 30 31 613.7123200 546.59621 10.9% 183 27s
H 33 31 611.3607300 546.59621 10.6% 172 27s
80 95 546.98063 16 294 611.36073 546.59621 10.6% 182 30s
399 421 552.40852 65 234 611.36073 546.59621 10.6% 88.2 35s
H 471 467 611.0197900 546.59621 10.5% 80.9 49s
H 472 467 610.0201500 546.59621 10.4% 80.9 49s
H 473 467 609.7646900 546.59621 10.4% 80.7 49s
H 474 467 607.6571200 546.59621 10.0% 80.6 49s
H 475 471 605.8061600 546.59621 9.77% 80.4 52s
Cutting planes:
Gomory: 18
Clique: 5
MIR: 119
Zero half: 19
RLT: 144
Explored 479 nodes (52766 simplex iterations) in 52.91 seconds
Thread count was 8 (of 8 available processors)
Solution count 10: 605.806 607.657 609.765 ... 635.409
Optimal solution found (tolerance 1.00e-01)
Best objective 6.058061600000e+02, best bound 5.465962100000e+02, gap 9.7737%I manually inspected the solution for the routing and there were no nonsensical connections as far as I can see. Can you see any red flags within the log or does the model just work a lot better now? I will keep on experimenting with different cost factors but hope that this was the solution to my problem.
Thanks to you Mario, I would not have been able to solve this problem myself.
Best Regards,
Michael Renner
0 -
Hi Michael,
Good to see that it works better now!
I cannot see any suspicious lines in the solver log. You might even set a smaller MIPGap to get better solutions.I would recommend to write a method that checks your final solution for feasibility, e.g., by building a small graph structure to see whether all routes are connected to some depot, whether the capacity is satisfied for each vehicle, etc. This helps finding modeling mistakes.
Best regards,
Mario0 -
Hi Mario,
I will now run the automatic tuning tool again to see from which parameters i can benefit to find solutions for different model sizes, as well as what a reasonable MIPGap is.
I already have a few different solution printers in place, which let me manually check the feasibility of the provided solution. I will get back to you if something should come up within the following experiments. If not, I sincerely thank you for your time and effort.
Best Regards,
Michael Renner
0
Please sign in to leave a comment.
Comments
8 comments