lrs home page
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
Functions of redund:
- Remove redundant inequalities from an H-representation
- Find the extremal vertices in a V-representation
Libraries:
- 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.
Demos:
- 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
Links to related software
The program can be distributed freely under the GNU GENERAL
PUBLIC LICENSE. Please read the file COPYING carefully before using.
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