lrslib is a self-contained 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. Precompiled linux/Windows
binaries supplied for small problems.

**lrsarith** (new)is a light self-contained ANSI C
package of arithmetic routines used in lrslib.
It contains fixed precision integer/rational arithmetic in 64 and
128-bit integers as well as extended precision interfaces to
GMP/FLINT/lrsMP. A hybrid template allows automatic use of
64/128/GMP arithmetic. Overflow protection is included. Download
includes sample programs.

Download
Debian/Ubuntu distribution:
sudo apt install lrslib (maintained by
David Bremner <bremner at debian.org> )

**Release of v7.1:** All C
library using hybrid arithmetic offering speedups of 2-5 times for
combinatorial polytopes. New:
parallel redund computation via **mplrs**.

Documentation:
User's Guide
lrslib Guide Theoretical Description
Computational
Results ** **Applications
lrsarith (new)

mplrs/plrs Computational
Results** **mplrs:Theoretical
Description** **
slides

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. New: vertex/facet cross reference list can be created. quickstart
- redund: Removes redundant inequalities from an H-representation. Finds the extremal vertices in a V-representation
**mplrs**: Skip Jordan's C wrapper for lrs/redund that allows for parallelization on clusters of machines and uses the MPI library quickstart

- lrsnash, 2nash:
Computes all Nash equlibria of a two person non-cooperative
game. 2nash is a 2-processor parallel version

- fourier: Temporarily withdrawn due to reported bugs.

Interface:

- Matlab:
GeoCalcLib, an interface
to lrs and redund developed by Rainer Schaich

- 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.

- 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 2021.1.29 School of Informatics, Kyoto University and School of Computer Science, McGill University