Fractional but not integer multi-commodity minimum cost flow

You can use the example for an undirected edge with unit capacities, but replace each undirected edge from A to B with a set of directed edges that look like this.

Each edge has a unit capacity. And if you have $x$ units of flow from A to B and $y$ units of flow from B to A, you can route it as long as $x+y \leq 1$.

This is the gadget referred to in Andreas Bjrklund's comment.

Solved by user1677 (23,499 )
Dec 31, 2015 at 14:14