Branch-and-Price: Column Generation Inside Branch and Bound

In branch-and-price, every node of a branch-and-bound tree has its LP relaxation solved by column generation on a Dantzig–Wolfe master. After CG converges at a node, the master LP solution $\boldsymbol{\lambda}^*$ defines an implied solution in the original variables:

$$\mathbf{x}^* = \sum\limits_j \lambda^*_j \mathbf{x}^j,$$

where $\mathbf{x}^j$ is the integer pattern (extreme point of the subproblem polytope) attached to master variable $\lambda_j$. If $\mathbf{x}^*$ is integer, the node is solved. Otherwise we must branch to drive the relaxation toward integrality.

For example, suppose CG terminates at a node with $\lambda_1^* = 0.4,$ $\lambda_2^* = 0.6$ (others zero) and patterns

$$\mathbf{x}^1 = \begin{bmatrix} 1 \\ 0 \\ 1 \end{bmatrix}, \qquad \mathbf{x}^2 = \begin{bmatrix} 0 \\ 1 \\ 1 \end{bmatrix}.$$

The implied original solution is

$$\mathbf{x}^* = 0.4 \begin{bmatrix} 1 \\ 0 \\ 1 \end{bmatrix} + 0.6 \begin{bmatrix} 0 \\ 1 \\ 1 \end{bmatrix} = \begin{bmatrix} 0.4 \\ 0.6 \\ 1 \end{bmatrix},$$

which is fractional in $x_1$ and $x_2$. The node is not yet integer-feasible, so branching is required.