What are postponed nodes?
Answered
I'm currently optimizing a MIP model, and this is how my MIP log looks like:
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 735.00007 0 218875 1231668.00 735.00007 100% - 21s
0 0 postponed 0 1231668.00 735.00007 100% - 149s
0 2 postponed 0 1231668.00 735.00007 100% - 329s
1 4 postponed 1 1231668.00 735.00007 100% 0.0 428s
3 8 postponed 2 1231668.00 735.00007 100% 0.0 574s
7 16 postponed 3 1231668.00 735.00007 100% 0.0 697s
Now I wonder what it means that my nodes / objective values are "postponed". Did Gurobi determine that it would be unnecessary effort to compute the objective values of the respective nodes? Does this indicate a problem with my model? I would expect this to be explained at https://www.gurobi.com/documentation/9.1/refman/mip_logging.html, but could find no mention of postponed nodes there.
Thanks, Lukas
-
HI Lukas,
A node is postponed if numerical trouble were encountered during the solution of the relaxation of this node. This may be due to very large/small variable bounds or very large/small coefficients. Instead of trying to do computations with possibly wrong numerical values, Gurobi postpones this particular node with the hope that it can prune this node or solve the numerical problem through information gathered in the B&B tree.
Could you post the first lines of your LOG file showing the model statistics, i.e, the number of rows, columns, and nonzeros together with the coefficient ranges?
Best regards,
Jaromił2 -
Hi Jaromił,
This is the size of my model:
Optimize a model with 663497 rows, 331973 columns and 2427819 nonzeros
Model fingerprint: 0xb4fd3671
Model has 296 SOS constraints
Variable types: 111748 continuous, 220225 integer (220224 binary)I realize that this is a rather large model. I'm giving Gurobi 128 threads to optimize this model, though it looks like most of the time it's doing something single-threaded. The coefficients don't look too bad:
Coefficient statistics:
Matrix range [1e+00, 3e+03]
Objective range [1e+00, 5e+00]
Bounds range [1e+00, 3e+03]
RHS range [1e+00, 3e+03]I did have some numeric trouble earlier with coefficients of up to 10^8, reformulated parts of my model, and now at least the root relaxation doesn't give me the "numerical trouble encountered" message anymore.
Is the model just too large?
Thanks, Lukas
0 -
Hi Lukas,
The size of the model should not be the reason for the postponed nodes. You are saying that you reformulated parts of your model. What exactly did you do to perform the reformulation? Note that reformulating a constraint
\[x = 10^8 y\]
as
\[\begin{align} x &= 10^4 x' \\ x' &= 10^4 y \end{align}\]
does not help as you are not really scaling the coefficient but rather trying to hide the large coefficient.
It may also happen that your coefficient matrix is almost singular causing numerical issues.
Our Numerical Guide might catch your interest.
Best regards,
Jaromił0 -
Thanks again! Indeed, presolving seems to introduce some large variable bounds:
gurobi> m = read("gurobi.mps")
Read MPS format model from file gurobi.mps
Reading time = 1.51 seconds
: 663497 rows, 331973 columns, 2427819 nonzeros
gurobi> m.printStats()
Statistics for model Unnamed :
Linear constraint matrix : 663497 Constrs, 331973 Vars, 2427819 NZs
Variable types : 111748 Continuous, 220225 Integer (220224 Binary)
SOS constraints : 296
Matrix coefficient range : [ 1, 2830.51 ]
Objective coefficient range : [ 1, 5 ]
Variable bound range : [ 1, 2830.51 ]
RHS coefficient range : [ 1, 2830.51 ]And then, after presolving:
gurobi> m = m.presolve()
Presolve removed 591 rows and 148 columns (presolve time = 5s) ...
Presolve added 0 rows and 146 columns
Presolve removed 15 rows and 0 columns
Presolve time: 6.37s
gurobi> m.printStats()
Statistics for model _pre :
Linear constraint matrix : 663482 Constrs, 332119 Vars, 2323938 NZs
Variable types : 111748 Continuous, 220371 Integer (220370 Binary)
Matrix coefficient range : [ 1, 2830.51 ]
Objective coefficient range : [ 1, 5 ]
Variable bound range : [ 1, 9.97035e+07 ]
RHS coefficient range : [ 1, 2830.51 ]My best guess is that for some of the variables for which I did not supply a bound, presolving infers some (very large) upper bound. Two questions related to this:
- Is this even bad? Are auto-inferred variable bounds added to the constraint matrix? If so, this would of course deteriorate matrix conditioning in this case.
- Can I somehow prevent Gurobi from doing that? You can see that presolving doesn't do too much for this model, so completely disabling presolving might be a good idea in this case, but I think it would be great if one could just forbid Gurobi to worsen the matrix conditioning in this way.
0 -
Hi Lukas,
Auto-inferred bounds are added to the presolved model. You can certainly try turning off Presolve by setting the parameter to 0 and you could also try setting the parameter Aggregate to 0. Do you provide bounds for all variables, especially the discrete ones? If not, try providing bounds for those to see whether this helps.
Best regards,
Jaromił0 -
Hi Jaromlł,
Thanks. The variables for which bounds were inferred were indeed variables of my model. Putting some reasonable upper bounds on them solved the problem with the huge bounds after presolving. I still can't quite get this model to behave, but I'll open a different question for other problems.
Thanks again,
Lukas
0 -
Hello,
I have encountered a similar issue, my model was postponing all nodes and never computed a result. The model did not have any severe numerical issues (all variables within relative range up to 10^7).
Additionally, the model worked fine when a part of the formulation were removed from the objective function, but rather kept as a constraint (essentially making the optimization problem into a feasibility problem).What was causing the issue were multiple SOS1 constraints (about 400 in total) in a sort of a hierarchical system of constraints, that served to select a weighed maximum of sorts.
I was able to reformulate the computation of maxima using big-M constraints which completely solved the issue of postponed nodes and the model now solves easily.
Hope this might help some other people struggling with postponed nodes.
Sincerely, Jiří0
Please sign in to leave a comment.
Comments
7 comments