Degeneracy in Interior Point Methods for linear programming: A survey

The publication of Karmarkar’s paper has resulted in intense research activity into Interior Point Methods (IMPs) for linear programming. Degeneracy is present in most real-life problems and has always been an important issue in linear programming, especially in the Simplex method. Degeneracy is also an important issue in IPMs. However, the difficulties are different in the two methods. In this paper, the authors survey the various theoretical and practical issues related to degeneracy in IPMs for linear programming. They survey results, which, for the most part, have already appeared in the literature. Roughly speaking, the authors shall deal with the effect of degeneracy on the following: the convergence of IPMs, the trajectories followed by the algorithms, numerical performance, and finding basic solutions.