1. An Algorithm for Determining Irrelevant Constraints and all Vertices in Systems of Linear Inequalities.
- Author
-
Mattheiss, T. H.
- Subjects
ALGORITHMS ,EMBEDDINGS (Mathematics) ,ALGEBRAIC geometry ,LINEAR programming ,MATRICES (Mathematics) ,MATHEMATICAL programming ,VECTOR analysis - Abstract
This paper describes a new method of generating all vertices of a given convex polytope. Additionally, irrelevant constraints are easily identified without the necessity of enumerating any of the vertices of the given convex polytope. The method embeds the given polytope in a one-higher-dimensional space. The projection of the additional vertices formed by the embedding process into the original space lie in the interior of the polytope and have a tree structure for one and two polytopes. For higher dimensions, the embedding process associates a number with each interior point that facilitates the construction of a spanning tree for all of the interior points. The interior points added can be efficiently generated by a variant of the simplex method. The vertices of the original polytope can be generated easily from these internal points by analyzing the appropriate simplex tableaux. [ABSTRACT FROM AUTHOR]
- Published
- 1973
- Full Text
- View/download PDF