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

[Alpár Jüttner]

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