(in reference to problem #35)
On 3/23/00 at 7:01 AM, GENE_RYE@udlp.com wrote:

Dr. Spingarn:

The goal here is to reduce cost once a feasible tree has been found. That feasible tree is - I believe - two sub trees, one composed of the inner three nodes, and one composed of the outer 4. I was able to put the work together to find this, but only by modifying somewhat the stated methods. The system of find a bad arc, include it in a path, change the flow, and drop an arc did not work well. I could get it to work, after a fashion, but it was not elegant. Do the rules permit the addition of multiple arcs at once?
No. At each iteration, precisely one arc drops out of the spanning tree and one arc is added to the spanning tree. You must keep careful track of which arcs are in the tree, or you will become lost. A spanning tree for a network with n nodes always has exactly n-1 arcs. The method should work without having to modify it. If at some time you have the choice of dropping an original arc or an artificial arc, you might choose to drop the original arc, just in order to achieve the decomposition (I don't know whether this will actually happen).
Since the division method specified in the book and in class centers around dividing the network into regions of potential, what is the rule when the solved network has both original and "new" arcs with zero flows connecting the parts together? Is the potential calculated based on the cost of the original arc or the "new" arc. Is the proper method to completely eliminate original arcs with zero flow and replace them with "new" arcs with zero flow in order to complete a tree?
The original arcs have cost $0 and the artificial arcs have cost $1. Specify the potential arbitrarily (100) at one node(*) and propogate it through the TREE. There is always a UNIQUE path from * to every other node that uses only tree arcs. Because of this uniqueness there is no ambiguity in determining the potential.

On 3/24/00 at 6:00 AM, GENE_RYE@udlp.com wrote:
In reference to problem #34

This of course is the one that was started in class, and left as assignment for the student to finish.....

I think I guessed my way through it enough to pick up the clues and hints of how the matrix method is supposed to work, and I think I got a solution. It only required one iteration (in itself, that is suspect), but the final requirement of the problem, the verification that c'x = b'p has me puzzled.

Yes it does sound suspect. Try working the problem first using nodes and arcs. Then try doing the corresponding steps with matrices.

In this problem, C is a 5 X 4 matrix. The flow solution, X, is a 5 X 4 matrix, granted it has a lot of zero entries in it. C ' is a 4 X 5 matrix.... When c'x is computed a 5 X 5 matrix results. This is all well and fine, except that b and p are both column vectors and b'p is therefore a scalar. I do not see how to make a 5 X 5 matrix equal a scalar, unless perhaps it is the det (c'x) that we are to use in this comparison? So, what is the magic trick to make this work?

c'x is not matrix multiplication. It is a dot product. In this context, c' is supposed to be the row vector of costs and x is the corresponding column vector of flows. You multiply the flow xj in arc j by the cost cj of arc j, and then you add up these products.