[Lemon-user] Network Simplex Initialisation (based on Bonneel's network_simplex_simple.h)

[Kovács Péter]

Hi Matthew,

>     /I am guessing the way to find a good initial tree with an initial
>     solution that has fewer than #sources+#sinks-1 arcs is to find arcs
>     with minimal cost to make the initial solution into a spanning tree.
>     I am still figuring out if this is correct / how I would implement it.
>     /
>
>
>   I tried this and the algorithm still does degenerate pivots. And,
> indeed, I came up with a small theoretical example where the algorithm
> still finds an arc with negative reduced cost despite initialising with
> minimal cost arcs.

I'm not sure whether you can entirely eliminate degenerate pivots, but I 
don't think that would be important. The algorithm should be fast even 
if a few degenerate pivots occur. That's normal.

> So, I am still wondering if there is a way to set the zero-flow arcs
> such that, if given the optimal solution, the algorithm does no
> iterations, i.e. no other arc has negative reduced cost. Anyone got any
> ideas on this?

I think, the selection of the zero-flow arcs is arbitrary. However, you 
should also be careful when specifying the node potentials. Not only do 
you have to set an optimal flow as an initial solution, but you have to 
set corresponding node pontentials in order to ensure that the 
optimality conditions hold for each arc. That is, the reduced cost of 
each arc should be non-negative. In general, in case of an optimal flow, 
optimal node potentials can be calculated with a shortest path 
computation (e.g. Bellman-Ford algorithm).

> Also, I have coded another version of the initialisation where I use the
> standard LEMON initialisation /after/ having added the arcs with
> positive flow, thus I only add an artificial arc if needed. So the
> number of artificial arcs is equal to the number of nodes minus the
> number of positive flow arcs in my initialisation. And in this
> initialisation, I only give the positive flow arcs, no need to input a
> spanning tree.

This approach seems to be easier and safer to implement and I don't 
think that it would be significantly slower. Many studies of network 
simplex algorithm showed that initializing with artifical arcs is to be 
prefered in practice, as the algorithm is very efficient in replacing 
them, maybe more efficient than the code you would write to select the 
zero-flow arcs for the tree.

> This seems to work OK (see joint file).
>
> Matthew

Regards,
Péter