A Survey and Comparison of Methods for Finding All Vertices of Convex Polyhedral Sets

DOI10.1287/moor.5.2.167zbMath0442.90050OpenAlexW2030334004MaRDI QIDQ3885508

Publication date: 1980

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

Full work available at URL: https://doi.org/10.1287/moor.5.2.167

zbMATH Keywords

survey computational results convex polytopes comparison of algorithms convex polyhedral sets finding all vertices

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Linear programming (90C05) Inequalities and extremum problems involving convexity in convex geometry (52A40) Specification and verification (program logics, model checking, etc.) (68Q60) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02) Polytopes and polyhedra (52Bxx)

Related Items

The geometry of certain fixed marginal probability distributions, A branch and bound algorithm for extreme point mathematical programming problems, Constructing the set of efficient objective values in linear multiple objective transportation problems, A LIBRARY FOR DOING POLYHEDRAL OPERATIONS, Capturing the essence of a metabolic network: a flux balance analysis approach, A finite cutting plane method for facial disjunctive programs, Algorithms to solve some problems of concave programming with linear constraints, Efficient solution generation for multiple objective linear programming based on extreme ray generation method, Ranking and selection for multiple performance measures using incomplete preference information, A method for solving d.c. programming problems. Application to fuel mixture nonconvex optimization problem, Properties of least squares estimates in set membership identification, A common formula to compute the efficient sets of a class of multiple objective linear programming problems, Geometry of possibility measures on finite sets, Practical issues on the projection of polyhedral sets, Enumerative techniques for solving some nonconvex global optimization problems, On finding new vertices and redundant constraints in cutting plane algorithms for global optimization, Segments in enumerating faces, A recursive algorithm for volume-based sensitivity analysis of linear decision models, Bounds on the complexity of halfspace intersections when the bounded faces have small dimension, An approximation method for computing the expected value of max-affine expressions, Mathematical systems for enhancing diffuse images of point sources, A penalty method for the identification of nonlinear elliptic differential operator, A representation of an efficiency equivalent polyhedron for the objective set of a multiple objective linear program, Markov chains with doubly stochastic transition matrices and application to a sequence of non-selective quantum measurements, Fourier algorithm revisited, Efficient allocation of resources to a portfolio of decision making units, The multidimensional truncated moment problem: Gaussian mixture reconstruction from derivatives of moments, Optimal distributions for multiplex logistic networks, Bi-objective optimization problems with two decision makers: refining Pareto-optimal front for equilibrium solution, Which nonnegative matrices are slack matrices?, A finite cutting plane method for solving linear programs with an additional reverse convex constraint, An improved vertex enumeration algorithm, Spatial multi-attribute decision analysis: axiomatic foundations and incomplete preference information, A Calculation of all Separating Hyperplanes of two Convex Polytopes, A state-set estimation algorithm for linear systems in the presence of bounded disturbances, Constructing the set of efficient objective values in multiple objective linear programs, Binary choice models with discrete regressors: identification and misspecification, Errors bounds for finite approximations of coherent lower previsions on finite probability spaces, Bilevel multiplicative problems: A penalty approach to optimality and a cutting plane based algorithm, (Deterministic) algorithms that compute the volume of polytopes, Exact and approximate approaches to the identification of stochastic MAX-plus-linear systems, A finite algorithm for solving the generalized lattice point problem, On-line and off-line vertex enumeration by adjacency lists, A new pivoting rule for solving various degeneracy problems, A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra, UNCERTAINTY AND ESTIMATION IN RECONSTRUCTABILITY ANALYSIS, Scenario-based portfolio model for building robust and proactive strategies, Linear dynamics for the state vector of Markov chain functions, On a calculation of an arbitrary separating hyperplane of convex polyhedral sets, Separating support hyperplanes for a pair of convex polyhedral sets, Unnamed Item, Generation and presentation of nearly optimal solutions for mixed-integer linear programming, applied to a case in faming system design, A validation and verification tool for global optimization solvers, An extreme-point-ranking algorithm for the extreme-point mathematical programming problem, Model predictive control for perturbed max-plus-linear systems, Delaunay-based derivative-free optimization via global surrogates. I: Linear constraints, Reduction techniques for network validation in systems biology, Finding and identifying optimal inventory levels for systems with common components, The generalized linear complementarity problem and an algorithm to find all its solutions, Performance of some boundary-seeking mode estimators on the dome bias model, Multiattribute utility functions, partial information on coefficients, and efficient choice, Combinatorial optimization and small polytopes, A new algorithm to find all vertices of a polytope, An algorithm for a class of nonlinear fractional problems using ranking of the vertices, Linear programming in tector criterion markov and semi-Markov decision processes, Optimization over the efficient set of a parametric multiple objective linear programming problem, The design of optimum component test plans in the demonstration of a series system reliability, Binomial mixtures: Geometric estimation of the mixing distribution, On minimal generators for semi-closed polyhedra, Ranking of vertices in the linear fractional programming problem, A NON-SPECIFICITY MEASURE FOR CONVEX SETS OF PROBABILITY DISTRIBUTIONS, A statistical approach to the analytic hierarchy process with interval judgements. I: Distributions on feasible regions, Optimal scaling of balls and polyhedra, Pivoting rules and redundancy schemes in extreme point enumeration, Selected bibliography on degeneracy, Degeneracy graphs: Theory and applications. An updated survey, Using Gale transforms in computational geometry, Efficient enumeration of the vertices of polyhedra associated with network LP's, Obtaining simultaneous solutions of linear subsystems of inequalities and duals, Extending quantum operations, Computing low-capacity 0–1 knapsack polytopes