Multicommodity flow in polynomial size

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.

-

1 Answer

There seems to be some small confusion here. Your primal is the path-flow formulation of the multicommodity flow problem, which orders separate path-flow to every path in some given path set $P$ (which in turn can be of exponential size), while your dual is in fact the dual linear program corresponding to the arc-flow formulation (and hence has polynomial number of variables). Wikipedia has the arc-flow primal you want here and here is a nice intro.

-
Thanks for pointing this out! Is there any textbook in the field you would recommend? – com Dec 16 '11 at 8:17
My all time favorite is Bazaraa, Jarvis, Sherali: Linear Programming and Network Flows, an extremely readable textbook on network flow theory (although a bit laconic on multicommodity flows). – Gabor Retvari Dec 19 '11 at 0:00