Column Generation Termination and Optimality

After solving a restricted master problem (RMP) for a multi-commodity flow, we obtain dual values $\pi_a \geq 0$ for each arc capacity and $\sigma_k$ for each commodity $k$'s demand constraint. The pricing subproblem for commodity $k$ is a shortest path problem on the network with reduced arc costs $c_a - \pi_a$. Let $z_k^*$ denote its optimal value.

The reduced cost of the best new column (path) for commodity $k$ is

$$\bar c_k^* \;=\; z_k^* - \sigma_k.$$

Termination criterion. Column generation terminates when no commodity has an improving column:

$$\bar c_k^* \;=\; z_k^* - \sigma_k \;\geq\; 0 \quad \text{for every commodity } k.$$

At termination, the current RMP solution is optimal for the full master LP, because no additional path can decrease the minimization objective.

If some $\bar c_k^* < 0$, the corresponding shortest path is an improving column and is added to the RMP.