Out of memory while running MIP model in Python with Gurobi package
I am solving a MIP model in Python with the Gurobi package. My mine CPU is as follows:
CPU model: 11th Gen Intel(R) Core(TM) i5-1145G7 @ 2.60GHz, instruction set [SSE2|AVX|AVX2|AVX512]
Thread count: 4 physical cores, 8 logical processors, using up to 1 thread.
I got an error of out of memory after a long time. Then, I changed the machine and I am using a computer with following characteristics:
CPU model: Intel(R) Xeon(R) Platinum 8488C, instruction set [SSE2|AVX|AVX2|AVX512]
Thread count: 16 physical cores, 32 logical processors, using up to 32 threads.
I also changed some parameters in the code. I Set parameter NodefileStart to value 0, parameter PreSparsify to value 1, Threads to value 32, and Method to value 1. But It seems it takes too long to solve the model. After 5 hours, it did not even start to show the optimality gap. Note that, I am optimizing a large-scale model with 341696 rows, 531828 columns, and 8060314 nonzeros.
The model has 66392 general constraints, and in terms of Variable types, there are 525808 continuous, 6020 integers (6020 binary).
Optimize a model with 341696 rows, 531828 columns and 8060314 nonzeros
Model fingerprint: 0x03a35757
Model has 66392 general constraints
Variable types: 525808 continuous, 6020 integer (6020 binary)
Coefficient statistics:
Matrix range [1e+00, 1e+03]
Objective range [1e+00, 3e+01]
Bounds range [1e+00, 1e+02]
RHS range [1e+00, 1e+03]
Presolve removed 200078 rows and 376353 columns (presolve time = 5s) ...
Presolve removed 402656 rows and 557750 columns (presolve time = 10s) ...
Presolve removed 142968 rows and 340820 columns
Presolve time: 10.65s
Presolved: 198728 rows, 191008 columns, 1282723 nonzeros
Variable types: 144810 continuous, 46198 integer (46198 binary)
Root simplex log...
Iteration Objective Primal Inf. Dual Inf. Time
0 handle free variables 15s
20513 -2.1293648e+02 9.651873e+03 0.000000e+00 15s
76702 2.8460022e+04 1.859709e+05 0.000000e+00 20s
93074 4.1566715e+04 1.624518e+05 0.000000e+00 25s
149842 9.3549408e+04 1.472253e+04 0.000000e+00 30s
189058 1.0409371e+05 0.000000e+00 0.000000e+00 32s
Root relaxation: objective 1.040937e+05, 189058 iterations, 17.36 seconds (14.57 work units)
Total elapsed time = 32.14s (DegenMoves)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 104093.712 0 862 - 104093.712 - - 33s
0 0 105046.082 0 1442 - 105046.082 - - 42s
0 0 105046.082 0 1472 - 105046.082 - - 44s
0 0 105390.805 0 1214 - 105390.805 - - 50s
0 0 105395.767 0 1339 - 105395.767 - - 52s
0 0 105395.767 0 1339 - 105395.767 - - 53s
0 0 105395.774 0 1340 - 105395.774 - - 53s
0 0 105395.774 0 1340 - 105395.774 - - 53s
0 0 105866.005 0 904 - 105866.005 - - 58s
0 0 105866.005 0 903 - 105866.005 - - 58s
0 0 105866.406 0 888 - 105866.406 - - 62s
0 0 105866.406 0 893 - 105866.406 - - 62s
0 0 105889.713 0 799 - 105889.713 - - 66s
0 0 105889.992 0 794 - 105889.992 - - 69s
0 0 105889.997 0 807 - 105889.997 - - 69s
0 0 105899.597 0 780 - 105899.597 - - 71s
0 0 105899.740 0 785 - 105899.740 - - 75s
0 0 105901.403 0 796 - 105901.403 - - 77s
0 0 105901.403 0 795 - 105901.403 - - 79s
0 0 105901.679 0 754 - 105901.679 - - 81s
0 0 105901.682 0 760 - 105901.682 - - 83s
0 0 105901.682 0 762 - 105901.682 - - 84s
0 0 105901.682 0 761 - 105901.682 - - 87s
0 0 105901.682 0 763 - 105901.682 - - 88s
0 0 105901.682 0 358 - 105901.682 - - 95s
0 2 105901.682 0 348 - 105901.682 - - 120s
27 32 105918.257 4 362 - 105901.682 - 629 125s
95 128 105917.913 7 399 - 105901.682 - 282 130s
223 256 105917.913 9 397 - 105901.682 - 152 135s
351 384 105918.235 11 396 - 105901.682 - 115 141s
415 448 105918.235 13 395 - 105901.682 - 110 145s
517 550 105918.235 16 392 - 105901.682 - 105 152s
549 608 105927.406 16 393 - 105901.682 - 111 156s
607 670 105918.959 17 404 - 105901.682 - 122 161s
669 729 105935.143 19 406 - 105901.682 - 134 165s
728 804 105935.799 19 405 - 105901.682 - 141 170s
803 876 105953.342 20 405 - 105901.682 - 154 176s
875 962 105949.100 21 403 - 105901.682 - 170 182s
961 1050 105959.790 23 405 - 105901.682 - 177 188s
1049 1206 105967.583 25 387 - 105901.682 - 183 196s
1205 1533 105982.051 28 396 - 105901.682 - 202 203s
1532 1860 106012.671 36 386 - 105901.682 - 206 209s
1859 2159 106036.111 43 412 - 105901.682 - 204 216s
2158 2461 106058.068 46 409 - 105901.682 - 207 222s
Created node file directory './grbnodes3'
2462 2756 106079.888 51 416 - 105901.682 - 207 230s
2760 3089 106115.099 54 439 - 105901.682 - 211 238s
3099 3403 106142.890 66 376 - 105901.682 - 217 246s
3413 3757 106167.369 74 395 - 105901.682 - 212 254s
3767 4177 106174.232 81 393 - 105901.682 - 211 261s
4190 4559 106191.161 95 466 - 105901.682 - 209 269s
4578 4974 106196.510 101 450 - 105901.682 - 212 277s
4995 5437 106206.430 107 448 - 105901.682 - 211 285s
5463 5892 106239.954 116 511 - 105901.682 - 206 293s
5923 6343 106253.410 131 445 - 105901.682 - 204 302s
6375 6855 106259.893 146 496 - 105901.682 - 200 310s
6890 7249 106266.247 155 488 - 105901.682 - 197 321s
7287 7783 106270.041 167 497 - 105901.682 - 197 330s
7830 8265 106284.954 179 487 - 105901.682 - 194 340s
8383 8770 106391.595 192 487 - 105901.682 - 198 351s
8900 9280 106417.717 202 499 - 105901.682 - 201 362s
9445 9841 106441.564 209 533 - 105901.682 - 202 375s
10024 10444 106453.098 228 478 - 105901.682 - 206 386s
10661 10969 infeasible 242 - 105901.682 - 206 400s
11236 11547 106691.031 253 517 - 105901.682 - 208 414s
11878 12285 106718.854 280 507 - 105901.682 - 208 430s
12689 12770 106758.127 297 501 - 105901.682 - 208 445s
13333 13251 106946.726 313 593 - 105901.682 - 215 460s
13924 13895 infeasible 318 - 105901.682 - 225 475s
14662 13896 106159.953 50 22130 - 105901.682 - 229 926s
14664 13897 106061.709 62 862 - 105901.682 - 229 966s
14665 13898 105964.620 26 1048 - 105901.682 - 229 978s
14666 13899 106271.931 200 905 - 105901.682 - 229 988s
14667 13899 105927.337 22 915 - 105901.682 - 229 990s
14668 13900 105943.032 20 919 - 105901.682 - 229 1003s
14669 13901 106619.953 327 827 - 105904.008 - 229 1009s
14670 13901 106115.832 98 828 - 105904.008 - 229 1022s
14671 13902 106053.054 58 777 - 105905.429 - 229 1028s
14672 13903 106619.953 328 794 - 105905.441 - 229 1031s
14673 13903 106308.614 163 783 - 105905.441 - 229 1047s
14674 13904 105926.400 14 717 - 105905.636 - 229 1051s
14676 13905 105963.285 25 707 - 105905.988 - 229 1071s
14677 13906 105976.230 21 705 - 105907.552 - 229 1075s
14678 13907 105916.843 19 729 - 105908.177 - 229 1083s
14680 13908 105955.791 24 730 - 105908.222 - 229 1085s
14681 13909 105953.333 20 729 - 105908.222 - 229 1105s
14682 13909 105954.634 19 719 - 105909.139 - 229 1111s
14683 13910 105966.741 23 709 - 105909.289 - 229 1117s
14684 13911 105945.036 20 704 - 105909.296 - 229 1138s
14685 13911 106584.173 165 718 - 105910.146 - 229 1142s
14686 13912 105952.238 18 713 - 105910.151 - 229 1167s
14687 13913 106165.760 192 700 - 105910.778 - 229 1170s
14688 13913 105926.618 12 697 - 105910.787 - 229 1187s
14690 13915 106395.066 188 713 - 105911.109 - 229 1190s
14691 13915 105992.824 37 721 - 105911.112 - 229 1200s
14694 13917 105971.649 26 735 - 105911.293 - 228 1214s
14695 13918 106165.760 192 740 - 105911.357 - 228 1217s
14697 13919 105918.238 6 745 - 105911.371 - 228 1228s
14698 13920 105939.774 22 722 - 105911.372 - 228 1231s
14699 13921 106308.872 84 719 - 105911.372 - 228 1241s
14700 13921 105928.656 19 723 - 105911.539 - 228 1245s
14701 13922 106059.663 38 741 - 105911.547 - 228 1254s
14702 13923 105933.505 18 730 - 105911.553 - 228 1255s
14707 13927 105911.553 14 862 - 105911.553 - 245 1293s
14708 13928 105936.395 17 1012 - 105911.553 - 245 1303s
14709 13929 105926.642 14 907 - 105911.650 - 245 1311s
14713 13931 105911.650 15 931 - 105911.650 - 245 1328s
14714 13932 106322.584 190 881 - 105911.658 - 245 1334s
14715 13933 105918.266 11 877 - 105911.658 - 245 1348s
14716 13933 105942.471 19 809 - 105911.774 - 245 1354s
14717 13934 105974.374 27 816 - 105911.793 - 245 1355s
14718 13935 105932.702 13 810 - 105911.797 - 245 1369s
14719 13935 105965.748 14 866 - 105911.907 - 245 1373s
14720 13936 106253.601 153 818 - 105911.911 - 245 1388s
14721 13937 105925.718 9 819 - 105912.055 - 245 1394s
14722 13937 105946.162 20 786 - 105912.628 - 245 1398s
14723 13938 106234.364 161 792 - 105912.699 - 245 1400s
14724 13939 105990.734 20 789 - 105912.707 - 245 1417s
14725 13939 105961.063 23 775 - 105913.140 - 245 1421s
14726 13940 105929.276 14 782 - 105913.141 - 245 1438s
14727 13941 106283.238 187 767 - 105913.151 - 245 1442s
14728 13941 106233.209 161 791 - 105913.347 - 245 1447s
14731 13943 105976.713 23 808 - 105913.484 - 245 1467s
14732 13944 105920.485 13 809 - 105913.548 - 244 1470s
14733 13945 109012.416 330 799 - 105913.548 - 244 1490s
14734 13945 106225.973 163 757 - 105913.582 - 244 1498s
14735 13946 105993.667 36 777 - 105913.595 - 244 1503s
14737 13947 106322.874 191 757 - 105913.606 - 244 1518s
14738 13948 106414.377 193 760 - 105913.646 - 244 1521s
14740 13949 106268.904 193 763 - 105913.678 - 244 1532s
14741 13950 106165.760 192 759 - 105914.039 - 244 1535s
14742 13951 106199.860 211 752 - 105914.042 - 244 1545s
14744 13952 106057.949 63 742 - 105914.146 - 244 1558s
14745 13953 105939.774 22 748 - 105914.172 - 244 1561s
14746 13953 105969.820 22 745 - 105914.172 - 244 1571s
14748 13955 105969.282 24 740 - 105914.172 - 244 1584s
14749 13955 106247.192 93 745 - 105914.181 - 244 1588s
14750 13956 105926.674 8 746 - 105914.181 - 244 1595s
14751 13957 105946.644 20 730 - 105914.181 - 244 1613s
14752 13957 106177.585 63 730 - 105914.181 - 244 1630s
14753 13958 105918.324 12 730 - 105914.181 - 244 1650s
14754 13962 105930.289 21 709 - 105914.181 - 281 1688s
14756 13965 105965.785 22 672 - 105914.181 - 281 1699s
14760 13972 105983.377 23 689 - 105914.181 - 282 1711s
14768 13985 106012.179 24 690 - 105914.181 - 282 1728s
14784 14012 106027.180 25 688 - 105914.181 - 283 1746s
14848 14054 106035.261 26 691 - 105914.181 - 286 1752s
14880 14076 106035.135 27 768 - 105914.181 - 286 1755s
14944 14121 106035.535 28 761 - 105914.181 - 286 1760s
15013 14169 106035.245 29 766 - 105914.181 - 285 1765s
15136 14244 106037.484 31 775 - 105914.181 - 284 1772s
15168 14265 106042.743 32 761 - 105914.181 - 284 1776s
15234 14303 106051.930 33 774 - 105914.181 - 285 1859s
15269 14326 106044.815 33 765 - 105914.181 - 285 1862s
15306 14357 106047.251 34 781 - 105914.181 - 286 1867s
15353 14399 106054.472 34 765 - 105914.181 - 287 1871s
15464 14468 106049.421 36 775 - 105914.181 - 289 1877s
15517 14503 106052.449 37 777 - 105914.181 - 290 1881s
15570 14541 106123.806 38 776 - 105914.181 - 290 1885s
15626 14572 106059.093 39 778 - 105914.181 - 291 1890s
15746 14649 106061.602 41 756 - 105914.181 - 293 1899s
15800 14679 106068.560 42 754 - 105914.181 - 294 1904s
15850 14716 106074.381 43 753 - 105914.181 - 294 1909s
15907 14752 106074.469 44 737 - 105914.181 - 295 1915s
15965 14792 106077.390 45 743 - 105914.181 - 297 1921s
16024 14828 106076.425 46 732 - 105914.181 - 298 1927s
16080 14878 106083.415 47 780 - 105914.181 - 300 1934s
16152 14908 106082.668 48 680 - 105914.181 - 302 1941s
16208 14961 106084.745 49 790 - 105914.181 - 304 1947s
16280 15035 106092.303 50 783 - 105914.181 - 306 1954s
16384 15091 106089.390 52 738 - 105914.181 - 308 1962s
16480 15120 106094.087 53 739 - 105914.181 - 309 1971s
16544 15170 106109.315 54 739 - 105914.181 - 311 1978s
16622 15233 106105.686 56 726 - 105914.181 - 312 1985s
16722 15392 106115.172 58 747 - 105914.181 - 314 1991s
16919 15528 106136.514 61 753 - 105914.181 - 319 1998s
17132 15681 106143.011 65 723 - 105914.181 - 321 2005s
17365 15651 106151.633 70 739 - 105914.181 - 325 2014s
17456 15765 106160.805 71 724 - 105914.181 - 327 2026s
17652 15858 106161.392 74 727 - 105914.181 - 336 2037s
17849 16037 106171.431 79 720 - 105914.181 - 343 2045s
18102 16048 106182.082 85 661 - 105914.181 - 348 2056s
18216 16269 106183.147 87 704 - 105914.181 - 350 2064s
18512 16490 106188.911 93 651 - 105914.181 - 355 2073s
18833 16500 106195.549 99 690 - 105914.181 - 360 2083s
18976 16768 106211.166 101 626 - 105914.181 - 361 2093s
19317 17024 106199.777 108 692 - 105914.181 - 365 2102s
19695 17037 106203.277 114 677 - 105914.181 - 369 2113s
19858 17386 106235.215 117 723 - 105914.181 - 372 2124s
20287 17618 106208.996 123 661 - 105914.181 - 374 2134s
20694 17681 106213.135 133 647 - 105914.181 - 377 2146s
20921 18032 106219.114 137 650 - 105914.181 - 379 2157s
21393 18247 106232.149 147 642 - 105914.181 - 381 2171s
21803 18296 106230.550 156 643 - 105914.181 - 382 2190s
22047 18589 106233.136 159 633 - 105914.181 - 382 2203s
22461 18895 106236.053 167 623 - 105914.181 - 385 2216s
22960 19060 106243.917 174 611 - 105914.181 - 386 2233s
23355 19501 106238.579 181 616 - 105914.181 - 388 2247s
23966 19802 106240.526 193 539 - 105914.181 - 390 2262s
24523 20128 106248.670 201 548 - 105914.181 - 391 2277s
25096 20570 106252.124 210 524 - 105914.181 - 394 2292s
25788 20919 106253.827 221 494 - 105914.181 - 395 2307s
26399 21400 106260.590 233 433 - 105914.181 - 397 2323s
27158 21749 106260.622 238 429 - 105914.181 - 397 2339s
27382 21674 106179.280 78 719 - 105914.181 - 399 2340s
27880 21965 106263.250 252 382 - 105914.181 - 400 2358s
28422 22319 106269.341 261 471 - 105914.181 - 404 2378s
29078 22833 106269.900 272 466 - 105914.181 - 406 2394s
29668 22636 106516.776 273 378 - 105914.181 - 409 2395s
29864 22699 106282.806 283 388 - 105914.181 - 410 2704s
30031 25101 106270.452 285 402 - 105914.181 - 410 2770s
32687 24867 106280.601 326 371 - 105914.181 - 414 2791s
33366 25526 106279.479 336 359 - 105914.181 - 415 2819s
34336 26012 106273.188 352 291 - 105914.181 - 418 2860s
35375 26211 106275.033 373 273 - 105914.181 - 420 2885s
36009 26837 106279.878 378 270 - 105914.181 - 426 2917s
36940 27455 106279.878 397 246 - 105914.181 - 429 2946s
37994 27977 106283.362 423 222 - 105914.181 - 430 2973s
38968 28722 106284.263 445 210 - 105914.181 - 433 2998s
40116 29485 106333.149 462 304 - 105914.181 - 435 3023s
41348 30299 106357.949 473 263 - 105914.181 - 436 3055s
42669 30565 infeasible 482 - 105914.181 - 436 3101s
43582 30547 infeasible 482 - 105914.181 - 441 3151s
44064 31456 105940.254 36 758 - 105914.181 - 444 3194s
45463 32134 106135.585 48 762 - 105914.181 - 448 3235s
46818 32154 106193.519 74 737 - 105914.181 - 454 3284s
47539 33134 106228.646 84 666 - 105914.181 - 457 3319s
49029 33726 106290.726 105 654 - 105914.181 - 463 3355s
50351 34531 106363.132 124 629 - 105914.181 - 466 3420s
51821 35332 106456.982 137 717 - 105914.181 - 469 3465s
53486 36334 106498.326 148 753 - 105914.181 - 473 3531s
55465 37264 106549.589 191 697 - 105914.181 - 475 3603s
57468 38291 106577.976 222 543 - 105914.181 - 477 3674s
59441 38292 105928.360 30 21800 - 105914.181 - 481 8295s
59443 38293 105925.430 32 862 - 105914.181 - 481 8374s
59444 38294 106902.223 175 1001 - 105914.181 - 481 8403s
59445 38295 106212.910 120 961 - 105915.566 - 481 8422s
59447 38296 106099.440 53 907 - 105917.287 - 481 8426s
59449 38297 105967.709 39 933 - 105917.423 - 481 8432s
59450 38298 106299.014 790 919 - 105917.447 - 481 8446s
59451 38299 107151.621 114 925 - 105917.447 - 481 8492s
59452 38299 105990.272 54 825 - 105917.597 - 481 8497s
59453 38300 105926.024 36 810 - 105917.597 - 481 8549s
59454 38301 106189.456 113 842 - 105917.631 - 481 8554s
59455 38301 105994.321 62 833 - 105917.699 - 481 8556s
59457 38303 106293.271 70 860 - 105917.710 - 481 8633s
59458 38303 105972.492 52 782 - 105917.773 - 481 8640s
59459 38304 105945.004 40 808 - 105917.779 - 481 8717s
59460 38305 105935.877 48 818 - 105917.883 - 481 8723s
59461 38305 106617.843 236 811 - 105918.121 - 481 8730s
59462 38306 106013.349 48 821 - 105918.145 - 481 8736s
59464 38307 106526.057 100 806 - 105918.334 - 481 8815s
59465 38308 106415.969 79 749 - 105919.091 - 481 8820s
59467 38309 105947.095 39 748 - 105919.120 - 481 8877s
59468 38310 106214.891 67 770 - 105919.353 - 481 8881s
59471 38312 105964.644 51 781 - 105919.492 - 481 8919s
59472 38313 105954.220 62 778 - 105919.492 - 481 8924s
59473 38313 106009.944 60 763 - 105919.492 - 481 8958s
59474 38314 105932.821 38 780 - 105919.498 - 481 8962s
59475 38315 106298.689 769 775 - 105919.498 - 481 8997s
59476 38315 105927.140 27 763 - 105919.505 - 481 9000s
59477 38316 105937.216 36 766 - 105919.505 - 481 9033s
59478 38317 106805.953 98 751 - 105919.507 - 481 9038s
Solution
Sry, I'll write a post instead of a comment, because this allows to add pictures and point out several things that you should check when running LP models.
Problem number 1.
You said that the model has 6k binary variables which is a reasonable number, but after relaxation stage Gurobi concluded that actual number of binary variables is 46k. This means that to implement some of the constraints you need to introduce additional binary variables. From my experience 46k is too many and basically this is why your model remains unsolvable.
Simplifying a lot 'branch-and-bound' is a combinatorial search of good integers that don't violate your constraints. And obviously combinatorial search for 46k binary variables (which of them should be 0 and which 1) is very hard task.
Problem number 2:
Incumbent and Gap are Nones during branch and bound. This means that the model can't find ANY feasible solutions for the problem (even single very non-optimal solution wasn't found). Usually you would expect to find first feasible solution very soon, at least in first 5-10 minutes of branch and bound (picture shows the beginning of branch-and-bound).
no feasible solutions found after 2.5 hours (9k seconds) of 'branch-and-bound'
My conculsions:
You've encounter a very hard problem to tackle.
- I would recommend to review the task and to decide: do you need any feasible solution or solution close to optimal? For example, if your task is related to scheduling jobs done by employees you most probably will be fine with any solution and don't need the closest to optimal;
- Break your task in parts. For example if you do a monthly planning break tasks in 4 weeks: do a week by week planning;
- Review constraints that require additional binary variables. Remove them from the model or think how to replace them with continuous constraints; Read science articles about similar problems/tasks and how to tackle them efficiently;
- Think if you can find and provide to Gurobi any feasible solution yourself using greedy search or smart combinatorial search. If you have any feasible solution that you can pass as a hint to the Gurobi this will significantly speed up branch-and-bound optimization.
- RuntimeError: Trying to backward through the graph a second time on loss tensor
- ERROR: post() got an unexpected keyword argument 'proxies'
- How do I automatically fix an invalid JSON string?
- Python generating a list of dates between two dates
- ModuleNotFoundError: No module named 'json'
- Check if string is None, empty or has spaces only
- invalid command name ".!canvas"
- SqlAlchemy: How to make a LONGBLOB column in mysql?
- Validate if input number is prime
- OpenAI remove key access while using AAD authentication
- Converting a Text File to a String in Python
- Problems with repeated draws of Sobol sequence in scipy
- Render NumPy array in FastAPI
- Any faster and memory-efficient alternative of torch.autograd.functional.jacobian(model.decoder, latent_l)?
- Convert integer to string in Python
- starting container process caused: exec: "fastapi": executable file not found in $PATH: unknown
- How to change version of Python in PyCharm
- convert image from CV_64F to CV_8U
- Pyspark new column when otherwise results in "should be a column" error
- FastAPI as a Windows service
- Regex to match a whole number not ending in some digits
- How can I measure the width of a string rendering via tkFont without creating a window first?
- The tilde operator in Python
- 2D stacking and optimizing
- Compute percentage of positive rows in a group_by polars DataFrame
- Extract domain name from URL in Python
- How to use AssertRaisesMessage() in Django tests
- Langchain ChatOllama always produces invalid format: expected "json" error
- Python client library for Language Server Protocol (LSP)
- How can I convert a python urandom to a string?