The Bound Proves It - Integer Programming & Branch-and-Bound

The incumbent is only proven optimal after every leaf closes. This lesson turns the full tree into a bound certificate. It also states the important caveat: branch-and-bound can be large even when each displayed value is exact.

highlighted = computed this step

Close the gap

The root LP bound is 10 and the proven incumbent is 9. Why: the search closes the possible improvement gap.

\text{gap}=1

Every leaf closed

The proof flag is 1 because every leaf is fathomed. Why: there is no open branch left that can contain a better integer point.

\text{all leaves fathomed}

Scope of the proof

This proof is for this IP tree; branch-and-bound can grow exponentially in general. Why: exact proof does not mean every instance is small.

\text{this tree proves this IP}

Diagram note

The matrix entries and tree statuses are recomputed from the same branch-and-bound run. Pixel positions are rounded for layout; every number shown is exact.

\text{closed leaves make the incumbent exact}