Degeneracy problems in mathematical programming and degeneracy graphs

Degeneracy problems in mathematical programming and degeneracy graphs

0.00 Avg rating0 Votes
Article ID: iaor1991696
Country: South Africa
Volume: 6
Start Page Number: 3
End Page Number: 36
Publication Date: Sep 1990
Journal: Orion
Authors:
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 analyzed. Cycling of the simplex method for LP is analyzed 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 analyzed.

Reviews

Required fields are marked *. Your email address will not be published.