An Algorithm for Determining Irrelevant Constraints and all Vertices in Systems of Linear Inequalities

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.