Resolution of degeneracy in generalized networks and penalty methods for linear programs.

Abstract

We introduce an analytical approach for studying lexicography in generalized network (GN) problems. Based on that we show that the strongly convergent algorithm, due to Elam et al. (1979), is equivalent to the lexico-simplex method. Also, we develop a strategy to select the dropping arc in the GN simplex algorithm when addressing GN problems with positive and negative multipliers. This strategy requires, in the worst case, an O(n) computational effort for selecting the dropping arc at each pivot step. This effort is the same as that required in the method of strong convergence. This thesis also deals with a piecewise linear penalty method for solving linear programs. We extend the penalty algorithm of Bartels (1980) in the following aspects: efficient computation of the step size, relaxation of the nondegeneracy assumption and a proof of the early stopping conditions. Moreover, a new approach for increasing the value of the penalty parameter has been outlined. This penalty algorithm seems to be a very competitive alternative to the simplex method as indicated by the experiments of Bartels (1980) and Gamble et al. (1989). We specialize this penalty algorithm for solving network flow problems. It is shown that the MCR Penalty Algorithm due to Gamble et al. (1989) for solving pure network problems admits stalling. Alternatively, we develop the Strongly Feasible (SF) Penalty Algorithm which has all the advantages of the MCR Penalty Algorithm and still provide us with a strategy to avoid stalling. The SF Penalty Algorithm uses a generalized concept of strongly feasible partitions, proposed by Marins (1987). This algorithm should perform better than Gamble et al.'s (1989) algorithm since its anti-cycling strategy is more efficient. We also propose a specialization of the penalty algorithm to solve GN flow problems. The resulting algorithm has been further refined to obtain the Strongly Convergent Penalty Algorithm which is proven finite by using a generalization of the concept of strongly convergent partitions. The generalized concepts of strong feasibility and strong convergence apply naturally to other flow problems with piecewise objective function, such as those studied by Rockafellar (1984).