A branch-and-bound node can close for three different reasons. It can be integer, infeasible, or unable to beat the incumbent bound. This lesson shows all three cases in one small tree.
highlighted = computed this step
Integer candidate
The y-low child gives (3, 0) with z=9. Why: an integer LP optimum becomes a candidate incumbent.
z=9
Bound fathom
The x-low leaf has LP bound 9, equal to the incumbent value. Why: a node that cannot beat the incumbent is closed.
bound≤zinc
Infeasible fathom
The x-high leaf has no feasible LP relaxation. Why: an empty relaxation cannot contain an integer feasible point.
LP infeasible
Diagram note
The three leaf statuses are recomputed by solving the LP relaxation at each node. Pixel positions are rounded for layout; every number shown is exact.
integer, infeasible, and bound fathoms close nodes