An algorithm for determining all extreme points of a convex polytope

DOI10.1007/BF01593771zbMath0378.90059WikidataQ56324214 ScholiaQ56324214MaRDI QIDQ4159164

Martin Dyer, L. G. Proll

Publication date: 1977

Published in: Mathematical Programming (Search for Journal in Brave)

Mathematics Subject Classification ID

Linear programming (90C05) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02) Polytopes and polyhedra (52Bxx)

Related Items

Farkas Certificates and Minimal Witnesses for Probabilistic Reachability Constraints, Directional differentiability of optimal solutions under Slater's condition, The generalized jacobian of the optimal solution in parametric optimization, Extreme point Quadratic Minimization Problem, A common formula to compute the efficient sets of a class of multiple objective linear programming problems, Evolution, games theory and polyhedra, Practical issues on the projection of polyhedral sets, Enumerative techniques for solving some nonconvex global optimization problems, Segments in enumerating faces, Fourier algorithm revisited, Linear optimization with fuzzy variable over fuzzy polytope, Linear programs with an additional reverse convex constraint, A simple algorithm for the-linear bilevel programming problem, On the calculation of a membership function for the solution of a fuzzy linear optimization problem, On the use of cuts in reverse convex programs, An improved vertex enumeration algorithm, A Calculation of all Separating Hyperplanes of two Convex Polytopes, Errors bounds for finite approximations of coherent lower previsions on finite probability spaces, An Interactive Polyhedral Approach for Multi-objective Combinatorial Optimization with Incomplete Preference Information, On the duality of a non-convex optimization problem and the strong unicity constant in linear Chebyshev approximation, A new pivoting rule for solving various degeneracy problems, On a calculation of an arbitrary separating hyperplane of convex polyhedral sets, Separating support hyperplanes for a pair of convex polyhedral sets, A validation and verification tool for global optimization solvers, Enumerating Vertices of Covering Polyhedra with Totally Unimodular Constraint Matrices, Generating all vertices of a polyhedron is hard, Enumerating Vertices of 0/1-Polyhedra associated with 0/1-Totally Unimodular Matrices, Sufficient optimality criterion for linearly constrained, separable concave minimization problems, Restricting weights in value efficiency analysis., On degeneracy in enumeration, Linearly constrained global optimization: a general solution algorithm with applications., Pivoting rules and redundancy schemes in extreme point enumeration, Selected bibliography on degeneracy, Degeneracy graphs: Theory and applications. An updated survey, An improved \(N\)-tree algorithm for the enumeration of all neighbors of a degenerate vertex, Efficient enumeration of the vertices of polyhedra associated with network LP's, Enumerating extreme points of a highly degenerate polytope

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An algorithm for determining redundant inequalities and all solutions to convex polyhedra
• Finding all vertices of a convex polyhedron
• An Algorithm for Finding All Vertices of Convex Polyhedral Sets
• A Node Method for Multiparametric Linear Programming
• Technical Note—Vertex Generation and Cardinality Constrained Linear Programs
• Algorithm for finding a general formula for the non-negative solutions of a system of linear inequalities
• Solving Certain Nonconvex Quadratic Minimization Problems by Ranking the Extreme Points
• Letter to the Editor—An Algorithm for Ranking all the Assignments in Order of Increasing Cost
• Extreme Point Mathematical Programming
• Solving the Fixed Charge Problem by Ranking the Extreme Points
• An Algorithm for Determining Irrelevant Constraints and all Vertices in Systems of Linear Inequalities