Pruning by Integrality

In branch-and-bound for an integer program, every node solves an LP relaxation. Sometimes the LP optimum turns out to be integer-valued in every variable — in which case it is automatically feasible for the original integer program.

A node is pruned by integrality when its optimal LP solution is integer-valued in every component required to be integer. No further branching is needed at this node.

For example, suppose a node's LP relaxation gives the optimal solution

$$\mathbf{x}^{LP} = \begin{bmatrix} 2 \\ 3 \\ 0 \end{bmatrix}, \qquad z^{LP} = 17.$$

Every component is an integer, so $\mathbf{x}^{LP}$ is a feasible IP solution. The node is pruned by integrality.

By contrast, the LP solution $(2,\, 1.5,\, 4)^T$ has a fractional component, so the corresponding node cannot be pruned by integrality and we must branch.