The Branch-and-Bound Tree

Introduces the branch-and-bound search tree for solving integer programs: nodes as LP subproblems, the three pruning rules (infeasibility, integrality, bound), tracking the incumbent and global bound, and walking through complete maximization and minimization trees.

Step 1 of 157%

Tutorial

The Branch-and-Bound Tree

Branch-and-bound (B&B) solves an integer program (IP) by exploring a tree of LP relaxations. Each node of the tree corresponds to a subproblem: the original IP together with the bound constraints inherited from every branching decision on the path from the root.

The root node is the LP relaxation of the original IP (no extra constraints).
Each non-root node is created by branching on a fractional variable in its parent.
A node whose LP relaxation has fractional value $x_j^* = f$ $x_{j}^{*} = f$ spawns two children:
- the down child adds $x_j \le \lfloor f \rfloor,$
- the up child adds $x_j \ge \lceil f \rceil.$

Each node is labeled with its LP optimal value (the node bound) and its LP solution. The set of nodes still waiting to be processed is the active list.

For instance, if the root LP of a maximization IP yields $z_0 = 14.7$ with $x_1 = 2.3$ fractional, branching on $x_1$ produces two children:

N_1: x_1 \le 2, \qquad N_2: x_1 \ge 3.

The root is then closed; $N_1$ and $N_2$ replace it on the active list.