Branch-and-Bound¶

Definition¶

Branch-and-bound solves an integer program by solving LP relaxations of subproblems, splitting subproblems when restricted variables are fractional, and discarding subproblems whose bounds cannot improve the best feasible integer solution. If $x_j=v$ is fractional, branch into

x_j\le\lfloor v\rfloor\qquad\text{and}\qquad x_j\ge\lceil v\rceil.

For a binary variable these branches fix it to 0 and 1.

Interpretation¶

Branch-and-bound finds the best integer solution by divide and conquer. It splits the problem into subproblems whose integer solutions together are exactly those of the original, and uses LP relaxations, ordinary linear programs, to decide which subproblems are still worth exploring.

A search tree: the root LP relaxation with bound 13 splits on x2 into two branches; the left branch splits again on x1 into an integer node with value 11 and an infeasible pruned node.

The tree belongs to the model $\max(3x_1+2x_2)$ with $2x_1+2x_2\le9.5$ and $x_1\le3.5$ from the pure integer program page. The root relaxation gives $(3.5,1.25)$ with bound $13$ . Branching on $x_2$ gives nodes with bounds $12.5$ and $12.25$ . Under $x_2\le1$ $1$ , branching on $x_1$ gives the integer point $(3,1)$ with $z=11$ $11$ , the first incumbent, and an infeasible node, since $x_1\ge4$ contradicts $x_1\le3.5$ $3.5$ . The node $x_2\ge2$ has bound $12.25>11$ $11$ , so it must still be explored; it contains no integer point better than $11$ , so $(3,1)$ is optimal.

The branches $x_j\le\lfloor v\rfloor$ and $x_j\ge\lceil v\rceil$ $⌈ v ⌉$ , built with the floor and ceiling functions, together keep every point with integer $x_j$ and remove only the strip $\lfloor v\rfloor<x_j<\lceil v\rceil$ $⌈ v ⌉$ , which contains the fractional optimum. So no integer solution is lost, and that fractional point cannot reappear. Each relaxation bounds every integer solution below its node, and the pruning rules close nodes that cannot help.

An integer solution found early is a candidate, not yet the answer: the search ends only when every open node is pruned. The order of exploring nodes changes the amount of work, not the optimum finally proved.

Key Results¶

Carry all ancestor branching constraints into each child.
Prune for infeasibility, an integral relaxed optimum, or an uncompetitive bound.
Continue until every remaining possibility is resolved or bounded by the incumbent.
Branching choices affect the work required but not the correctly proven optimum.

Examples¶

The figure branches on $x_2=1.25$ $1.25$ , giving $x_2\le\lfloor1.25\rfloor=1$ or $x_2\ge\lceil1.25\rceil=2$ $2$ .

A fractional value $x_1=3.3$ yields branches $x_1\le3$ and $x_1\ge4$ $4$ .
The development-project model has optimum 3.4; recompute the LP relaxation at each node rather than copying intermediate values.

Prerequisites¶

Sources¶

OR Modelling · Week 3

Aliases: B&B, branch and bound

Last updated: 20 October 2026 03:02