Column Generation for Dantzig-Wolfe Masters

After Dantzig-Wolfe reformulation of a block-structured LP, the master problem has one variable $\lambda_k$ for each extreme point $\mathbf{x}^k$ of the subproblem polyhedron $P$:

$$\min_{\lambda\geq 0}\;\sum_k (c^T\mathbf{x}^k)\,\lambda_k \quad\text{s.t.}\quad \sum_k (A_1\mathbf{x}^k)\,\lambda_k = b_1,\quad \sum_k \lambda_k = 1.$$

Because $P$ may have an enormous number of extreme points, we never enumerate them. Instead, we solve a restricted master that uses only a small subset of columns, then check whether any missing column would improve the objective. This check uses the reduced cost.

Let $\pi$ be the dual prices for the linking constraints $A_1\mathbf{x}=b_1$, and let $\mu$ be the dual price for the convexity constraint $\sum_k\lambda_k=1$. The reduced cost of the column associated with extreme point $\mathbf{x}^k$ is

$$\bar{c}_k = c^T\mathbf{x}^k - \pi^T(A_1\mathbf{x}^k) - \mu.$$

If $\bar{c}_k<0$, the column prices in -- adding $\lambda_k$ to the restricted master can decrease the objective. If $\bar{c}_k\geq 0$ for every extreme point, the current restricted master solution is optimal for the full master.

For instance, with $c=\begin{bmatrix}1\\2\end{bmatrix}$, $A_1=\begin{bmatrix}1 & 1\end{bmatrix}$, $\pi=3$, $\mu=-2$, and $\mathbf{x}^k=\begin{bmatrix}2\\1\end{bmatrix}$:

$$\begin{align*} c^T\mathbf{x}^k &= 1(2)+2(1)=4,\\ A_1\mathbf{x}^k &= 1(2)+1(1)=3,\\ \bar{c}_k &= 4 - 3(3) - (-2) = -3. \end{align*}$$

Since $\bar{c}_k=-3<0$, this column prices in.