The multi-commodity flow problem is a network flow problem with multiple commodities (flow demands) between different source and sink nodes.

Given a flow network ${\displaystyle \,G(V,E)}$, where edge ${\displaystyle (u,v)\in E}$ has capacity ${\displaystyle \,c(u,v)}$. There are ${\displaystyle \,k}$ commodities ${\displaystyle K_{1},K_{2},\dots ,K_{k}}$, defined by ${\displaystyle \,K_{i}=(s_{i},t_{i},d_{i})}$, where ${\displaystyle \,s_{i}}$ and ${\displaystyle \,t_{i}}$ is the source and sink of commodity ${\displaystyle \,i}$, and ${\displaystyle \,d_{i}}$ is its demand. The variable ${\displaystyle \,f_{i}(u,v)}$ defines the fraction of flow ${\displaystyle \,i}$ along edge ${\displaystyle \,(u,v)}$, where ${\displaystyle \,f_{i}(u,v)\in [0,1]}$ in case the flow can be split among multiple paths, and ${\displaystyle \,f_{i}(u,v)\in \{0,1\}}$ otherwise (i.e. "single path routing"). Find an assignment of all flow variables which satisfies the following four constraints:

(1) Link capacity: The sum of all flows routed over a link does not exceed its capacity.

(2) Flow conservation on transit nodes: The amount of a flow entering an intermediate node ${\displaystyle u}$ is the same that exits the node.

(3) Flow conservation at the source: A flow must exit its source node completely.

(4) Flow conservation at the destination: A flow must enter its sink node completely.

Load balancing is the attempt to route flows such that the utilization ${\displaystyle U(u,v)}$ of all links ${\displaystyle (u,v)\in E}$ is even, where

The problem can be solved e.g. by minimizing ${\displaystyle \sum _{u,v\in V}(U(u,v))^{2}}$. A common linearization of this problem is the minimization of the maximum utilization ${\displaystyle U_{max}}$, where