Pruning by Bound

Use the relationship between a node's relaxation bound and the current incumbent value to decide which open nodes in a branch-and-bound tree can be discarded without further branching. Covers both the maximization rule ( $\bar z \le z^*$ ) and the minimization rule ( $\underline z \ge z^*$ ), sweeping over an open list, and re-pruning after incumbent updates.

Step 1 of 157%

Tutorial

Pruning by Bound (Maximization)

In a branch-and-bound tree, each open node is a subproblem whose relaxation (typically the LP relaxation) yields a bound on the objective values reachable in that subtree. The incumbent is the best feasible integer solution found so far; we denote its objective by $z^*$ .

For a maximization integer program, the relaxation produces an upper bound $\bar z$ on every integer-feasible point inside the node's subtree. If

\bar z \le z^*,

then no descendant of this node can strictly improve on the incumbent. We prune the node by bound and discard the entire subtree without further branching.

For instance, suppose the incumbent is $z^* = 30$ and a node has $\bar z = 28.7$ . Since $28.7 \le 30$ , every integer point in this subtree has objective at most $28.7$ , which is worse than $30$ . Prune.