Pruning by Infeasibility

In branch and bound, prune a node whenever its subproblem has no feasible solution. The justification: branching only adds constraints, so an infeasible parent cannot have a feasible descendant. Combined with pruning by bound and by integrality, this completes the standard pruning toolkit.

Step 1 of 157%

Tutorial

Pruning by Infeasibility

In branch and bound, we explore subproblems by adding constraints to narrow the search. After solving the LP relaxation at a node, we may discover that the constraint set has no solutions at all -- the LP relaxation is infeasible.

When this happens, we prune by infeasibility: discard the node and do not branch from it.

The justification is direct. Branching only ever adds constraints. So every descendant of an infeasible node would inherit the same conflicting constraints (plus more). If the parent has no feasible point, none of its descendants can have one either.

For example, suppose a node inherits the branching constraints

x_1 \leq 2 \quad \text{and} \quad x_1 \geq 3.

No value of $x_1$ satisfies both, so the constraint set is empty. We prune this node by infeasibility, mark it with $\times$ , and remove it from the list of active nodes.