Why Decompose: Block Structure in Large Problems

Large-scale linear programs often hide block structure in their constraint matrices. Recognizing block-diagonal, block-angular, and dual block-angular forms reveals when an LP separates into smaller, independent (or near-independent) subproblems — the foundation of Dantzig–Wolfe, Benders, and other decomposition algorithms. This lesson shows how to identify these structures and quantify the computational payoff of exploiting them.

Step 1 of 157%

Tutorial

Block-Diagonal Structure: When an LP Separates Completely

When a linear program has hundreds of thousands of variables and constraints, solving it as one giant problem is wasteful — and often infeasible. Many large-scale LPs have block structure: their constraint matrix can be permuted so that every nonzero entry lies inside a few well-defined blocks, with zeros everywhere else.

The simplest case is block-diagonal structure, where the constraint matrix has the form

A = \begin{bmatrix} A_1 & & & \\ & A_2 & & \\ & & \ddots & \\ & & & A_K \end{bmatrix}.

Each block $A_k$ acts on its own variables $x_k$ and its own constraints. The full LP

\min \; \sum\limits_{k=1}^{K} c_k^{\!\top} x_k \quad \text{s.t.} \quad A_k x_k \le b_k,\; x_k \ge 0

decouples into $K$ independent LPs — one per block. We solve each separately (and in parallel); the global optimum is the sum of the subproblem optima, because no variable or constraint links the blocks.

For example, the constraint matrix

\begin{bmatrix} 2 & 1 & 0 & 0 & 0 \\ 3 & 4 & 0 & 0 & 0 \\ 0 & 0 & 5 & 1 & 2 \\ 0 & 0 & 0 & 6 & 3 \end{bmatrix}

splits into one subproblem on $(x_1, x_2)$ and a second on $(x_3, x_4, x_5)$ — two LPs that share nothing.