Degeneracy problems in mathematical programming and degeneracy graphs

Abstract

Degeneracy may cause various computing and other complications in any mathematical programming problem of the kind where the constraint set 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 its properties analysed. Cycling of the simplex method for LP is analysed and a method to construct cycling examples of arbitrary size is proposed. The neighbourhood problem is solved by a new approach to determine a minimal N-tree (N for neighbour), and an efficient method to determine all vertices of a convex polytope is described. A new version of the simplex method is indicated that does not need Phase 1, should be faster than commercial codes and automatically contains an anticycling device. For a degenerate optimal solution of an LP-problem, sensitivity analysis as well as shadow price determination and interpretation are tackled by using a special class of DG's, the so-called optimum DG's. The connection between weakly redundant constraints, a degenerate optimal solution of the associated LP and sensitivity analysis as well as shadow price determination is analysed.