Survey of solved and open problems in the degeneracy phenomenon
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.
- A Note on Shadow Prices in Linear Programming
- A Technique for Resolving Degeneracy in Linear Programming
- An analysis of degeneracy
- Convex Polytopes
- Degeneracy graphs and the neighbourhood problem
- scientific article; zbMATH DE number 3626518 (Why is no real title available?)
- scientific article; zbMATH DE number 3634009 (Why is no real title available?)
- New Finite Pivoting Rules for the Simplex Method
- Occurrences of cycling and other phenomena arising in a class of linear programming models
- On the structure of the set bases of a degenerate point
- Optimality and Degeneracy in Linear Programming
- Redundancy in mathematical programming. A state-of-the-art survey
- Shadow prices and sensitivity analysis in linear programming under degeneracy. State-of-the-art-survey
- The Computation of Shadow Prices in Linear Programming
- The generalized simplex method for minimizing a linear form under linear inequality restraints
- Shadow prices and sensitivity analysis in linear programming under degeneracy. State-of-the-art-survey
- Degeneracy in transportation problems
- Degeneracy graphs and simplex cycling
- A new pivoting rule for solving various degeneracy problems
- Weakly redundant constraints and their impact on postoptimal analyses in LP
- On the connectedness of optimum-degeneracy graphs
- Balinski-Tucker simplex tableaus: Dimensions, degeneracy degrees, and interior points of optimal faces
- Selected bibliography on degeneracy
- Degeneracy graphs: Theory and applications. An updated survey
- Bounds on the number of vertices of perturbed polyhedra
- On degeneracy and collapsing in the construction of the set of objective values in a multiple objective linear program
- On some properties of \(0\)-degeneracy graphs
- On the line graphs of the complete r-partite graphs
- Degeneracy subgraph of the Lemke complementary pivot algorithm and anticycling rule
- Degeneracy degrees of constraint collections
- Degenerate optimal basis graphs in linear programming
- Sensitivity analysis of the optimal assignment.
- An exploratory computational analysis of dual degeneracy in mixed-integer programming
- Systematic construction of examples for cycling in the simplex method
- scientific article; zbMATH DE number 3896665 (Why is no real title available?)
- A note on degeneracy in linear programming
- An analysis of degeneracy
- scientific article; zbMATH DE number 1163805 (Why is no real title available?)
- Small degenerate simplices can be bad for simplex methods
- scientific article; zbMATH DE number 4114364 (Why is no real title available?)
- Approaches to sensitivity analysis in linear programming
- On the structure of the set bases of a degenerate point
This page was built for publication: Survey of solved and open problems in the degeneracy phenomenon
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1101009)
