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

[Matthew Galati]

Thanks Alpár,

It would seem that we want the tree arcs in the final spanning tree (to
maintain optimality). I see that you are putting them first in the arcs
object. Looking at kruskals, it first sorts that object. How can you be sure
that those arcs are chosen first by Kruskal's - since the algorithm will
choose based on weight? To be safe, maybe we should put an artificially low
weight on those tree arcs in the arcs object?

Matt






2010/3/9 Alpár Jüttner <alpar at cs.elte.hu>

> 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?
>
> Anyway, you can reconstruct the basis quite easily from the solution
> without having to touch the network simplex implementation.
>
> 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
>
>
>
> 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> <
> 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
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lemon.cs.elte.hu/pipermail/lemon-user/attachments/20100309/278e5516/attachment.html>