Computational experience with the reverse search vertex enumeration algorithm

1 January 1998

journal article
research article
Published by Taylor & Francis in Optimization Methods and Software

Vol. 10 (2) , 107-124
https://doi.org/10.1080/10556789808805706

Abstract

This paper describes computational experience obtained in the development of the Irs code, which uses the reverse search technique to solve the vertex enumeration/convex hull problem for d-dimensional convex polyhedra. We give empirical results showing improvements obtained by the use of lexicographic perturbation, lifting, and integer pivoting. We also give some indication of the cost of using extended precision arithmetic and illustrate the use of the estimation function of Irs.The empirical results are obtained by running various versions of the program on a set of well-known non-trivial polyhedra: cut, configuration, cyclic, Kuhn-Quandt, and metric polytopes.

Keywords

This publication has 9 references indexed in Scilit:

Primal—Dual Methods for Vertex and Facet Enumeration
Discrete & Computational Geometry, 1998
How good are convex hull algorithms?
Computational Geometry, 1997
Geometry of Cuts and Metrics
Published by Springer Nature ,1997
Ground states of a ternary fcc lattice model with nearest- and next-nearest-neighbor interactions
Physical Review B, 1994
A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
Discrete & Computational Geometry, 1992
Preface
Discrete Applied Mathematics, 1985
On the Extreme Rays of the Metric Cone
Canadian Journal of Mathematics, 1980
Combinatorial Analysis and Computers
The American Mathematical Monthly, 1965
An experimental study of the simplex method
Proceedings of Symposia in Applied Mathematics, 1963