Path-Based Formulation of Multi-Commodity Flow

Reformulate the multi-commodity flow LP using one decision variable per source-to-sink path instead of one per arc. Write the objective as a sum of per-unit path costs times path flows, impose demand constraints (one per commodity) and bundle/capacity constraints (one per arc using path-arc indicators), and evaluate the objective on a given path-flow solution.

Step 1 of 157%

Tutorial

Path-Flow Variables and Path Costs

In the path-based formulation of multi-commodity flow, the decision variables represent flow along entire paths rather than along individual arcs. For each commodity $k,$ let $P_k$ denote the set of directed paths from source $s_k$ to sink $t_k.$ For each path $p\in P_k$ we introduce

f_p^k = \text{units of commodity } k \text{ routed along path } p.

The per-unit cost of routing commodity $k$ along path $p$ is the sum of per-unit arc costs along that path:

c_p^k = \sum\limits_{(i,j)\,\in\, p} c_{ij}^k.

For example, suppose a commodity is routed along $p:\ s\to a\to b\to t$ with per-unit arc costs $c_{sa}=2,\ c_{ab}=4,\ c_{bt}=3.$ Then

c_p = 2 + 4 + 3 = 9.