Survey of solved and open problems in the degeneracy phenomenon (Q1101009)

Degeneracy may cause various computing problems and other kind of complications in any mathematical programming problem the constraints set of which defines a convex polyhedral set (particularly, a polytope). In order to be able to study various, seemingly independent degeneracy phenomena from a unifying viewpoint a so called degeneracy graph (DG for short) is defined, and a general theory of DG's for 2-, 3- and higher degenerate vertices is developed. Based on this theory an answer to the question why and when cycling of the simplex method for LP occurs is found. Also a method is proposed how to construct cycling examples of arbitrary size. The so-called neighbourhood problem, i.e. the determination of neighbouring vertices of a degenerate vertex is dealt with and a new approach to determine a minimal N-tree (N for neighbour) is under consideration. A by-product of this research should be an efficient method to determine all vertices of a convex polytope independently of whether degeneracy occurs or not. Further research in this direction uses the minimal N-tree method for elaborating a new version of the simplex method that does not need Phase 1 and should be faster than conventional professional codes. This code will include also an anticycling device. In a degenerate optimal solution of an LP-problem sensitivity as well as shadow prices determination and interpretation is tackled by using a special class of DG's, so called optimum DG's. Applying the theory of optimum DG's, also the connection between weakly redundant constraints, a degenerate optimal solution of the associated LP and sensitivity analysis as well as shadow prices determination is analyzed.