[Lemon-user] adding new arcs to a graph

[Kovács Péter]

Hi Leandro,

Unfortunatelly, the min cost flow algorithms in LEMON do not support 
efficient reoptimization for (slightly) modified input data. In your 
example, the first run() process does not make the second one faster.

A possible approach would be to use the optimal solution of the original 
problem as a starting solution of the second execution of the algorithm, 
but it is not supported yet. The corresponding issue can be found here:
https://lemon.cs.elte.hu/trac/lemon/ticket/221

In case of the CycleCanceling algorithm, however, it would be much 
easier to implement this. (An alternative init() function, in which we 
simply use the given feasible solution instead of executing the 
Circulation algorithm to compute one, would suffice.) Although this 
algorithm is typically slow in solving min cost flow problems from 
sratch, it could be efficient in such use cases.

There are many other ways to deal with this problem, of course, but I 
think this is the easiest to try.

Anyway, it is quite strange and misleading that 'graph' denotes the 
algorithm object in your example.

Best regards,
Peter



On 2012.10.16. 21:12, Leandro Callegari Coelho wrote:
> Hello list,
>
> Suppose I have an initial graph, which I can compute whatever I want,
> e.g., min cost flow using the network simplex algorithm:
>
>
>           NetworkSimplex<ListDigraph, int, int> graph(g);
>         int status = graph
>        .lowerMap(lowerMap)
>        .upperMap(upperMap)
>        .costMap(costMap)
>        .supplyMap(supplyMap)
>        .run();
>
> Then suppose that after creating the basic structures I want to add a
> couple of arcs to this graph. I don't know them beforehand, and then I
> want to reoptimize it. Currently I do:
>
>    //add more arcs here
>    //define the lowerMap, upperMap, costMap for the new arcs here
>    graph.reset();
>
>     and then again
>
>
>         int status = graph
>        .lowerMap(lowerMap)
>        .upperMap(upperMap)
>        .costMap(costMap)
>        .supplyMap(supplyMap)
>        .run();
>
> I tend to believe this is rather slow, because apparently I am
> redefining the whole structure again. However, I know that only a few
> arcs (whose labels I know) have been added. Is there a more efficient
> way of reoptimizing it?
>
> Thanks in advance
> Leandro
>
>
> --
>
> LCC
>
> "Absence of evidence is not evidence of absence"
> Carl Sagan (1934 - 96)
>
>
>
> _______________________________________________
> Lemon-user mailing list
> Lemon-user at lemon.cs.elte.hu
> http://lemon.cs.elte.hu/mailman/listinfo/lemon-user
>