lrslib is a self-contained ANSI C implementation
of the reverse search algorithm for vertex enumeration/convex hull
problems. Version 4.1 is implemented as a callable library and comes with two main driver programs:
lrs and redund, a set of demo drivers suitable for customization, and a
choice of three arithmetic packages. Input file formats are compatible
with Komei Fukuda's cdd package.
An input file consists of either an H-representation (half-space description)
or V-representation (vertex/ray description) of a convex polyhedron, which
need not be of full dimension. Linearities, respectively hyperplanes or lines,
are allowed in either description. All computations are done exactly in either
multiple precision or fixed integer arithmetic. Output is not stored
in memory, so even problems with very large output sizes can sometimes be
solved. The program is intended for Unix/Linux platforms, but Win98 binaries
are also provided, *caveat emptor*. The old workhorse lrs3.2a is still available, but
no longer maintained.

Documentation: User's Guide.
lrslib Guide.
Theoretical Description.
Computational
Results. Download
Testdrive.

Functions of lrs:

- Convert an H-representation to a V-representation: the vertex enumeration problem
- Convert a V-representation to an H-representation: the facet enumeration problem
- Estimate the number of vertices/rays or facets of a polyhedron
- Compute the volume of a polytope given by a list of vertices
- Solve LP problems for a polyhedron given by an H-representation
- Compute the Voronoi vertices and rays for an input set of data points
- The ability to suspend and restart execution at any time

- Remove redundant inequalities from an H-representation
- Find the extremal vertices in a V-representation

- lrslib: A callable library of functions implementing lrs and redund
- lrsmp: A multiple precision arithmetic package for lrslib
- lrslong: A fixed precision integer package for lrslib

lrsgmp: A multiple precision arithmetic package for lrslib based on GNU MP.

- vedemo.c Compute vertices of a set of generated hypercubes
- chdemo.c Compute facets of a set of generated cyclic polytopes
- lpdemo.c Solve a set of linear programs for generated hypercubes

David Avis avis@cs.mcgill.ca http://www.cs.mcgill.ca/~avis

Computer Science, McGill University, 3480 University, Montreal , Quebec, Canada H3A 2A7

last update: 2004.8.24