Column Generation: The Master/Subproblem Pattern

In the path-based formulation of multi-commodity flow, every $s_k$–$t_k$ path is a candidate variable $x_p.$ For realistic networks the number of paths is astronomical — far too many to enumerate.

Column generation sidesteps this by maintaining only a small subset of paths at a time and adding new ones on demand. The procedure alternates between two LPs.

Restricted Master Problem (RMP). The original LP restricted to the current working set of path variables. Solving the RMP returns a primal flow and a set of optimal dual prices:

• $\alpha_k \ge 0$ on each commodity $k$'s demand constraint — the marginal value of one more unit of demand for commodity $k;$
• $\beta_e \ge 0$ on each edge $e$'s capacity constraint — the shadow price of capacity on edge $e.$

Pricing subproblem. Search outside the working set for a path with negative reduced cost. For a path $p \in \mathcal{P}_k,$

$$\bar c_p \;=\; \sum_{e \in p}(c_e + \beta_e) \;-\; \alpha_k.$$

If $\bar c_p < 0,$ adding $p$ to the RMP can improve the objective, so $p$ enters as a new column. If no path anywhere has $\bar c_p < 0,$ the current RMP solution is already optimal for the full LP.

This is the master/subproblem pattern: the master sends prices $(\alpha_k, \beta_e)$ down to the subproblem; the subproblem returns a column.