Why Multi-Commodity Flow Breaks Total Unimodularity

The constraint matrix of multi-commodity flow stacks block-diagonal incidence matrices with bundling-row blocks. Each block is totally unimodular, but the combined matrix is not: it contains 3x3 submatrices with determinant of absolute value 2. As a consequence, the LP relaxation can have fractional vertices, and integer multi-commodity flow is hard.

Step 1 of 157%

Tutorial

The Multi-Commodity Flow Constraint Matrix

In single-commodity flow, the constraint matrix equals the node-arc incidence matrix $A$ , which is totally unimodular (TU). Every LP-relaxation vertex is therefore integer whenever the right-hand side is integer.

In $K$ -commodity flow, each commodity $k$ has its own flow vector $\mathbf{x}^k$ , and arcs share capacity through bundling constraints $\sum_{k=1}^{K} x^k_a \le u_a$ on each arc $a$ . Stacking conservation (one block per commodity) and bundling (one block across all commodities) gives the block form

M = \begin{bmatrix} A & 0 & \cdots & 0 \\ 0 & A & \cdots & 0 \\ \vdots & & \ddots & \vdots \\ 0 & 0 & \cdots & A \\ I & I & \cdots & I \end{bmatrix}.

The top $K$ rows of blocks form the conservation block -- a block-diagonal stack of incidence matrices. The bottom strip is the bundling block -- $K$ copies of the identity placed side-by-side.

Each individual block ( $A$ or $I$ ) is TU. But TU is not preserved under stacking: $M$ contains square submatrices whose determinants escape $\{-1, 0, 1\}$ . The next tutorial exhibits the smallest such obstruction.