# Fractional but not integer multi-commodity minimum cost flow

I'm searching for an example digraph for the multi-commodity minimum cost flow problem with integer demand. There shouldn't be an integer but fractional optimal solution. I found here a similar question but it considers an undirected graph or to be precise I don't catch Andreas Björklund's last comment.

Can anyone help? Thank you in advance!

• Schrijver's book on Combinatorial Optimization discusses several aspects of multiflows in Vol C. Jan 2, 2016 at 4:55
• Just to add another variant to the puzzle: what would be the minimal example for a fractional optimal solution to a 2-commodity network flow problem where the underlying directed network has no cycles? Jan 6 at 17:44

## 1 Answer

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 Björklund's comment.