Skip to main content

Advice on how to speed up of MILP (Pyomo with Gurobi)

Answered

Comments

5 comments

  • Fabian Schmid
    • Gurobi-versary
    • Conversationalist
    • First Question

    Following the gurobi log for the model with larger energy system component sizes.
    I increase MIPGap to 2e-3 to reduce runtime. But it is still obvious that Gurobi needs most of the time to close the final steps of MIPGap.

    Operational optimization:  2023-03-31 11:15:15  Create model
    [    0.00] Start
    [+  21.17] Built model
           44.18 seconds required for presolve
    Set parameter MIPGap to value 0.002
    Gurobi Optimizer version 10.0.1 build v10.0.1rc0 (win64)

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

    Optimize a model with 394203 rows, 280320 columns and 849720 nonzeros
    Model fingerprint: 0xec6edcb1
    Variable types: 236520 continuous, 43800 integer (43800 binary)
    Coefficient statistics:
      Matrix range     [5e-05, 1e+02]
      Objective range  [8e-02, 4e-01]
      Bounds range     [1e-01, 1e+00]
      RHS range        [1e-03, 2e+02]
    Presolve removed 177271 rows and 106921 columns
    Presolve time: 1.91s
    Presolved: 216932 rows, 173399 columns, 627906 nonzeros
    Variable types: 138359 continuous, 35040 integer (35040 binary)
    Deterministic concurrent LP optimizer: primal simplex, dual simplex, and barrier
    Showing barrier log only...

    Root barrier log...

    Ordering time: 0.06s

    Barrier statistics:
     AA' NZ     : 7.675e+05
     Factor NZ  : 1.994e+06 (roughly 170 MB of memory)
     Factor Ops : 2.265e+07 (less than 1 second per iteration)
     Threads    : 1

                      Objective                Residual
    Iter       Primal          Dual         Primal    Dual     Compl     Time
       0   2.45125532e+05 -1.39920366e+06  1.64e+01 6.40e-01  1.94e+01     4s
       1   4.96627402e+04 -5.69950068e+05  9.31e-01 3.24e-12  1.99e+00     4s
       2   5.18358830e+03 -1.26332669e+05  1.78e-01 2.09e-12  3.60e-01     4s
       3   3.82356060e+03 -6.20434619e+04  9.58e-02 2.41e-12  1.95e-01     4s
       4   3.45107074e+03 -3.57925084e+04  3.97e-02 1.93e-12  1.08e-01     4s
       5   3.27937901e+03 -1.41215494e+04  2.11e-02 1.64e-12  5.05e-02     5s
       6   2.58142443e+03 -3.68566402e+03  9.58e-03 1.28e-12  1.94e-02     5s
       7   2.03210208e+03 -1.57522820e+02  3.04e-03 1.20e-12  6.74e-03     5s
       8   1.81230783e+03  6.45056512e+02  1.38e-03 1.31e-12  3.39e-03     5s
       9   1.73008747e+03  1.04709209e+03  9.33e-04 1.36e-12  2.02e-03     5s
      10   1.67573648e+03  1.31598653e+03  4.98e-04 1.42e-12  1.07e-03     5s
      11   1.63629627e+03  1.42403637e+03  2.10e-04 1.43e-12  5.78e-04     6s
      12   1.61619020e+03  1.52188124e+03  8.65e-05 1.30e-12  2.54e-04     6s
      13   1.60792931e+03  1.56116172e+03  4.46e-05 1.24e-12  1.28e-04     6s
      14   1.60392054e+03  1.57377593e+03  2.72e-05 1.39e-12  8.13e-05     6s
      15   1.60130056e+03  1.58409986e+03  1.60e-05 1.42e-12  4.67e-05     7s
      16   1.59993945e+03  1.59118177e+03  1.05e-05 1.35e-12  2.56e-05     7s
      17   1.59887686e+03  1.59300101e+03  6.50e-06 1.51e-12  1.68e-05     7s
      18   1.59812399e+03  1.59499507e+03  3.86e-06 1.34e-12  9.22e-06     7s
      19   1.59772259e+03  1.59589958e+03  2.39e-06 1.31e-12  5.48e-06     7s
      20   1.59755894e+03  1.59633353e+03  1.82e-06 1.38e-12  3.84e-06     8s
      21   1.59738047e+03  1.59654978e+03  1.27e-06 1.51e-12  2.63e-06     8s
      22   1.59727934e+03  1.59673521e+03  9.02e-07 1.42e-12  1.78e-06     8s
      23   1.59712908e+03  1.59688683e+03  3.94e-07 1.18e-12  7.86e-07     8s
      24   1.59708170e+03  1.59695465e+03  2.32e-07 1.18e-12  4.32e-07     8s
      25   1.59706959e+03  1.59699278e+03  1.91e-07 1.10e-12  3.00e-07     9s
      26   1.59704888e+03  1.59699591e+03  1.23e-07 1.57e-12  2.00e-07     9s
      27   1.59704216e+03  1.59700084e+03  1.00e-07 1.64e-12  1.59e-07     9s
      28   1.59703995e+03  1.59700458e+03  9.30e-08 1.53e-12  1.42e-07     9s
      29   1.59701348e+03  1.59700955e+03  9.49e-09 9.02e-13  1.52e-08     9s
      30   1.59701020e+03  1.59700991e+03  1.36e-09 9.01e-13  6.72e-10    10s
      31   1.59701003e+03  1.59701002e+03  5.75e-11 8.94e-13  2.10e-11    10s

    Barrier solved model in 31 iterations and 9.97 seconds (5.40 work units)
    Optimal objective 1.59701003e+03


    Root crossover log...

       74619 DPushes remaining with DInf 0.0000000e+00                10s
           0 DPushes remaining with DInf 0.0000000e+00                12s

        5629 PPushes remaining with PInf 1.0123747e-04                12s
           0 PPushes remaining with PInf 0.0000000e+00                12s

      Push phase complete: Pinf 0.0000000e+00, Dinf 1.3812786e-11     12s


    Root simplex log...

    Iteration    Objective       Primal Inf.    Dual Inf.      Time
       53802    1.5970100e+03   0.000000e+00   0.000000e+00     12s
    Concurrent spin time: 0.02s

    Solved with barrier
       53802    1.5970100e+03   0.000000e+00   0.000000e+00     12s

    Root relaxation: objective 1.597010e+03, 53802 iterations, 9.45 seconds (6.48 work units)

        Nodes    |    Current Node    |     Objective Bounds      |     Work
     Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

         0     0 1597.01002    0  870          - 1597.01002      -     -   15s
    H    0     0                    1638.4332602 1597.01002  2.53%     -   16s
    H    0     0                    1636.6899077 1597.01002  2.42%     -   18s
         0     0 1602.09632    0  294 1636.68991 1602.09632  2.11%     -   21s
    H    0     0                    1612.6719822 1602.09632  0.66%     -   22s
         0     0 1602.11074    0  292 1612.67198 1602.11074  0.65%     -   23s
         0     0 1602.51257    0  253 1612.67198 1602.51257  0.63%     -   24s
    H    0     0                    1606.9854239 1602.51257  0.28%     -   25s
         0     0 1602.51474    0  251 1606.98542 1602.51474  0.28%     -   25s
         0     0 1602.63747    0  244 1606.98542 1602.63747  0.27%     -   29s
         0     0 1602.64233    0  244 1606.98542 1602.64233  0.27%     -   29s
         0     0 1602.65455    0  244 1606.98542 1602.65455  0.27%     -   32s
    H    0     0                    1606.6696528 1602.65455  0.25%     -   33s
         0     0 1602.65941    0  242 1606.66965 1602.65941  0.25%     -   34s
         0     0 1602.65941    0  242 1606.66965 1602.65941  0.25%     -   37s
         0     2 1602.65941    0  242 1606.66965 1602.65941  0.25%     -   40s
        23    28 1602.78294    6  232 1606.66965 1602.74693  0.24%  16.3   45s
        51    63 1602.84775   12  225 1606.66965 1602.74693  0.24%   8.6   50s
        72    92 1602.90630   18  216 1606.66965 1602.74693  0.24%   6.8   55s
       114   140 1603.00445   28  207 1606.66965 1602.74693  0.24%   5.5   60s
       155   184 1603.04658   37  195 1606.66965 1602.74693  0.24%   5.1   68s
       183   229 1603.05965   45  188 1606.66965 1602.74693  0.24%   4.7   71s
       306   354 1603.10793   76  161 1606.66965 1602.74693  0.24%   3.8   76s
       390   423 1603.12230   90  156 1606.66965 1602.74693  0.24%   3.6   81s
       462   501 1603.13117  108  151 1606.66965 1602.74693  0.24%   3.2   86s
       527   579 1603.16362  127  144 1606.66965 1602.74693  0.24%   3.2   91s
    H  578   583                    1606.6018997 1602.74693  0.24%   3.0   94s
    H  579   583                    1606.5835226 1602.74693  0.24%   3.0   94s
       582   625 1603.18185  141  142 1606.58352 1602.74693  0.24%   3.0   97s
       624   675 1603.18219  152  143 1606.58352 1602.74693  0.24%   3.0  100s
       708   773 1603.18375  173  144 1606.58352 1602.74693  0.24%   2.8  107s
       772   811 1603.19702  192  141 1606.58352 1602.74693  0.24%   2.7  110s
       873   930 1603.26482  223  132 1606.58352 1602.74693  0.24%   2.6  118s
       929   987 1603.27464  239  131 1606.58352 1602.74693  0.24%   2.6  121s
       986  1082 1603.27547  247  128 1606.58352 1602.74693  0.24%   2.5  125s
      1137  1258 1603.31566  285  118 1606.58352 1602.74693  0.24%   2.3  131s
      1257  1343 1603.34173  305  115 1606.58352 1602.74693  0.24%   2.3  135s
      1396  1451 1603.42187  324  107 1606.58352 1602.74693  0.24%   2.3  142s
      1450  1503 1603.46607  335  106 1606.58352 1602.74693  0.24%   2.3  157s
      1502  1595 1603.46653  348  107 1606.58352 1602.74693  0.24%   2.4  161s
      1594  1599 1603.46770  364  104 1606.58352 1602.74693  0.24%   2.4  225s
    H 1598  1632                    1606.5576683 1602.74693  0.24%   2.4  230s
      1631  1704 1603.47128  373  103 1606.55767 1602.74693  0.24%   2.4  235s
    H 1647  1704                    1606.5521773 1602.74693  0.24%   2.4  235s
    H 1685  1704                    1606.5413203 1602.74693  0.24%   2.3  235s
      1703  1782 1603.47187  389  102 1606.54132 1602.74693  0.24%   2.3  241s
      1781  1865 1603.47244  401  100 1606.54132 1602.74693  0.24%   2.3  247s
      1864  1949 1603.47268  418  100 1606.54132 1602.74693  0.24%   2.3  253s
      1948  2061 1603.49309  433  100 1606.54132 1602.74693  0.24%   2.3  261s
    H 1975  2061                    1606.5299138 1602.74693  0.24%   2.3  261s
      2060  2169 1603.56768  456   97 1606.52991 1602.74693  0.24%   2.3  268s
      2168  2278 1603.71159  480   94 1606.52991 1602.74693  0.24%   2.4  275s
      2277  2331 1603.80298  508   89 1606.52991 1602.74693  0.24%   2.4  282s
    H 2280  2331                    1606.5297627 1602.74693  0.24%   2.4  282s
    H 2294  2331                    1606.5198520 1602.74693  0.23%   2.4  282s
      2330  2440 1603.80323  522   88 1606.51985 1602.74693  0.23%   2.3  290s
    H 2335  2440                    1606.3674171 1602.74693  0.23%   2.3  290s
      2439  2623 1603.88712  548   86 1606.36742 1602.74693  0.23%   2.4  298s
      2622  2774 1603.96610  579   82 1606.36742 1602.74693  0.23%   2.4  305s
      2773  2922 1603.98755  600   81 1606.36742 1602.74693  0.23%   2.4  313s
      2921  3081 1604.00874  627   78 1606.36742 1602.74693  0.23%   2.5  322s
    H 2958  3081                    1606.2246328 1602.74693  0.22%   2.5  322s
      3080  3221 1604.37179  657   73 1606.22463 1602.74693  0.22%   2.5  331s
    H 3220  3368                    1606.2151581 1602.74693  0.22%   2.6  340s
      3367  3519 1604.31636  705   70 1606.21516 1602.74693  0.22%   2.6  350s
      3518  3678 1604.34502  731   68 1606.21516 1602.74693  0.22%   2.7  360s
      3677  3840 1604.44704  762   65 1606.21516 1602.74693  0.22%   2.7  370s
    H 3693  3840                    1606.1699375 1602.74693  0.21%   2.7  370s
    H 3839  3844                    1605.8834888 1602.74693  0.20%   2.7  450s
    H 3842  3844                    1605.8692771 1602.74693  0.19%   2.7  451s

    Cutting planes:
      Gomory: 120
      Implied bound: 199
      MIR: 314
      Flow cover: 1824
      Relax-and-lift: 115

    Explored 3843 nodes (66342 simplex iterations) in 451.27 seconds (326.43 work units)
    Thread count was 8 (of 8 available processors)

    Solution count 10: 1605.87 1605.88 1606.17 ... 1606.54

    Optimal solution found (tolerance 2.00e-03)
    Best objective 1.605869277090e+03, best bound 1.602746932564e+03, gap 0.1944%
          451.58 seconds required for solver
            3.46 seconds required for postsolve
    [+ 525.81] Wrote LP file and solved
    [+   0.08] Loaded results
    [+  84.37] Save model txt
    0
  • Maliheh Aramon
    • Gurobi Staff

    Hi Fabian,

    Are coefficeint statistics looking good enough/could they still have an impact on runtime? It would be possible to change the objective range to make it bigger than 1.

    The coefficient statistics of your models look reasonable. As stated in Gurobi’s numerical guidelines, the general rule of thumb is to have matrix coefficients to be contained in 6 orders of magnitude and ideally be within \([10^{-3}, 10^6]\). Please note that bad numbers in the model is only one of the potential sources of numerical challenges. Having almost parallel constraints in the model (see this example) is another potential source of numerical challenges. 

    Further, I wonder why model runtime is heavily dependent on energy system component sizes. 

    How does changing the component size reflect on the model? From your logs, it seems that it changes the constraint coefficients and as a result changes the feasible region. Therefore, it is not unexpected that the runtime varies depending on the feasible region.

    Do you have any recommendations how to handle this application of the MILP and how to deal with Gurbobi parameter setting in such a case?

    To close the gap sooner based on your last log, it would make sense to reach a high quality solution faster. You can consider experimenting with the parameters below:

    • NoRelHeurTime: Experiment with the NoRel heuristic which is effective in finding high-quality solutions before solving the root relaxation. You might start by setting this parameter to 100 seconds and then adjust based on its progress and effectiveness.
    • Heuristics: Increase the percentage of the total runtime spent on heuristic algorithms. You can start by bumping the default value to 0.1 or 0.2.
    • Cuts=1: Decrease the intensity of applying cutting plane generation 
    • MIPFocus=1: Change the focus of the optimizer to reaching a high quality solution faster
    • Presolve=2: Intensify the utilization of the presolve procedure techniques in the hope of reducing the presolved model size and tightening it

    Best regards,

    Maliheh

    0
  • Fabian Schmid
    • Gurobi-versary
    • Conversationalist
    • First Question

    Dear Maliheh,

    thank you very much for your feedback and recommendations.

    I will experiment with the parameters you mentioned, thanks for the support.

    Fabian

    0
  • Permanently deleted user
    • Gurobi-versary
    • First Comment

    Hi! I'm having right now the same kind of problem with the modelling of battery operations with resolution on the second...
    Did you find any solution to speed up the process?

    Andrea

    0
  • Fabian Schmid
    • Gurobi-versary
    • Conversationalist
    • First Question

    Hi Andrea,

    I could identify some improvements with the changing of the recommended solver settings.

    But nevertheless when the problem changes, identified parameters might be again not-optimal.
    Best
    Fabian

    0

Please sign in to leave a comment.