lrs home page                                           v7.3      

 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

 
The program can be distributed freely under the GNU GENERAL PUBLIC LICENSE. Please read the file COPYING carefully before using.