lrslib is a self-contained C
implementation of the reverse search algorithm for vertex
enumeration/convex hull problems consisting primarily

of lrs (limited multithreading) and
mplrs (openMPI). Other problems in
Polyhedral Computation can also be solved, including two person
games. The library comes with a choice of
several arithmetic packages. Input file formats are
compatible with Komei Fukuda's cddlib
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 WSL or cygwin on Windows. Precompiled
Linux/Windows binaries are supplied for small problems.

**lrsarith** (new)is a light self-contained 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
Binaries
Debian/Ubuntu (currently v7.1):
sudo apt install lrslib (maintained by
David Bremner <bremner at debian.org> )

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

** **mplrs:Theoretical
Description** **
Parallel Redundancy Removal
lrslib Guide
Applications
slides

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

- V-H
transformation: converting an H-representation to a
V-representation and vice versa (v7.3 new
lrs now multithreaded)

- 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 and finding a minimum representation (v7.3 new, fully parallel in mplrs ) of an H or V-representation
- Projecting a polyhedron to a subset of its variables (Fourier elimination) (v7.3 now fully parallel in mplrs)
- 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 (currently full
dimensional input only)

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