What is root relaxation in MILP models?
Answered
When I see the log of my milp model I see the following line appears:
Root relaxation: objective 2.551315e+03, 541 iterations, 0.01 seconds (0.01 work units)
What does this mean? How is it different from the LP relaxation? Or are they the same?
-
-
Gurobi Staff
Hi,
For a MILP, the root relaxation is the LP relaxation at the root node of the branch-and-bound tree, i.e., the first LP relaxation that is solved after presolving.
Best regards,
Mario0 -
-
Hello,
What about a convex MIQP? I am solving an MIQP and that line of the log says
Root relaxation: objective 1.406271e-02, 2275 iterations, 0.07 seconds (0.08 work units)
However, if I set all the binary variables to be continuous instead, I get a convex program whose optimal value is 29.3.On a similar note, the convex relaxation takes 0.23 seconds to solve, while the MIQP log after 8 seconds still says
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 29.13175 0 129 - 29.13175 - - 8s
So it seems that it has not started the branch and bound process yet, but is still working on solving the convex relaxation. Any suggestions to speed up the solution of this MIQP?
Thank you very much,Tobia
0 -
-
-
Hi Tobia,
In most cases, the quadratic objective terms in an MIQP are linearized to convert it to an MILP. This can weaken the bound obtained from the continuous relaxation. This is probably what you observe in your run.
You can control what is done with the quadratic terms with the parameters PreQLinearize and PreMIQCPForm (if Q-constraints are present).
Mario
1 -
-
Hi Mario,
Thank you for the quick response. Setting PreMIQCPForm to 1 or 2 solves the issue.
Tobia
0 -
Please sign in to leave a comment.
Comments
4 comments