Nodes in MIP logging
Answered
Hi,
I have a question regarding the explored nodes after reading the MIP Logging. I will start with my understanding of Branch and Bound:
Initialize an empty list of relaxed problems L=[]. Put root relaxation inside L.
Loop:
Pick out a relaxed problem A inside L, solve it, get relaxed binary solution z
(z[i] \in [0, 1]), and objective o (lower bound for A).
(1) If o is worse than the current best feasible solution, stop exploring A.
Else (2) If z is binary feasible, record o as the current best solution.
Else (3) Pick one non-binary element in z (say z[0]). Branch A into A1(z[0]=0)
and A2(z[0]=1). Put A1 and A2 into L.
Update their lower bounds (e.g. using duality).
Until the current best solution approaches the lowest lower bound.
MIP Logging shows explored and unexplored nodes. Is the number of explored nodes the same as the number of solved relaxed problems like A? Is the number of unexplored nodes the same as problems in L but not yet solved?
The logging also shows the average simplex iterations performed per node. My understanding is since Gurobi uses branch and cut, it solves simplexes when solving A to find cutting planes?
Thank you!
-
Hi Xuan,
Is the number of explored nodes the same as the number of solved relaxed problems like A?
Correct.
Is the number of unexplored nodes the same as problems in L but not yet solved?
Correct.
The logging also shows the average simplex iterations performed per node. My understanding is since Gurobi uses branch and cut, it solves simplexes when solving A to find cutting planes?
The column \(\texttt{It/Node}\) shows the average number of Simplex iterations performed per node, i.e., the average number of Simplex iteration to solve a problem A to optimality.
Best regards,
Jaromił0 -
Hi Jaromił,
Thanks for the answer!
The column It/Node shows the average number of Simplex iterations performed per node, i.e., the average number of Simplex iteration to solve a problem A to optimality.
What if A is a QP? Does this column shows the interior point iterations?
Best regards,
Xuan Lin
0 -
Hi Xuan Lin,
If the QP Simplex is used, then QP Simplex iterations are listed. Please note that by default, Gurobi will always try to use the Simplex algorithm for node relaxations. For a QP with a convex objective, Gurobi would use the QP Simplex. For a nonconvex model, a linear relaxation would be constructed, which is would then be solved via the Simplex algorithm.
However, if you explicitly set the parameter NodeMethod=2 to tell Gurobi to use the Barrier algorithm at every node, then this column shows the number of interior point iterations.
Best regards,
Jaromił0 -
Hi Jaromił,
Thanks for the answer! I actually didn't know that QPs can be solved with simplex.
May I ask a minor question: does the column "unexplored nodes" always goes to 0 as the algorithm terminates?
Thank you!
0 -
Hi Xuan Lin,
May I ask a minor question: does the column "unexplored nodes" always goes to 0 as the algorithm terminates?
Yes, the column "unexplored nodes" goes to 0 when the algorithm terminates. However, please note that depending on the output frequency it is possible that you will not see the part of the log where the number of unexplored nodes declines. It is possible that at some point during the optimization process, Gurobi finds some cuts, incumbent, propagation information that allows it to prune (almost) all unexplored nodes. This often looks like and could be described as a "sudden convergence" of the algorithm.
Best regards,
Jaromił0
Please sign in to leave a comment.
Comments
5 comments