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

[Matthew Galati]

I checked and the graph is, in fact, disconnected. It has 4 connected
components. Does this somehow explain the fact that the number of basics is
less than the number of rows?

Thanks,
Matt



On Wed, Mar 3, 2010 at 3:51 PM, Matthew Galati <magh at lehigh.edu> wrote:

> 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/8d891b6f/attachment.html>