[Lemon-user] number of STATE_TREE vars at end of network simplex (on connected graph)

[Kovács Péter]

Dear All,

> Hmmm. I didn't noticed before, that the bases in the two representations
> aren't necessarily the same. Shouldn't NetworkSimplex provide this
> functionality built-in?

I don't find it important, because you can easily constuct a basis using 
the flow values, as you wrote.

> Anyway, you can reconstruct the basis quite easily from the solution
> without having to touch the network simplex implementation.

Yes, you can obtain those arcs that must be in all bases without having 
to touch the implementation. And you can extend it arbitrarily to a 
spanning tree (a basis), e.g. using Kruskal. However, you cannot obtain 
the actual basis the algorithm found, but it does not seem important.

> For this you have to select the arcs the flow of which are neither at
> the lower nor at the upper bound, then you have to extend these arcs to
> a spanning tree. You can do it in almost linear time with Kruskal alg,
> like this:
>
> int A=countArcs(g);
> ///This will contain<arc,cost>  pairs. We don't use the second value
> ///but only the order. Kruskal will pick up the arcs starting from the
> ///beginning of this vector.
> std::vector<std::pair<Graph::Arc,int>  >  arcs(A);
> int b=0;
> int e=A-1;
> ///Fill the `arcs` with the edges,
> ///those are not on the boundary will come first
> for(Graph:ArcIt a(g);a!=INVALID;++a)
>    if(lower[a]<flow[a]&&  flow[a]<upper[a])
>      arcs[b++] = std::pair<Graph::Arc,int>(a,1);
>    else arcs[e--] = std::pair<Graph::Arc,int>(a,1);
> ///This vector will contain the basis:
> std::vector<Arc>  basis;
> ///Run kruskal. We don't know the size of the solution in advance,
> ///that's why we start with az empty vector and use the back_inserter
> kruskal(g,arcs,std::back_inserter(basis));
>
> See the kruskal doc for more details
> http://lemon.cs.elte.hu/pub/doc/1.1.2/a00443.html#ga0b63cab19a2f168772a13d7c59449eb
>
> Disclaimer: I haven't try to compile the code above, so you should
> except bugs/typos in it.
>
> Regards,
> Alpar

Regards,
Peter


> On Tue, 2010-03-09 at 08:02 +0100, Kovács Péter wrote:
>> Dear Matt,
>>
>> In short, the network simplex algorithm works with an extended graph,
>> not the original one. This method causes the unexpected results.
>>
>> For more details, recall the notes I wrote in one of my previous emails:
>>
>>   >  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 you have a digraph with n nodes, then the algorithm extends it to
>> a digraph with n+1 nodes and operates on it with spanning trees (that
>> have n arcs). If you restrict these trees into the original arcs, then
>> you may get a forest, not a tree, even if your original digraph is
>> connected. (Some artificial arcs may remain in the basis at the end.)
>>
>> These internal data are not public, so you have to modify the
>> network_simplex.h file. E.g. you can paste the following lines at the
>> end of the start() function:
>>
>>       int basic1 = 0;
>>       for (int j = 0; j != _arc_num; j++) {
>>         if (_state[j] == STATE_TREE) basic1++;
>>       }
>>       int basic2 = basic1;
>>       for (int j = _arc_num; j != _all_arc_num; j++) {
>>         if (_state[j] == STATE_TREE) basic2++;
>>       }
>>       std::cout<<  "Number of nodes: "<<  countNodes(_graph)<<  std::endl;
>>       std::cout<<  "Number of basic arcs in the original graph:"
>>                 <<  basic1<<  std::endl;
>>       std::cout<<  "Number of basic arcs in the extended graph:"
>>                 <<  basic2<<  std::endl;
>>
>> The results for your network are the following:
>>
>> Number of nodes: 1000
>> Number of basic arcs in the original graph: 995
>> Number of basic arcs in the extended graph: 1000
>>
>> If you do need a spanning tree, i.e. n-1 basic arcs in the original
>> digraph (supposing it is weakly connected), then you can extend the
>> obtained forest _arbitrarily_ to a spanning tree.
>>
>> I hope, I could made it clear.
>>
>> Best regards,
>> Peter
>>
>>
>> 2010.03.09. 2:45 keltezéssel, Matthew Galati írta:
>>> FYI - I tried updating to trunk version of network_simplex.h. I am now
>>> getting 995 basics at the end.
>>>
>>> ====================
>>>
>>> Hi - I have a new example of where the number of STATE_TREE vars is not what
>>>
>>>
>>> I had expected.
>>>
>>> The number of nodes=1000, the number of basics = 987 at the end of
>>> optimization. I checked and the graph is connected. Any ideas?
>>>
>>> The data is here:http://coral.ie.lehigh.edu/~magh/tmp/net.dimacs2<http://coral.ie.lehigh.edu/%7Emagh/tmp/net.dimacs2>
>>>
>>>
>>>
>>> Thanks,
>>> Matt
>>>
>>>
>>
>> _______________________________________________
>> Lemon-user mailing list
>> Lemon-user at lemon.cs.elte.hu
>> http://lemon.cs.elte.hu/mailman/listinfo/lemon-user
>
>