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

Documentation:
User's Guide
online
manual (new) lrs:Theoretical Description
Computational Results ** ** lrsarith (new)

** **mplrs:Theoretical
Description** **
lrslib Guide
Applications
slides

**Functions of ***mplrs*/*lrs***
include: **

- V-H
transformation: converting an H-representation to a
V-representation and vice versa

- Estimating
the number of vertices/rays or facets of a polytope, and
estimating the total running time (lrs only)

- Triangulating and computing the volume of a polytope given by a V-representation
- Removing redundancy from an H or V-representation
- Projecting a polyhedron to a subset of its variables (Fourier elimination) (v7.2 new)
- Determining if an inequality is redundant
in computing the projection to a subset of its variables
(uses SMT-solver, v7.2 new)

- Solving linear
programming problems in exact arithmetic (Simplex method,
lrs only)

- Computing the Voronoi
vertices and rays for an input set of data points and the
corresponding Delaunay
triangulation

- Eliminating variables in linearities in H-representations and extracting columns from V-representations (lrs only)
- Computing all Nash equilibria for 2-person matrix games (lrsnash)
- Computing a cross
reference table of vertices/rays vs facets

- The ability to suspend and restart execution at any time

- 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