ISSN:
1572-9338
Keywords:
Linear programming
;
interior point methods
;
degeneracy
;
polynomial algorithms
;
global and local convergence
;
basis recovery
;
numerical performance
;
sensitivity analysis
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
,
Economics
Notes:
Abstract The publication of Karmarkar's paper has resulted in intense research activity into Interior Point Methods (IPMs) 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, we survey the various theoretical and practical issues related to degeneracy in IPMs for linear programming. We survey results, which, for the most part, have already appeared in the literature. Roughly speaking, we 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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02096259
Permalink
