NAME

       lrslib: Convert between representations of convex polyhedra, remove redundant
       inequalities, convex hull computation, solve linear programs in exact precision, compute
       Nash-equibria in 2-person games.

SYNOPSIS

       lrs [input-file] [output-file]

       redund [input-file] [output-file]

       mpirun -np num-proc mplrs input-file [output-file] [options]

       lrsnash [options] [input-file]

       hvref/xvref [input-file]

DESCRIPTION

       A polyhedron can be described by a list of inequalities (H-representation) or as by a list
       of its vertices and extreme rays (V-representation).  lrslib is a C library containing
       programs to manipulate these representations.  All computations are done in exact
       arithmetic.

       lrs converts an H-representation of a polyhedron to its V-representation and vice versa,
       known respectively as the vertex enumeration and facet enumeration problems (see Example
       (1) below).  lrs can also be used to solve a linear program, remove linearities from a
       system, and extract a subset of columns.

       redund removes redundant inequalities in an input H-representation and outputs the
       remaining inequalities.  For a V-representation input it outputs all extreme points and
       extreme rays. Both outputs can be piped directly into lrs.  redund is a link to lrs which
       performs these functions via the redund and redund_list options.

       mplrs is Skip Jordan's parallel wrapper for lrs/redund.

       lrsnash is Terje Lensberg's application of lrs for finding Nash-equilibria in 2-person
       games.

       hvref/xvref produce a cross reference list between H- and V-representations.

ARITHMETIC

       From version 7.1 lrs/redund/mplrs use hybrid arithmetic with overflow checking, starting
       in 64bit integers, moving to 128bit (if available) and then GMP.  Overflow checking is
       conservative to improve performance: eg. with 64 bit arithmetic, a*b triggers overflow if
       either a or b is at least 2^31, and a+b triggers an overflow if either a or b is at least
       2^62.  Typically problems that can be solved in 64bits run 3-4 times faster than with GMP
       and inputs solvable in 128bits run twice as fast as GMP.

       Various arithmetic versions are available and can be built from the makefile:

NOTES

       User's guide for lrslib
           http://cgm.cs.mcgill.ca/~avis/C/lrslib/USERGUIDE.html

AUTHOR

       David Avis <avis at cs dot mcgill dot ca >

SEE ALSO

       lrs(1), mplrs(1), lrsnash(1),