[Lemon-user] number of STATE_TREE vars at end of network simplex

[Matthew Galati]

In this case, it probably is NOT connected. I will check and get back to
you. This comes from a multicommodity flow problem - so the extracted
network should be disconnected.



On Wed, Mar 3, 2010 at 3:40 PM, Alpár Jüttner <alpar at cs.elte.hu> wrote:

> Hi,
>
> Just a short question: is your graph connected?
>
> Btw, I had a short look at lemon/network_simplex.h and I was surprised
> to see that _state is declared as BoolVector, but it can get three
> different values (STATE_TREE, STATE_LOWER, STATE_UPPER). Luckily,
> BoolVector is currently defined an std::vector<char>, but to me it looks
> quite dirty.
>
> Regards,
> Alpar
>
>
> On Wed, 2010-03-03 at 10:22 -0500, Matthew Galati wrote:
> > Hi. I am trying to form a basis to hand a standard LP simplex solver
> > (dual simplex) after running LEMON's network simplex. From my
> > understanding, network simplex forms the basis as a spanning tree,
> > which will have m-1 entries (where m = the number of rows = the number
> > of nodes in network). And the last element of the basis would normally
> > come from a basic "artificial variable" - which seems it can be found
> > by looking for the row with _pi[i] = 0.
> >
> > I am running against a Dimacs format file. Net simplex solves the
> > problem fine, but at the end, I print out the number of arcs with
> > STATE_TREE (basic) and it is not what I had expected. There are 256
> > nodes in the network, but only 252 links that are set to basic.
> >
> > Am I interpreting the basis incorrectly? Or might there be a bug?
> >
> > Let me know if you want the dimacs file to repeat the issue I am
> > seeing.
> >
> > Thanks,
> > Matt
> > _______________________________________________
> > Lemon-user mailing list
> > Lemon-user at lemon.cs.elte.hu
> > http://lemon.cs.elte.hu/mailman/listinfo/lemon-user
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lemon.cs.elte.hu/pipermail/lemon-user/attachments/20100303/1fe669ea/attachment.html>