Node-Arc Formulation of Multi-Commodity Flow

The node-arc formulation models a multi-commodity flow problem as a linear program with one decision variable for each (arc, commodity) pair.

Let $G=(N,A)$ be a directed graph carrying $K$ commodities. For each arc $(i,j)\in A$ and each commodity $k\in\{1,\ldots,K\}$, define

$$x_{ij}^k = \text{units of commodity } k \text{ shipped on arc } (i,j).$$

Each $x_{ij}^k$ has an associated per-unit cost $c_{ij}^k$, and the objective is to minimize total shipping cost across all commodities and arcs:

$$\min \;\; \sum_{k=1}^{K}\sum_{(i,j)\in A} c_{ij}^k\, x_{ij}^k.$$

For example, with $K=2$ commodities on arcs $(1,2)$ and $(2,3)$, suppose

$$c_{12}^1=3,\ c_{12}^2=5,\ c_{23}^1=2,\ c_{23}^2=4,$$

and the flows are $x_{12}^1=4,\ x_{12}^2=2,\ x_{23}^1=4,\ x_{23}^2=2.$ Then the objective evaluates to

$$3(4)+5(2)+2(4)+4(2) = 12+10+8+8 = 38.$$