quicksum contraint slows solver.
回答済みHi,
I´m working in a MILP model. It solves relatively fast within 10 to 15 minutes. But after adding the following two constraints, the solver takes about 4 days to solve the problem. Any idea why these constraints would slow make the optimization so slow?
Thanks
m.addConstr(gp.quicksum(P_bat_charge[it, it1] for it in h_4 for it1 in m_15) * delta_t <= Max_charge_E_op_period )
m.addConstr(gp.quicksum(P_bat_discharge[it, it1] for it in h_4 for it1 in m_15) * delta_t >= -Max_discharge_E_op_period )
-
正式なコメント
This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?. -
Hi David,
It is hard for the Community to provide help with little information you provide. In particular, How do I ask a good question? and Posting to the Community Forum may be of interest.
Does the problem solve so slow only if you add both constraints or is one enough? What are the sizes of \(\texttt{h_4}\) and \(\texttt{m_15}\)? What is the number of variables, constraints, and non-zeros in your problem? What are the ranges of your coefficients? Does Gurobi have difficulties in finding a feasible solution or is it rather the lower bound which converges slowly?
Could you share parts of the LOG output?
Best regards,
Jaromił0 -
Hi Jaromił,
Thanks for your reply and suggestions! I haven´t actually tried to just implement one of the constraints since that wouldn't make much sense in my problem.
The ranges for h_4 and m_15 are 2190 and 16 respectively. Gurobi takes most of the time moving the lower bound. It is worth mentioning that I'm using MIPFocus = 1.
I guess the answers for the rest of your questions will be found in the log.
Thank you so much for your help.
Gurobi Optimizer version 9.0.3 build v9.0.3rc0 (win64)
Optimize a model with 531490 rows, 637290 columns and 1134974 nonzeros
Model fingerprint: 0xfcfeb2b1
Model has 126198 quadratic constraints
Model has 210240 general constraints
Variable types: 422670 continuous, 214620 integer (142350 binary)
Coefficient statistics:
Matrix range [1e-01, 5e+01]
QMatrix range [6e-06, 1e+01]
QLMatrix range [2e-01, 2e+02]
Objective range [3e-03, 7e+01]
Bounds range [1e+00, 2e+01]
RHS range [6e-03, 5e+04]
Presolve removed 349190 rows and 385968 columns (presolve time = 30s) ...
Presolve removed 349190 rows and 390786 columns (presolve time = 31s) ...
Presolve removed 728265 rows and 593317 columns (presolve time = 35s) ...
Presolve added 36738 rows and 0 columns
Presolve removed 0 rows and 140245 columns
Presolve time: 37.05s
Presolved: 843764 rows, 550371 columns, 2155980 nonzeros
Presolved model has 33117 bilinear constraint(s)
Variable types: 353781 continuous, 196590 integer (123524 binary)
Deterministic concurrent LP optimizer: dual simplex and barrier
Showing barrier log only...
Root barrier log...
Ordering time: 0.30s
Barrier statistics:
AA' NZ : 8.380e+06
Factor NZ : 1.691e+07 (roughly 600 MBytes of memory)
Factor Ops : 6.957e+08 (less than 1 second per iteration)
Threads : 1
Objective Residual
Iter Primal Dual Primal Dual Compl Time
0 -2.13697108e+08 2.76554599e+08 5.68e+07 3.38e+01 2.11e+05 43s
1 -7.49344652e+07 3.91565613e+08 2.26e+07 6.65e+01 8.35e+04 44s
2 -2.34778703e+07 4.87012320e+08 7.15e+06 9.35e+00 3.51e+04 45s
3 -2.19293468e+06 4.77839191e+08 7.85e+05 9.66e-13 4.11e+03 46s
4 3.00837458e+05 2.87545357e+08 7.82e+04 8.53e-13 5.22e+02 47s
5 6.14563135e+05 1.08241846e+08 1.07e+04 5.08e-13 1.10e+02 48s
6 7.95682023e+05 4.98772174e+07 1.40e-01 3.06e-13 3.80e+01 49s
7 9.12480521e+05 3.29349357e+07 5.76e-02 2.37e-13 2.38e+01 50s
8 1.07097772e+06 1.51679258e+07 2.77e-02 1.63e-13 1.03e+01 51s
9 1.53654068e+06 8.62082115e+06 9.62e-03 1.76e-13 5.12e+00 51s
10 1.82309098e+06 4.65922756e+06 8.55e+01 1.49e-13 2.05e+00 52s
11 2.11880831e+06 3.50741684e+06 2.30e+01 1.55e-13 1.00e+00 53s
12 2.27289650e+06 3.09480829e+06 1.44e+01 1.35e-13 5.93e-01 54s
13 2.40341045e+06 2.87441226e+06 7.66e+00 1.49e-13 3.40e-01 55s
14 2.47329220e+06 2.72587271e+06 4.35e+00 1.59e-13 1.82e-01 56s
15 2.51851278e+06 2.66670456e+06 2.45e+00 2.40e-13 1.07e-01 57s
16 2.55019890e+06 2.62261020e+06 1.22e+00 1.23e-13 5.23e-02 58s
17 2.56529847e+06 2.60553563e+06 6.70e-01 1.46e-13 2.90e-02 59s
18 2.57124936e+06 2.59763479e+06 4.57e-01 1.30e-13 1.91e-02 60s
19 2.57651848e+06 2.59159336e+06 2.71e-01 1.92e-13 1.09e-02 61s
20 2.58074629e+06 2.58850307e+06 1.22e-01 1.60e-13 5.60e-03 62s
21 2.58259889e+06 2.58630984e+06 5.68e-02 1.95e-13 2.68e-03 63s
22 2.58323797e+06 2.58565372e+06 3.42e-02 1.10e-13 1.74e-03 64s
23 2.58395064e+06 2.58514057e+06 7.73e-03 1.60e-13 8.59e-04 65s
24 2.58430337e+06 2.58479463e+06 9.20e-07 2.33e-13 3.54e-04 66s
25 2.58446838e+06 2.58458545e+06 2.20e-07 2.79e-13 8.44e-05 67s
26 2.58451567e+06 2.58454635e+06 3.97e-08 3.05e-13 2.21e-05 68s
27 2.58452313e+06 2.58453191e+06 1.46e-08 3.72e-13 6.33e-06 69s
28 2.58452624e+06 2.58452953e+06 4.79e-09 2.32e-13 2.37e-06 70s
29 2.58452745e+06 2.58452849e+06 2.61e-09 2.32e-13 7.53e-07 71s
30 2.58452752e+06 2.58452820e+06 3.35e-08 3.38e-13 4.92e-07 72s
31 2.58452752e+06 2.58452820e+06 2.50e-07 3.22e-13 4.84e-07 73s
32 2.58452762e+06 2.58452801e+06 1.72e-07 3.43e-13 2.84e-07 75s
33 2.58452763e+06 2.58452800e+06 5.90e-07 3.20e-13 2.71e-07 76s
34 2.58452765e+06 2.58452793e+06 5.22e-07 3.68e-13 2.00e-07 78s
35 2.58452766e+06 2.58452793e+06 5.09e-07 3.19e-13 1.95e-07 79s
36 2.58452766e+06 2.58452792e+06 4.83e-07 3.60e-13 1.85e-07 81s
37 2.58452769e+06 2.58452792e+06 4.13e-06 3.20e-13 1.66e-07 82s
Barrier solved model in 37 iterations and 81.87 seconds
Optimal objective 2.58452769e+06
Root crossover log...
237593 DPushes remaining with DInf 3.9308713e-03 83s
0 DPushes remaining with DInf 0.0000000e+00 85s
91298 PPushes remaining with PInf 4.8951965e-02 85s
30834 PPushes remaining with PInf 1.4355401e-02 85s
0 PPushes remaining with PInf 1.5133022e-03 90s
Push phase complete: Pinf 1.5133022e-03, Dinf 2.9615843e+02 90s
Root simplex log...
Iteration Objective Primal Inf. Dual Inf. Time
239802 2.5845278e+06 0.000000e+00 2.961584e+02 90s
240250 2.5845278e+06 0.000000e+00 0.000000e+00 91s
241074 2.5845278e+06 0.000000e+00 0.000000e+00 93s
Extra 824 simplex iterations after uncrush
Concurrent spin time: 11.22s (can be avoided by choosing Method=3)
Solved with barrier
Root relaxation: objective 2.584528e+06, 241074 iterations, 65.99 seconds
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 2584527.83 0 21126 - 2584527.83 - - 299s
0 0 2583846.71 0 13759 - 2583846.71 - - 638s
0 0 2583629.96 0 10291 - 2583629.96 - - 717s
0 0 2583433.76 0 7875 - 2583433.76 - - 855s
0 0 2583432.29 0 7848 - 2583432.29 - - 860s
0 0 2583408.59 0 7004 - 2583408.59 - - 884s
0 0 2583407.52 0 6976 - 2583407.52 - - 888s
0 0 2583404.19 0 6927 - 2583404.19 - - 908s
0 0 2583403.04 0 6912 - 2583403.04 - - 912s
0 0 2583402.24 0 6496 - 2583402.24 - - 1105s
H 0 0 -203668.0077 2583402.24 1368% - 2397s
H 0 0 -202763.4149 2583402.24 1374% - 2632s
0 2 2583402.24 0 6496 -202763.41 2583402.24 1374% - 2652s
H 1 4 -202397.3024 2583401.91 1376% 708 2656s
H 3 6 -202321.7237 2583401.00 1377% 253 2776s
H 4 6 -202285.0139 2583401.00 1377% 904 2776s
7 10 2583325.63 4 6474 -202285.01 2583401.00 1377% 1135 2780s
H 8 10 -202230.7922 2583401.00 1377% 993 2780s
11 15 2583308.73 6 6465 -202230.79 2583401.00 1377% 726 2785s
14 21 2583304.37 7 6461 -202230.79 2583401.00 1377% 575 2791s
H 20 25 -189780.8762 2583401.00 1461% 411 2804s
H 24 50 -179259.8077 2583401.00 1541% 400 2828s
49 96 2583281.89 23 6418 -179259.81 2583401.00 1541% 214 2856s
95 108 2583278.62 45 6397 -179259.81 2583401.00 1541% 113 3131s
107 154 2583277.87 51 6391 -179259.81 2583401.00 1541% 101 3158s
H 153 200 -171454.6927 2583401.00 1607% 71.2 3184s
H 158 200 -170781.2749 2583401.00 1613% 69.0 3184s
H 160 200 -170131.1649 2583401.00 1618% 68.2 3184s
H 162 200 -169744.5324 2583401.00 1622% 67.4 3184s
H 193 200 -169435.2567 2583401.00 1625% 57.2 3184s
199 204 2583276.57 94 6385 -169435.26 2583401.00 1625% 55.6 3459s
H 203 250 -169372.2384 2583401.00 1625% 54.5 3489s
H 204 250 -164733.8204 2583401.00 1668% 54.3 3489s
H 206 250 -161122.4922 2583401.00 1703% 53.8 3489s
H 207 250 -160752.9104 2583401.00 1707% 53.5 3489s
H 216 250 -160721.9384 2583401.00 1707% 51.4 3490s
H 222 250 -159966.4944 2583401.00 1715% 50.1 3490s
H 240 250 -159362.7037 2583401.00 1721% 46.5 3490s
249 296 2583276.43 118 6381 -159362.70 2583401.00 1721% 44.9 3517s
295 308 2583276.20 141 6378 -159362.70 2583401.00 1721% 38.3 3801s
H 305 308 -150590.6579 2583401.00 1816% 37.1 3801s
307 354 2583276.11 147 6374 -150590.66 2583401.00 1816% 36.9 3831s
H 353 399 -144310.1259 2583401.00 1890% 32.7 3859s
H 360 399 -144139.8332 2583401.00 1892% 32.3 3859s
H 366 399 -141997.3542 2583401.00 1919% 32.0 3859s
399 403 2583265.11 182 6374 -141997.35 2583401.00 1919% 29.9 4141s
403 449 2583264.43 183 6374 -141997.35 2583401.00 1919% 29.8 4172s
H 415 449 -141917.6012 2583401.00 1920% 29.3 4172s
H 427 449 -141774.8232 2583401.00 1922% 28.9 4172s
H 448 449 -141723.3827 2583401.00 1923% 28.1 4172s
449 495 2583258.02 198 6374 -141723.38 2583401.00 1923% 28.1 4202s
H 466 495 -141643.3389 2583401.00 1924% 27.6 4202s
H 478 495 -141288.8407 2583401.00 1928% 27.2 4202s
495 507 2583250.19 213 6374 -141288.84 2583401.00 1928% 26.9 4478s
507 553 2583248.15 217 6374 -141288.84 2583401.00 1928% 26.5 4486s
553 599 2583240.33 233 6376 -141288.84 2583401.00 1928% 25.5 4513s
H 554 599 -134116.4197 2583401.00 2026% 25.4 4514s
H 557 599 -133432.7742 2583401.00 2036% 25.3 4514s
H 561 599 -131957.1207 2583401.00 2058% 25.2 4514s
H 569 599 -131014.4132 2583401.00 2072% 25.1 4514s
599 603 2583232.55 248 6374 -131014.41 2583401.00 2072% 24.5 4789s
603 649 2583231.85 249 6374 -131014.41 2583401.00 2072% 24.5 4797s
649 695 2583224.03 265 6376 -131014.41 2583401.00 2072% 23.7 4820s
695 707 2583216.25 280 6374 -131014.41 2583401.00 2072% 23.0 5095s
707 753 2583214.21 284 6374 -131014.41 2583401.00 2072% 22.9 5103s
Created node file directory './grbnodes0'
H 753 799 -121197.4674 2583401.00 2232% 22.3 5130s
H 760 799 -121162.9709 2583401.00 2232% 22.2 5130s
H 765 799 -120071.7969 2583401.00 2252% 22.2 5130s
H 779 799 -119957.1842 2583401.00 2254% 22.0 5130s
H 788 799 -119898.9847 2583401.00 2255% 21.9 5130s
799 803 2583198.56 315 6376 -119898.98 2583401.00 2255% 21.8 5417s
803 849 2583197.91 316 6374 -119898.98 2583401.00 2255% 21.7 5425s
849 895 2583190.08 331 6374 -119898.98 2583401.00 2255% 21.3 5451s
895 907 2583182.26 347 6376 -119898.98 2583401.00 2255% 21.0 5733s
907 953 2583180.22 351 6376 -119898.98 2583401.00 2255% 20.9 5742s
953 999 2583172.45 366 6374 -119898.98 2583401.00 2255% 20.5 5767s
H 956 999 -111652.6969 2583401.00 2414% 20.5 5767s
H 957 999 -111627.2254 2583401.00 2414% 20.5 5767s
H 963 999 -111360.4544 2583401.00 2420% 20.5 5767s
999 1003 2583164.61 381 6374 -111360.45 2583401.00 2420% 20.3 6178s
H 1003 1021 -111358.2002 2583401.00 2420% 20.2 6193s
H 1021 1067 -104501.4402 2583401.00 2572% 20.1 6221s
H 1044 1067 -85867.63242 2583401.00 3109% 19.9 6221s
1067 1113 2583155.77 399 6376 -85867.632 2583401.00 3109% 19.8 6236s
H 1068 1113 -85651.84642 2583401.00 3116% 19.8 6236s
H 1071 1113 -82155.22792 2583401.00 3245% 19.8 6236s
H 1090 1113 -81528.31017 2583401.00 3269% 19.7 6236s
H 1093 1113 -81030.82567 2583401.00 3288% 19.6 6236s
1113 1159 2583148.00 414 6374 -81030.826 2583401.00 3288% 19.5 6244s
1159 1205 2583140.16 429 6374 -81030.826 2583401.00 3288% 19.3 6255s
1205 1251 2583132.34 445 6376 -81030.826 2583401.00 3288% 19.1 6263s
1251 1297 2583124.56 460 6374 -81030.826 2583401.00 3288% 18.9 6273s
1297 1305 2583116.73 475 6374 -81030.826 2583401.00 3288% 18.7 6552s
1305 1351 2583115.40 478 6374 -81030.826 2583401.00 3288% 18.6 6561s
1351 1391 2583107.56 493 6374 -81030.826 2583401.00 3288% 18.5 6587s
H 1352 1391 -81011.40967 2583401.00 3289% 18.5 6587s
H 1356 1391 -80998.14417 2583401.00 3289% 18.5 6587s
H 1359 1391 -80883.22217 2583401.00 3294% 18.5 6587s
H 1361 1391 -77727.00667 2583401.00 3424% 18.5 6587s
H 1362 1391 -76724.45067 2583401.00 3467% 18.4 6587s
1391 1411 2583100.76 507 6376 -76724.451 2583401.00 3467% 18.4 6850s
1411 1457 2583097.37 513 6374 -76724.451 2583401.00 3467% 18.3 6858s
1457 1503 2583089.55 529 6376 -76724.451 2583401.00 3467% 18.1 6884s
1480 1503 2583142.18 545 6362 -76724.451 2583401.00 3467% 18.1 6885s
1503 1549 2583081.78 544 6374 -76724.451 2583401.00 3467% 18.0 6891s
1549 1595 2583073.94 559 6374 -76724.451 2583401.00 3467% 17.9 6903s
1595 1607 2583066.12 575 6376 -76724.451 2583401.00 3467% 17.8 7160s
1607 1653 2583064.08 579 6376 -76724.451 2583401.00 3467% 17.8 7167s
1653 1696 2583056.31 594 6374 -76724.451 2583401.00 3467% 17.6 7193s
H 1654 1696 -76400.87642 2583401.00 3481% 17.6 7193s
H 1662 1696 -70629.05692 2583401.00 3758% 17.6 7194s
1696 1706 2583053.42 606 6372 -70629.057 2583401.00 3758% 17.5 7474s
1706 1752 2583052.74 610 6369 -70629.057 2583401.00 3758% 17.5 7482s
1752 1798 2583052.24 627 6368 -70629.057 2583401.00 3758% 17.2 7505s
1798 1804 2583052.15 643 6368 -70629.057 2583401.00 3758% 16.8 7785s
H 1799 1804 -70610.95867 2583401.00 3759% 16.8 7785s
1804 1850 2583052.14 645 6368 -70610.959 2583401.00 3759% 16.8 7792s
1850 1896 2583052.06 660 6368 -70610.959 2583401.00 3759% 16.4 7818s
H 1896 1906 -70551.93092 2583401.00 3762% 16.0 8097s
1906 1952 2583051.60 684 6368 -70551.931 2583401.00 3762% 15.9 8107s
1952 1998 2583049.73 703 6372 -70551.931 2583401.00 3762% 15.7 8133s
H 1998 2004 -70218.66742 2583401.00 3779% 15.6 8396s
H 2001 2004 -64700.49667 2583401.00 4093% 15.6 8396s
H 2003 2004 -64111.06367 2583401.00 4130% 15.6 8396s
2004 2050 2583046.41 720 6367 -64111.064 2583401.00 4130% 15.6 8403s
2050 2096 2583043.42 735 6367 -64111.064 2583401.00 4130% 15.4 8428s
H 2096 2106 -63969.85442 2583401.00 4138% 15.3 8708s
H 2099 2106 -60923.24117 2583401.00 4340% 15.3 8708s
2106 2152 2583039.79 754 6367 -60923.241 2583401.00 4340% 15.2 8716s
2152 2198 2583036.79 769 6367 -60923.241 2583401.00 4340% 15.1 8741s
H 2198 2204 -60825.06617 2583401.00 4347% 15.0 9025s
2204 2250 2583033.37 787 6372 -60825.066 2583401.00 4347% 15.0 9033s
2250 2296 2583030.44 802 6367 -60825.066 2583401.00 4347% 14.9 9057s
H 2296 2306 -60773.47267 2583401.00 4351% 14.7 9338s
H 2297 2306 -60767.50642 2583401.00 4351% 14.7 9338s
H 2298 2306 -60702.38017 2583401.00 4356% 14.7 9339s
2306 2352 2583026.75 821 6372 -60702.380 2583401.00 4356% 14.7 9346s
2352 2394 2583023.82 836 6367 -60702.380 2583401.00 4356% 14.6 9373s
H 2354 2394 -60635.40067 2583401.00 4361% 14.6 9373s
H 2361 2394 -56243.73392 2583401.00 4693% 14.6 9373s
H 2365 2394 -55618.78992 2583401.00 4745% 14.6 9373s
H 2378 2394 -55566.97092 2583401.00 4749% 14.6 9373s
H 2390 2394 -54751.23842 2583401.00 4818% 14.5 9374s
2394 2408 2583021.09 850 6367 -54751.238 2583401.00 4818% 14.5 9657s
2408 2454 2583020.13 855 6372 -54751.238 2583401.00 4818% 14.5 9667s
2454 2500 2583017.20 870 6367 -54751.238 2583401.00 4818% 14.4 9689s
2477 2500 2583089.17 889 6350 -54751.238 2583401.00 4818% 14.4 9690s
2500 2502 2583014.20 885 6367 -54751.238 2583401.00 4818% 14.3 9971s
2502 2548 2583014.08 886 6367 -54751.238 2583401.00 4818% 14.3 9979s
2548 2594 2583011.09 901 6367 -54751.238 2583401.00 4818% 14.2 10006s
H 2551 2594 -50689.66667 2583401.00 5197% 14.2 10006s
2594 2608 2583008.05 917 6372 -50689.667 2583401.00 5197% 14.1 10285s
2608 2654 2583007.19 921 6367 -50689.667 2583401.00 5197% 14.1 10294s
2631 2654 2583088.76 940 6350 -50689.667 2583401.00 5197% 14.1 10295s
2654 2700 2583004.16 937 6372 -50689.667 2583401.00 5197% 14.0 10319s
2700 2724 2583001.23 952 6367 -50689.667 2583401.00 5197% 13.9 10553s
2724 2770 2582998.23 967 6367 -50689.667 2583401.00 5197% 13.9 10563s
2770 2816 2582995.20 983 6372 -50689.667 2583401.00 5197% 13.8 10590s
H 2777 2816 -43981.26117 2583401.00 5974% 13.8 10590s
H 2787 2816 -43886.17442 2583401.00 5987% 13.8 10590s
H 2791 2816 -43588.45817 2583401.00 6027% 13.8 10591s
2816 2862 2582992.27 998 6367 -43588.458 2583401.00 6027% 13.8 10608s
2862 2908 2582989.28 1013 6367 -43588.458 2583401.00 6027% 13.8 10616s
2908 2954 2582986.24 1029 6372 -43588.458 2583401.00 6027% 13.7 10626s
2954 3000 2582983.31 1044 6367 -43588.458 2583401.00 6027% 13.7 10635s
440387 436112 2579248.59 108164 3019 53715.8856 2583353.30 4709% 6.8 508479s
440435 436159 2579248.42 108176 3019 53715.8856 2583353.30 4709% 6.8 508503s
440482 436206 2579248.20 108187 3018 53715.8856 2583353.30 4709% 6.8 508524s
[...]
451712 447411 2578926.66 110890 2973 53715.8856 2583353.30 4709% 6.8 514740s
451759 447458 2578926.42 110902 2973 53715.8856 2583353.30 4709% 6.8 514763s0 -
Hi David,
It is the feasible point (Incumbent) that seems to be the problem here so setting MIPFocus to 1 is good. You could try the new no relaxation heuristic. I would start with setting the NoRelHeurTime parameter to 3600. This provides 3600 seconds for the no relaxation heuristic which tries to find feasible solution before starting the B&B algorithm. However, this requires an update to Gurobi version 9.1. Other than that, you might also be interested in the documentation on most important parameters for MIPs.
Your problem is a quadratic one and has >400k continuous and >200k discrete variables with over 1 mio nonzeros. Thus, a long solution time is rather expected.
Best regards,
Jaromił0
投稿コメントは受け付けていません。
コメント
4件のコメント