Multi-Commodity Network Flow

Network structure gives a natural block-angular LP. Dantzig-Wolfe Decomposition exploits commodity-level independence to decompose into per-commodity shortest-path sub-problems.

Problem Description

A multi-commodity network flow problem routes several distinct commodities through a shared network. Each commodity has its own origin, destination, and demand, but all commodities share the same arc capacities. The objective is to satisfy all demands at minimum total cost.

Notation (all symbols defined before first use):

$G = (V, A)$: Directed graph with nodes $V$ and arcs $A$ .
$K$: Number of commodities.
$s^k, t^k$: Source and sink node for commodity $k$ .
$d^k$: Demand for commodity $k$ .
$u_{ij}$: Capacity of arc $(i,j) \in A$ (shared across all commodities).
$c_{ij}^k$: Unit cost of routing commodity $k$ on arc $(i,j)$ .
$f_{ij}^k$: Flow of commodity $k$ on arc $(i,j)$ .

Block-Angular Structure

The LP can be written as:

\begin{aligned} \min \quad & \sum_{k=1}^{K} \sum_{(i,j)\in A} c_{ij}^k f_{ij}^k \\ \text{s.t.} \quad & \sum_{k=1}^{K} f_{ij}^k \le u_{ij} \quad \forall (i,j) \in A \quad \text{(coupling: capacity constraints)} \\ & \sum_{j:(i,j)\in A} f_{ij}^k - \sum_{j:(j,i)\in A} f_{ji}^k = b_i^k \quad \forall i \in V, \, k = 1,\ldots,K \quad \text{(sub-problem: flow balance for commodity } k\text{)} \\ & f_{ij}^k \ge 0 \quad \forall (i,j) \in A, \, k \end{aligned}

where $b_i^k = d^k$ if $i = s^k$ , $b_i^k = -d^k$ if $i = t^k$ , else $0$ .

Dantzig-Wolfe Decomposition Applied

By relaxing the capacity constraints with dual multipliers $\mu_{ij} \ge 0$ , the Lagrangian breaks into $K$ independent single-commodity minimum-cost flow problems.

Dual variables: $\mu_{ij}$ represents the congestion price on arc $(i,j)$ . It penalises each unit of flow on a congested arc, effectively redistributing commodities away from bottlenecks.

Master problem: The RMP aggregates convex combinations of extreme flows for each commodity:

\begin{aligned} \min \quad & \sum_{k=1}^K \sum_{p \in P^k} c^{kp} \lambda^{kp} \\ \text{s.t.} \quad & \sum_{k=1}^K \sum_{p \in P^k} a_{ij}^{kp} \lambda^{kp} \le u_{ij} \quad \forall (i,j) \in A \quad \text{(coupling)} \\ & \sum_{p \in P^k} \lambda^{kp} = 1 \quad \forall k \quad \text{(convexity)} \\ & \lambda^{kp} \ge 0 \end{aligned}

where $P^k$ is the set of paths from $s^k$ to $t^k$ , $a_{ij}^{kp} = 1$ if path $p$ uses arc $(i,j)$ , else $0$ .

Pricing sub-problem for commodity $k$ : Find the minimum reduced-cost path from $s^k$ to $t^k$ under the modified arc costs:

\hat{c}_{ij}^k = c_{ij}^k + \mu_{ij}^*

This is a shortest path problem — solvable in polynomial time for each commodity independently.

Citation

Ford, L. R., & Fulkerson, D. R. (1958). A suggested computation for maximal multi-commodity network flows . Management Science, 5(1), 97–101. doi:10.1287/mnsc.5.1.97