Survey of solved and open problems in the degeneracy phenomenon

DOI10.1007/BF01589397zbMath0641.90049MaRDI QIDQ1101009

Peter Zörnig, Tomas Gal, Hermann-Josef Kruse

Publication date: 1988

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

zbMATH Keywords

sensitivityall vertices of a convex polytopecycling of the simplex methoddegeneracy graphminimal N-treeneighbourhood problemshadow prices determinationweakly redundant constraints

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Sensitivity, stability, parametric optimization (90C31) Linear programming (90C05) Polytopes and polyhedra (52Bxx)

Related Items

On the line graphs of the complete \(r\)-partite graphs, Degeneracy subgraph of the Lemke complementary pivot algorithm and anticycling rule, A new pivoting rule for solving various degeneracy problems, Systematic construction of examples for cycling in the simplex method, Sensitivity analysis of the optimal assignment., Approaches to sensitivity analysis in linear programming, On the connectedness of optimum-degeneracy graphs, Degenerate optimal basis graphs in linear programming, 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

Cites Work

• Unnamed Item
• Unnamed Item
• Redundancy in mathematical programming. A state-of-the-art survey
• On the structure of the set bases of a degenerate point
• Degeneracy graphs and the neighbourhood problem
• Shadow prices and sensitivity analysis in linear programming under degeneracy. State-of-the-art-survey
• The generalized simplex method for minimizing a linear form under linear inequality restraints
• A Note on Shadow Prices in Linear Programming
• An analysis of degeneracy
• The Computation of Shadow Prices in Linear Programming
• Occurrences of cycling and other phenomena arising in a class of linear programming models
• New Finite Pivoting Rules for the Simplex Method
• A Technique for Resolving Degeneracy in Linear Programming
• Convex Polytopes
• Optimality and Degeneracy in Linear Programming