Dantzig-Wolfe Decomposition: Reformulating with Extreme Points

Consider an LP in block-angular form:

$$\min \mathbf{c}^T \mathbf{x} \quad \text{s.t.} \quad A\mathbf{x} = \mathbf{b}, \quad \mathbf{x} \in X,$$

where the $m$ rows of $A\mathbf{x} = \mathbf{b}$ are the coupling constraints and $X = \{\mathbf{x} \geq \mathbf{0} : D\mathbf{x} \leq \mathbf{d}\}$ is the subproblem polyhedron. Assume $X$ is bounded with extreme points $\mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_K$.

The resolution theorem states that every point $\mathbf{x} \in X$ can be written as a convex combination of the extreme points:

$$\mathbf{x} = \sum_{k=1}^K \lambda_k \mathbf{v}_k, \quad \sum_{k=1}^K \lambda_k = 1, \quad \lambda_k \geq 0.$$

This substitution replaces the original variables $\mathbf{x}$ with the convex weights $\lambda_k$.

For instance, suppose $X$ has extreme points

$$\mathbf{v}_1 = \begin{bmatrix} 0 \\ 0 \end{bmatrix}, \quad \mathbf{v}_2 = \begin{bmatrix} 4 \\ 0 \end{bmatrix}, \quad \mathbf{v}_3 = \begin{bmatrix} 0 \\ 6 \end{bmatrix}.$$

To express $\mathbf{x} = \begin{bmatrix} 2 \\ 3 \end{bmatrix}$ as a convex combination, we solve

$$\lambda_2 \begin{bmatrix} 4 \\ 0 \end{bmatrix} + \lambda_3 \begin{bmatrix} 0 \\ 6 \end{bmatrix} = \begin{bmatrix} 4\lambda_2 \\ 6\lambda_3 \end{bmatrix} = \begin{bmatrix} 2 \\ 3 \end{bmatrix},$$

giving $\lambda_2 = \tfrac{1}{2}, \lambda_3 = \tfrac{1}{2},$ and convexity forces $\lambda_1 = 1 - \tfrac{1}{2} - \tfrac{1}{2} = 0.$