Originally posted by: JimDan

Greetings,

I am referring to paper "Enhancements of spanning tree labelling procedures for network optimization" by Barr, Glover and Klingman. This paper provides details of efficient basis update for the primal network simplex method.

The method proceeds by maintaining a tree T rooted at node r with dual value 0. Once an arc (p,q) enters the basis, a cycle if formed and a min ratio test determines the leaving arc (u,v) so that the tree structure is maintained. Rooting a tree T at node r means that node r is the only node at depth/level of 0. All other nodes have a depth/level greater than 0 depending on the number of hops to be taken to reach the root node.

Note that given T, if one removes arc (u,v), the tree splits into two smaller trees, T1 and T2 (say).

One of the steps of the basis exchange is that the dual values of nodes either in T1 (that subtree that contains r) or T2 (that subtree that does not contain r) have to be updated so as to maintain complementary slackness conditions. There are rules that the authors specify to choose T1 or T2 whose duals are to be updated. The basic idea is to choose that subtree for dual update which has the least number of nodes.

Now, suppose T1 (which contains r) is chosen for dual value update. Then, there need not be any node in new basis tree that has dual value 0. 

After a series of iterations, this could lead to values of dual variables that increase without bound. Not that this is a problem, but in certain cases, after a large number of simplex iterations, the dual values could exceed the integer limit of variables in Visual C++.

I was wondering if anyone with experience working with primal network simplex codes knows how to handle this issue.

One thought that comes to my mind is that if the value of any dual (assume all duals have nonnegative values) exceeds some large positive integer M, visit each node and reset its dual by subtracting M from each dual value.

Could we do any better than this? How does netopt deal with this issue?

Thanks in advance.

Originally posted by: BoJensen

It sometimes helps to think the network setup in a standard LP context. A column in a pure network has two non zeroes, since we have -1.0 and 1.0 for the leaving node and entering node. A basis for a network problem has not full rank, since one row of the basis will be linear dependent. It's actually this dependency which can be explored to update the smaller tree for the duals, since the solution is not unique.

It's correct that updating this way may overflow an integer value. But depending on the network structure, each dual may also decrease, since update for the subtree maybe negative. To avoid the overflow, you could monitor the maximum dual and then recalculate the duals from root node if overflow occurs. Notice there's no guarantee this recalculation will not overflow an integer value either. If the duals can not be stored in an integer, then you have to use doubles.

Originally posted by: JimDan

Thanks Bo.

Indeed, the dual values can increase as well as decrease. I had mentioned that they are nonnegative just for illustrative purposes.

So, it appears that the only way to be sure so as to prevent overflow is that at some point I would have to traverse the entire tree using the thread[] index if I choose to update T1 or T2 and keep doing this repeatedly.

The other option appears to me to be that the dual values will always be updated only in sub tree T2 (the one that does not contain the root node.) That way, the root node can always have 0 as its dual value. The downside here is that T2 could be a rather large tree as compared to T1.

Apart from these two, I don't think there are any other efficient ways to update dual values.

Originally posted by: BoJensen

I think in a real life application, if the dual calculation overflow in the smallest tree update, then there's also a fair chance it will overflow with the recalculation and in this case using doubles is the only solution.

Originally posted by: BoJensen

Minor correction. As a colleague of mine pointed out, using doubles, just to protect against overflow in storing an integer value, is not the best idea. Using a 64 bit integer is much better. I guess my answer was affected by the fact, I was also thinking about handling fractional objectives.