An improved \(N\)-tree algorithm for the enumeration of all neighbors of a degenerate vertex

DOI10.1007/BF02023105zbMath0786.90038MaRDI QIDQ1312773

Ferdinand Geue

Publication date: 5 May 1994

Published in: Annals of Operations Research (Search for Journal in Brave)

zbMATH Keywords

convex polyhedrasubgraphdegeneracy graphslexicographic pivot selection strategyneighborhood-problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Linear programming (90C05) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items (4)

Degeneracy subgraph of the Lemke complementary pivot algorithm and anticycling rule ⋮ A reverse search algorithm for the neighborhood problem ⋮ Degeneracy graphs: Theory and applications. An updated survey ⋮ On some properties of \(0\)-degeneracy graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the structure of the set bases of a degenerate point
• Pivoting rules and redundancy schemes in extreme point enumeration
• Degeneracy graphs and the neighbourhood problem
• An improved vertex enumeration algorithm
• A new pivoting rule for solving various degeneracy problems
• Weakly redundant constraints and their impact on postoptimal analyses in LP
• Bounds on the number of vertices of perturbed polyhedra
• Determination of the efficient set in multiobjective linear programming
• The generalized simplex method for minimizing a linear form under linear inequality restraints
• An Algorithm for Finding All Vertices of Convex Polyhedral Sets
• An algorithm for determining all extreme points of a convex polytope
• The Probability that a Random Polytope is Bounded
• New Finite Pivoting Rules for the Simplex Method
• A Technique for Resolving Degeneracy in Linear Programming
• A note on cycling in the simplex method
• An Algorithm for Determining Irrelevant Constraints and all Vertices in Systems of Linear Inequalities
• Optimality and Degeneracy in Linear Programming

This page was built for publication: An improved \(N\)-tree algorithm for the enumeration of all neighbors of a degenerate vertex