メインコンテンツへスキップ

quicksum contraint slows solver.

回答済み

コメント

4件のコメント

  • 正式なコメント
    Simranjit Kaur
    • Gurobi Staff Gurobi Staff
    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?.
  • Jaromił Najman
    • Gurobi Staff Gurobi Staff

    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
  • David Mejía
    • Gurobi-versary
    • Conversationalist
    • Curious

    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 514763s
    0
  • Jaromił Najman
    • Gurobi Staff Gurobi Staff

    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

投稿コメントは受け付けていません。