2
votes
Accepted
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 ...
- 24.3k
1
vote
Anyone recognize this as a special type of multi-commodity flow problem?
I think you can solve this as a single shortest path problem with respect to arc weights
$$\overline{w}_{ij}=\min\{-w_{ijp}\ :\ p\in\{1,\ldots,m\}\}.$$
For every arc $(i,j)$ fix some $p(i,j)\in\{1,\...
- 1,026
Only top scored, non community-wiki answers of a minimum length are eligible