Studies of lexicography in the generalized network simplex method

This paper introduces an analytical approach for studying lexicography in generalized network problems. The equations obtained can be used to understand and to extend the existing theory. First, it is verified that all nonzero elements have the same sign in each row vector of a basis inverse for a generalized network (GN) problem with positive multipliers. However, this property does not necessarily hold when there exist negative multipliers. Second, the authors developed a strategy to select the dropping arc in the GN simplex algorithm when addressing GN problems with positive and negative multipliers. This strategy is also based on lexicography and requires performing some comparisons. However, the values to be compared are already known since they can be obtained as a by-product of the calculations necessary to compute the basis representation of the entering arc. Consequently, the computational effort per pivot step is O(n) in the worst case. This worst case effort is the same as that required by the strongly convergent rules for selecting the dropping arc in the method of strong convergence.