Skip to main content

What happens after root relaxation has been solved? Long time before exploring further nodes according to log

Answered

Comments

4 comments

  • Matthias Miltenberger
    Gurobi Staff Gurobi Staff

    Hi Hendrik,

    Yes, Gurobi is processing the root node while printing those "0   0" lines. Here's an excerpt from our MIP Logging documentation:

    Note that the explored node count often stays at 0 for an extended period. This means that the Gurobi MIP solver is processing the root node. The Gurobi solver can often expend a significant amount of effort on the root node, generating cutting planes and trying various heuristics in order to reduce the size of the subsequent branch-and-cut tree.

    I hope that answers your question. To reduce the time spent in the root node and start with the branch-and-bound process earlier, you can try reducing the number of cuts being added to the problem via parameters Cuts and CutPasses.

    Cheers,
    Matthias

    1
  • Hendrik Weber
    Gurobi-versary
    First Question
    Conversationalist

    Ah yes, thank you so much for the quick response. I probably should have read the documentation first :)
    Thanks!
    Hendrik

    0
  • Youssef Hebaish
    Gurobi-versary
    First Comment

    Hi Matthias Miltenberger

    I'm running a model and it seems to be stuck at the same stage for a long time. What does that mean exactly? Did the model find a feasible solution? 

     

    Thanks in advance!

    Optimize a model with 443880 rows, 125280 columns and 86978853 nonzeros
    Model fingerprint: 0x73f15bd1
    Variable types: 0 continuous, 125280 integer (125280 binary)
    Coefficient statistics:
      Matrix range     [1e+00, 5e+00]
      Objective range  [1e+00, 7e+02]
      Bounds range     [1e+00, 1e+00]
      RHS range        [1e+00, 3e+02]
    Presolve removed 41398 rows and 70660 columns (presolve time = 6s) ...
    Presolve removed 248410 rows and 70795 columns (presolve time = 10s) ...
    Presolve removed 272651 rows and 70795 columns (presolve time = 15s) ...
    Presolve removed 324353 rows and 77561 columns (presolve time = 20s) ...
    Presolve removed 327660 rows and 77562 columns (presolve time = 25s) ...
    Presolve removed 327660 rows and 77562 columns (presolve time = 30s) ...
    Presolve removed 374148 rows and 82836 columns (presolve time = 35s) ...
    Presolve removed 379194 rows and 82867 columns (presolve time = 40s) ...
    Presolve removed 379250 rows and 82895 columns (presolve time = 45s) ...
    Presolve removed 379250 rows and 82895 columns (presolve time = 50s) ...
    Presolve removed 389075 rows and 82947 columns (presolve time = 55s) ...
    Presolve removed 389075 rows and 82983 columns (presolve time = 60s) ...
    Presolve removed 389181 rows and 83032 columns (presolve time = 65s) ...
    Presolve removed 390498 rows and 83073 columns (presolve time = 70s) ...
    Presolve removed 390498 rows and 83073 columns (presolve time = 75s) ...
    Presolve removed 390787 rows and 83111 columns (presolve time = 80s) ...
    Presolve removed 390799 rows and 83111 columns (presolve time = 85s) ...
    Presolve removed 380919 rows and 73231 columns
    Presolve time: 85.94s
    Presolved: 62961 rows, 52049 columns, 8357376 nonzeros
    Variable types: 0 continuous, 52049 integer (52022 binary)
    Deterministic concurrent LP optimizer: primal simplex, dual simplex, and barrier
    Showing barrier log only...

    Root barrier log...


    Barrier performed 0 iterations in 92.98 seconds (332.38 work units)
    Barrier solve interrupted - model solved by another algorithm

    Concurrent spin time: 0.32s (can be avoided by choosing Method=3)

    Solved with dual simplex

    Root simplex log...

    Iteration    Objective       Primal Inf.    Dual Inf.      Time
        2222    1.8998000e+04   0.000000e+00   0.000000e+00     93s

    Root relaxation: objective 1.899800e+04, 2222 iterations, 2.26 seconds (4.49 work units)
    Total elapsed time = 95.37s

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

         0     0 18998.0000    0  903          - 18998.0000      -     -   98s
         0     0 18998.0000    0  839          - 18998.0000      -     -  103s
         0     0 18998.0000    0  812          - 18998.0000      -     -  105s
         0     0 18998.0000    0  732          - 18998.0000      -     -  112s
         0     0 18998.0000    0  745          - 18998.0000      -     -  113s
         0     0 18998.0000    0  710          - 18998.0000      -     -  120s
         0     0 18998.0000    0  709          - 18998.0000      -     -  121s
         0     0 18998.0000    0  707          - 18998.0000      -     -  127s
         0     0 18998.0000    0  713          - 18998.0000      -     -  128s
         0     0 18998.0000    0  695          - 18998.0000      -     -  135s
         0     0 18998.0000    0  695          - 18998.0000      -     -  142s
         0     2 18998.0000    0  695          - 18998.0000      -     -  180s
        39    24 18998.0000    7  717          - 18998.0000      -   287  185s
       114    84 18998.0000   15  710          - 18998.0000      -   132  190s
       228   136 18998.0000   27  710          - 18998.0000      -  76.0  197s
       282   183 infeasible   33               - 18998.0000      -  69.2  202s
       385   278 18998.0000   40  709          - 18998.0000      -  67.5  209s
       533   316 infeasible   52               - 18998.0000      -  60.6  217s
       672   386 19002.0580   61  733          - 18998.0000      -  65.6  227s
       876   485 19005.0882   76  703          - 18998.0000      -  62.8  238s
      1085   592 infeasible   94               - 18998.0000      -  59.6  249s
      1299   729 19021.0000  107  680          - 18998.0000      -  58.2  261s
      1561   858 19024.0250  129  685          - 18998.0000      -  53.9  274s
      1813  1042 19077.0000  145  630          - 18998.0000      -  51.6  287s
    0
  • Matthias Miltenberger
    Gurobi Staff Gurobi Staff

    Hi Youssef,

    Gurobi does not find a feasible solution to this model instance. You can see this from the \(\texttt{Incumbent}\) column and also that there is no gap - we need a primal solution (incumbent) and a dual bound (LP solution) to compute the gap.

    You can play around with different settings, e.g., MIPFocus, Heuristics, NoRelHeurTime, to make Gurobi spend more time and effort finding solutions.

    I hope that helps.

    Cheers,
    Matthias

    0

Please sign in to leave a comment.