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

T. H. Mattheiss
Additional contact information
T. H. Mattheiss: Southern Illinois University, Carbondale, Illinois

Operations Research, 1973, vol. 21, issue 1, 247-260

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.

Date: 1973
References: Add references at CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.21.1.247 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:21:y:1973:i:1:p:247-260

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().