|
Abstract : |
This paper describes an implementation of Chernikova's algorithm for finding an irredundant set of vertices for a given polyhedron defined by a set of linear inequalities and equations. This algorithm can also be used for the dual problem: given a set of extremal rays and vertices, find the associated irredundant set of facet supporting hyperplanes. The method is an extension of initial Chernikova's algorithm (nonnegative domain), and is mainly based on the polyhedral cone duality principle. A new enhancement for extremal ray detection is presented together with its effects on a class of polyedra. KEY WORDS: System of linear inequalities and equations, polyhedral cones, duality, homogeneous coordinates, bidirectional coordinates, Chernikova's algorithm. 1, |
