An updated survey on degeneracy in mathematical programming and degeneracy graphs: A survey with new results

The concepts of a degenerate vertex of a convex polytope, of the representation graph of a convex polytope and of various types of degeneracy graphs (DG’s for short) of a degenerate vertex are introduced. Some properties of the DG’s are surveyed. Efficiency problems like cycling of the simplex method are mentioned and the neighborhood problem is indicated for illustration. Optimum DG’s are introduced and sensitivity analysis under degeneracy is discussed. Interrelations among degeneracy, weakly redundant constraints and sensitivity analysis are indicated. Further applications of DG’s to linearly constrained mathematical programming problems as well as to nonlinear programming, integer, combinatorial etc. programming are mentioned.