Generating All the Faces of a Polyhedron

Abstract

The determination of all the extreme points of a given convex polyhedron$P \subset \mathbb{R}^n $ generally requires a substantial amount of computations; this note presents a conceptually simple algorithm for this purpose. Unlike other methods, the procedure generates only those basic solutions which are extreme points (i.e., only feasible basic solutions). More generally, this approach is able to generate all the faces of any dimension$k(0\leqq k\leqq n)$, that is, all those k-dimensional subpolyhedra which lie on the boundary of the given polyhedron P.