The original linear program for multicommodity flow has exponentially many variables. How to find equivalent linear program that has polynomial size?
Linear program of multicommodity flow
$maximize \space \sum_{p\epsilon P}^{ } {f_{p}}$
$subject \space to \space$
$\sum_{p:e\epsilon P}^{ } {f_{p}} \leq c_{e}, e \epsilon E$
$f_{p} \geq 0, p \epsilon P$
This formulation has exponentially many variables.
The dual LP problem to multicommodity flow is sparsest flow, which is can be formulated in polynomial size by using metrics
$minimize \space \sum_{e\epsilon E}^{ } {c_{e}d_{e}}$
$subject \space to$
$\sum_{u,v \epsilon V}^{ } {d_{v,u}} \geq 1$
$d_{v,w} \leq d_{v,r}+d_{r,w} \space \forall v,u,r \epsilon V$
$d_{v,r} \leq d_{v,w}+d_{w,r} \space \forall v,u,r \epsilon V$
$d_{w,r} \leq d_{w,v}+d_{v,r} \space \forall v,u,r \epsilon V$
$d_{v,w} \geq 0 \space \forall v,u \epsilon V$
where,
$c_{e}$ - capacity of the edge $e$
$d_{e} = 1$ iff $e$ is in $s-t$ cut
I suspect we can use metric to formulate multicommodity problem in polynomial size too. But right now it's not obvious to me.