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

[Kovács Péter]

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
>
>