lrs home page
lrslib Ver 6.0 is a self-contained ANSI
C implementation as a callable library of the reverse search
algorithm for vertex enumeration/convex hull problems and
comes with a choice of three arithmetic
packages. Input file formats are compatible with Komei
Fukuda's cdd
package. 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 will
compile using gcc/cygwin on Windows.
New: parallel versions plrs/mplrs offer near linear
speedups for many problems on a wide range of hardware.
Documentation:
User's Guide
lrslib Guide Theoretical Description
Computational
Results Download
mplrs/plrs Computational Results
(New)
Drivers:
- lrs:
Converts
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. quickstart
- plrs: C++ wrapper
for lrs that allows for parallelization using the Boost library
on shared memory multi-core machines and is described here
quickstart
talk
- (New in
6.0) mplrs:
C wrapper for lrs that allows for parallelization on clusters of
machines and uses the MPI library quickstart
- redund: Removes redundant
inequalities from an H-representation. Finds the extremal
vertices in a V-representation
- nash, 2nash: Computes all Nash
equlibria of a two person non-cooperative game. Can handle
bounds on payoff functions. 2nash is a 2-processor parallel
version
- fourier: Temporarily withdrawn due to reported bugs.
Libraries:
- lrslib: A
callable library of functions implementing the above drivers
- 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
2015.7.23
School of
Informatics, Kyoto University and School of Computer Science, McGill University