lrs home page                                           v7.2       

 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

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