Abstract
We consider the problem of developing an efficient algorithm for enumerating the extreme points of a convex polytope specified by linear constraints. Murty and Chung (Math Program 70:27–45, 1995) introduced the concept of a segment of a polytope, and used it to develop some steps for carrying out the enumeration efficiently until the convex hull of the set of known extreme points becomes a segment. That effort stops with a segment, other steps outlined in Murty and Chung (Math Program 70:27–45, 1995) for carrying out the enumeration after reaching a segment, or for checking whether the segment is equal to the original polytope, do not constitute an efficient algorithm. Here we describe the central problem in carrying out the enumeration efficiently after reaching a segment. We then discuss two procedures for enumerating extreme points, the mukkadvayam checking procedure, and the nearest point procedure. We divide polytopes into two classes: Class 1 polytopes have at least one extreme point satisfying the property that there is a hyperplane H through that extreme point such that every facet of the polytope incident at that extreme point has relative interior point intersections with both sides of H; Class 2 polytopes have the property that every hyperplane through any extreme point has at least one facet incident at that extreme point completely contained on one of its sides. We then prove that the procedures developed solve the problem efficiently when the polytope belongs to Class 2.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Alfakih A.Y., Yi T., Murty K.G.: Facets of an assignment problem with a 0 − 1 side constraint. J. Comb. Optim. 4, 365–388 (2000)
Avis D., Fukuda K.: A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra. Discrete Comput. Geometry 8, 295–313 (1992)
Dantzig G.B.: Linear Programming and Extensions. Princeton University Press, Princeton (1963)
Grünbaum B.: Covex Polytopes. Wiley Interscience, New York (1967)
Khachiyan, L., Boros, E., Borys, K., Elbassioni, K., Gurvich, V.: Generating All Vertices of a polyhedron is Hard. RUTCOR, Rutgers University (2006)
Murty K.G.: Adjacency on convex polyhedra. SIAM Rev. 13(3), 377–386 (1971)
Murty K.G.: Linear Programming. Wiley, New York (1983)
Murty K.G., Chung S.J.: Segments in enumerating facets. Math. Program. 70, 27–45 (1995)
Murty K.G.: A new practically efficient interior point method for LP. Algorithmic Oper. Res. 1, 3–18 (2006)
Provan J.S.: Efficient enumeration of the vertices of polyhedra associated with network LPs. Math. Program. 63, 47–64 (1994)
Tiwary, H.R.: Private communication (2007)
Ziegler G.M.: Lectures on Polytopes. Springer, New York (1994)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Murty, K.G. A problem in enumerating extreme points, and an efficient algorithm for one class of polytopes. Optim Lett 3, 211–237 (2009). https://doi.org/10.1007/s11590-008-0103-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11590-008-0103-8