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

[Kovács Péter]

Hi All,

Alpar explained the situation clearly.

One more note: the current implementation of the network simplex 
algorithm extends the graph with an artificial root node and several 
artificial arcs connected to this root node to quickly form a starting 
basis. So, the digraph is made (weakly) connected even if it was not 
connected. Then the algorithm operates on the new digraph with spanning 
trees, but at the end, the results are interpreted in terms of the 
original digraph, that's why we obtain a spanning forest, as Alpar wrote.

So, if your digraph is not (weakly) connected, then you'd better divide 
it into components, and solve these subproblems seprately, as you wrote. 
It should be faster, but at least it cannot be slower. I would be 
pleased to hear some results about such a comparison. Of course, the 
algorithm could be extended by this separation method, but it is not 
implemented yet.

Regards,
Peter


2010.03.04. 0:44 keltezéssel, Matthew Galati írta:
> Ok. I have to think about how that would translate to an LP basis -
> which expects the number of basics to be the number of rows. Or, maybe
> I should just decompose the graph and solve each separately - which
> would be more efficient anyway - and can be multi-threaded.
>
> Thanks,
> Matt
>
> On 3/3/10, Alpar Juttner<alpar at cs.elte.hu>  wrote:
>>
>>
>> "Matthew Galati"<magh at lehigh.edu>  wrote:
>>
>>> 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?
>>
>> Yes, it does.  The number of edges in a spanning  forest (thus the size of
>> the basis) is equal to the number of nodes minus the number of connected
>> components, i.e. 256-4=252 in your case.
>>
>> Regards,
>> Alpar
>> Sent from my Android phone with K-9. Please excuse my brevity.
>