Branch-and-Bound Pruning¶

Proposition¶

For a maximization integer program with incumbent value $L$, a branch-and-bound node can be pruned if its LP relaxation is infeasible, its relaxed optimizer satisfies all integer restrictions, or its relaxed upper bound $U$ satisfies $U\le L$$L$. In the integral case, update the incumbent if appropriate. For minimization, reverse the bound comparison.

Interpretation¶

Pruning is how branch-and-bound avoids searching the whole tree: a node is closed as soon as it is certain that its subproblem cannot contain a better integer solution than the incumbent.

The figure shows the outcomes of solving a node's LP relaxation in a maximization problem. If the relaxation is infeasible, the subproblem has no feasible points. If its optimum is integer, it is the best point of the subproblem and replaces the incumbent value $L$ when it is better. If its bound $U$ (written $z_R$ in the figure) satisfies $U\le L$$L$, no point of the subproblem beats the incumbent. Only a fractional optimum with $U>L$ leads to further branching.

All three rules rest on the optimization bounds. The integer points of a subproblem are feasible for its relaxation, so in a maximization none of them has a value above $U$, and branching only adds constraints, so every node further down has a bound of at most $U$ too. For minimization the roles reverse: a node is pruned when its relaxed lower bound is at least the incumbent value.

Two slips are common. A fractional relaxed optimum is never a reason to prune; it only shows where to branch. And pruning by bound needs a genuine incumbent: comparing with a rounded point that violates a constraint can discard the subproblem containing the true optimum.

Key Results¶

• For maximization, a valid global upper bound is the maximum of the incumbent value and the LP bounds of active unresolved nodes.
• At completion the incumbent proves the optimal value.
• Pruning equality with the incumbent is sufficient to find the optimum value, but can discard other equally optimal solutions.

Examples¶

For minimization, prune a node when its relaxed lower bound $z_R$, the optimal value of its LP relaxation, is at least the incumbent value.

• A node with upper bound 3.3 can be discarded once the incumbent is 3.4.
• In week 3 practice 9, the branch $x_3\ge7$ is infeasible because $x_2+3x_3\le20$ and $x_2\ge0$$0$.

Prerequisites¶

• Branch-and-Bound
• Incumbent Solution

Related Concepts¶

• Optimization Bounds

Sources¶

• OR Modelling · Week 3

Keywords: fathoming

Last updated: 20 October 2026 03:02