How to solve the minimum-cost flow problem on a complete graph, with a concave cost function of flow for each edge?
-
06-11-2019 - |
Question
Here is the problem:
Input:
A series of source/sink nodes at fixed positions with given outwards/inwards flow
Edges are NOT specified. The edges can connect any nodes.
The total source and sink flow match
A concave cost function that gives a cost per edge in terms of flow capacity
Expected output:
- The minimum costing graph (not necessarily fully connected) that connects all sources to sinks and permits the required flow, without creating extra nodes.
Therefore the network topology is unspecified and should be optimized.
Many thanks.
No correct solution
Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange