lrs home page
lrslib is a selfcontained ANSI
C implementation 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.
Download
New: Release of v7.0: hybrid arithmetic versions of lrs/redund/mplrs offer
speedups of 25 times for combinatorial polytopes.
Documentation:
User's Guide
lrslib Guide Theoretical Description
Computational
Results Applications
mplrs/plrs Computational
Results (new) mplrs:Theoretical
Description(new)
slides
Drivers:
 lrs:
Converts
an
Hrepresentation
(halfspace)
of a polyhedron to a Vrepresentation (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
Hrepresentation. Compute the Voronoi vertices and rays for an
input set of data points. quickstart

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 Hrepresentation. Finds the extremal
vertices in a Vrepresentation

lrsnash, 2nash: Computes all Nash
equlibria of a two person noncooperative game. 2nash is a
2processor parallel version
 fourier: Temporarily withdrawn due to reported bugs.
Interface:
 Matlab:
GeoCalcLib, an interface
to lrs and redund developed by Rainer Schaich
Libraries:
 lrslib: A
callable library of functions implementing the above drivers
except lrsnash
 lrsnash: A callable
library of routines for computing Nash equilibria (used with
lrslib)
 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
2018.10.30
School of
Informatics, Kyoto University and School of Computer Science, McGill University