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

[matthew henry]

>
>
> *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.

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?

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 seems to work OK (see joint file).

Matthew
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lemon.cs.elte.hu/pipermail/lemon-user/attachments/20150612/61c70b82/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: network_simplex_simple_modified_initpos.h
Type: text/x-chdr
Size: 50816 bytes
Desc: not available
URL: <http://lemon.cs.elte.hu/pipermail/lemon-user/attachments/20150612/61c70b82/attachment-0001.h>