I've recently come across the problem that seems to be quite interesting but i don't know how to tackle it. I suppose that it might be a special case of maximum flow problem but it seems to be rather different so i need an advice.
Suppose that we have a weighted directed graph with two (possibly the same) vertices designated as "source" (S) and "target" (T). We can imagine that vertices represent the currencies and edges are conversion options. There is some initial amount of money in vertex S and it has to be converted to vertex T in such way that the resulting sum is maximum possible.
Conversion can be done in parts so if there is some sum S at vertex V and there are several edges coming from V then we can send different amounts of money along these edges (i.e. we are not obliged to use only one edge or to divide the sum in equal parts or to use multiples of some fixed lot etc.). We are also not obliged to convert total sum. It can be the case that the best option is to convert some part of it.
Now comes the trickiest part. Each edge's weight depends on amount of money that must be transported through an edge. For each edge E there is some function F(E) that receives amount of money entering the edge and returns amount of money leaving the edge. We can assume that ratio of output/input gets smaller when input gets bigger.
Thank you very much for any ideas. Any help will be highly appreciated.