0
$\begingroup$

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 Answers 1

1

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.

  • 0
    My all time favorite is [Bazaraa, Jarvis, Sherali: Linear Programming and Network Flows](http://www.amazon.com/Linear-Programming-Network-Mokhtar-Bazaraa/dp/0471636819), an extremely readable textbook on network flow theory (although a bit laconic on multicommodity flows).2011-12-19