Degeneracy problems in mathematical programming and degeneracy graphs

Open Access
Publisher Website
Google Scholar
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

This publication has 0 references indexed in Scilit: