lrs home page
lrslib Ver 4.2 is a
ANSI C implementation
as a callable library of the reverse search algorithm for vertex
problems and comes with a
choice of three arithmetic packages. Input file formats are
with Komei Fukuda's cdd
package. All computations are
done exactly in either
multiple precision or fixed integer arithmetic. Output is
in memory, so even problems with very large output sizes can sometimes
solved. The program is intended for Unix/Linux platforms, but will
compile using gcc/cygwin on Windows.
an H-representation (half-space) of a polyhedron to a V-representation
(vertex/ray) or vice versa. Estimates the number of
vertices/rays or facets of a polyhedron. Computes the volume of a
polytope given by a list of vertices. Solves LP problems over a
polyhedron given by an H-representation. Compute the Voronoi vertices
and rays for an input set of data points.
- redund: Removes
redundant inequalities from an H-representation. Finds the extremal
vertices in a V-representation
- nash: Computes
all Nash equlibria of a two person non-cooperative game. Can handle
bounds on payoff functions.
- fourier: Projects a polyhedron
given by an H-representation onto a
subspace using Fourier elimination (contributed by Tallman Nkgau).
callable library of functions implementing the above drivers
- lrsmp: A
multiple precision arithmetic package for lrslib
- lrslong: A fixed precision
package for lrslib
A multiple precision
arithmetic package for lrslib based on GNU MP.
Links to related software
Compute vertices of a set of generated hypercubes
Compute facets of a set of generated cyclic polytopes
Solve a set of linear programs for generated hypercubes
The program can be distributed freely under the
PUBLIC LICENSE. Please read the file COPYING carefully before using.
Computer Science, McGill University, 3480 University,
, Quebec, Canada H3A 2A7
last update: 2005.6.1