The Branch-and-Bound Tree - Integer Programming & Branch-and-Bound

A branch-and-bound proof is a finite tree of LP relaxations. The leaves explain why no unexplored branch can beat the incumbent. This lesson reads the complete IP-B tree as an exact certificate.

highlighted = computed this step

Complete tree

The full tree closes with integer optimum (3, 0) and z=9. Why: every branch either becomes a candidate or gets closed.

z_{IP}=9

Deterministic order

The search explores the floor branch before the ceiling branch. Why: a fixed rule makes the proof tree reproducible.

\text{floor branch before ceiling branch}

Diagram note

The colored leaves are recomputed statuses from exact LP relaxations. Pixel positions are rounded for layout; every number shown is exact.

\text{the tree is the certificate}