<p>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.</p>

<p><a href="https://i.sstatic.net/WzFe4.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/WzFe4.jpg" alt="enter image description here"></a></p>

<p>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$. </p>

<p>This is the gadget referred to in Andreas Björklund's comment.</p>

CC BY-SA 3.0
2015-12-31T14:14:39.603Z
2015-12-31T14:14:39.603Z
Peter Shor 
<p>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 <a href="https://cstheory.stackexchange.com/questions/21913/can-the-optimal-minimum-cost-two-commodities-flow-be-fractional-on-this-special">here</a> a similar question but it considers an undirected graph or to be precise I don't catch Andreas Björklund's last comment.</p>

<p>Can anyone help? Thank you in advance!</p>

CC BY-SA 3.0
2016-01-02T04:55:08.753Z
Schrijver's book on Combinatorial Optimization discusses several aspects of multiflows in Vol C.
Chandra Chekuri
CC BY-SA 4.0
2023-01-06T17:44:16.467Z
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?
Tuomo Takkula
<graph-theory><examples><multicommodity-flow>
Fractional but not integer multi-commodity minimum cost flow
Rorschach
# Fractional but not integer multi-commodity minimum cost flow

(Asked by: username_0 on 2015-12-31)

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](https://cstheory.stackexchange.com/questions/21913/can-the-optimal-minimum-cost-two-commodities-flow-be-fractional-on-this-special) 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!

**Tags:** graph-theory, examples, multicommodity-flow
> **Comments:**
> **username_1**: Schrijver's book on Combinatorial Optimization discusses several aspects of multiflows in Vol C.  
> **username_2**: 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?  

---

## 1 answers

### Answer by username_3 on 2015-12-31. Score: 2 | Accepted 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.

[![enter image description here](https://i.sstatic.net/WzFe4.jpg)](https://i.sstatic.net/WzFe4.jpg)

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.


---

