[Lemon-user] Reverse min cost flow

[Kovács Péter]

Hi All,

Although there might be better solutions (more efficient or more 
general, like the ILP approach), I think the simplest one is to 
iteratively run a min-cost flow algorithm (e.g. NetworkSimplex), but 
_not_ for every tick of flow. It is much better to apply binary search 
to find the desired amount of flow. It requires log(K) executions of the 
min-cost flow algorithm, where K is the absolute maximum flow value. In 
practice, it won't be more than 20-30.

Best regards,
Peter



> Maybe the best way to solve it is by (Integer) Linear Programming where
> you should use the "max flow model" (maximize flow as objective
> function) and a cost-based constraint: sum of edge_flow * edge_cost <=
> given cost.
>
> The advantage you get is that it's fairly easy to introduce new
> constraints possibly needed in the future. On the other hand, LP solvers
> aren't so fast as the algorithms implemented in LEMON.
>
> 2016-04-07 9:22 GMT-03:00 Arthurus Castus <arthurus314 at hotmail.com
> <mailto:arthurus314 at hotmail.com>>:
>
>     Hi everybody,
>
>     I'm looking for a smart way to find the max possible flow for a
>     given cost. For now, I do it by running multiple times the
>     NetworkSimplex for every tick of flow until the total cost reaches
>     the wanted value (I could also do it by dichotomy).
>
>     Do you know if there are a better way to resolve it ? If not, do you
>     have an idea about how could I re-use structures from the run N-1 to
>     use it in N ?
>
>     Many thanks
>     _______________________________________________
>     Lemon-user mailing list
>     Lemon-user at lemon.cs.elte.hu <mailto:Lemon-user at lemon.cs.elte.hu>
>     http://lemon.cs.elte.hu/mailman/listinfo/lemon-user
>
>
>
>
> --
> /Rafael Kendy Arakaki/
> Mestrando em Ciência da Computação
> Universidade Estadual de Campinas - Instituto de Computação
>
>
> _______________________________________________
> Lemon-user mailing list
> Lemon-user at lemon.cs.elte.hu
> http://lemon.cs.elte.hu/mailman/listinfo/lemon-user
>