Dan Moniz's question:
---------------------

In step 2 of the Network Simplex Method, after we push flow along a
cycle C in T + uv, could it be that only arc uv is saturated or empty?
(So that no arc in the tree could be removed for the update?)

Response:
---------

Yes, it could happen that uv is the only arc in C that is saturated or 
empty after we push flow along the cycle. In this case, there is no
update made to the tree T. In a degenerate pivot (when the flow pushed
is 0), though, there is necessarily a tree-arc that is either saturated
or empty, and one such arc should be removed in the tree update.

For instance, consider the digraph D = ({1,2,3}, {12,23,31})
with node-demands b_1 = -1, b_3 = +1, and w_uv (x_uv,c_uv) triples:

arc 12:  0(1,3)
arc 23:  0(1,3)
arc 31: -1(0,1)

This is a tree flow with T consisting of arcs {12,23}. The corresponding
potentials are all 0 for nodes 1,2,3.
However, the reduced cost for arc 31 is -1 < 0, but x_31 = 0. So we push
flow of 1 along the cycle (3,1,2,3). There is no update to the tree. Arc
31 now satisfies the optimality condition.


Correction to Network Simplex Algorithm:
----------------------------------------

In the lectures, I mistakenly claimed that there would always be a
tree-arc u'v' that is either saturated or empty. Please correct this in
Step 2 of the algorithm. This part should read:

    If there is an arc u'v' on the cycle C and in T which is saturated 
    or empty, then update the tree as T <-- T + uv - u'v'. (Else, there 
    is no update.)

Note that if the tree is not updated, the potentials do not change, but
we have one less violated arc.