A Study of Degeneracy in the Simplex Algorithm for Linear Programming and Network Flow Problems (Optimization, Mathematical).

Degeneracy has been the subject of much research in the field of mathematical programming, since it is related to the computational efficiency of the simplex algorithm. In the presence of degeneracy, the simplex algorithm may cycle forever by visiting the same set of bases indefinitely. Even if cycling does not occur, the simplex algorithm may "stall" in the same basic feasible solution of the problem for a long sequence of degenerate pivot steps before its optimality is established or a better solution is found. Studying degeneracy is not only important computationally, it is also of theoretical value in the field of computational complexity because to prove the optimality of a current degenerate solution, or to find a strictly better solution, in the simplex algorithm is computationally equivalent to solving another linear program in itself. This dissertation is concerned with the phenomenon of degeneracy as it affects the simplex algorithm for solving linear programming problems. In the first chapter, we present an overview of degeneracy, its computational and theoretical significance in the operation of the simplex algorithm, and a summary of the current methods for resolving it. Chapter 2 contains a study of degeneracy and methods for resolving it in the primal simplex algorithm for pure and generalized networks. In particular, we study Cunningham's method of strong feasibility for avoiding cycling in the primal network simplex algorithm and show that it is equivalent to the st and ard lexico-simplex algorithm for general LP's. In Chapter 3, degeneracy in the dual network simplex algorithm is discussed and a perturbation based method is presented to avoid cycling under degeneracy in that method. Finally, Chapter 4 presents a specialization of the lexico-simplex algorithm to the Generalized Upper Bounding Technique for structured linear programs and its application in avoiding cycling in the primal simplex algorithm for network flow problems with additional linear constraints.Ph.D.Operations researchUniversity of Michiganhttp://deepblue.lib.umich.edu/bitstream/2027.42/160401/1/8502909.pd