## table of contents

LRSLIB(1) | lrslib 7.1 | LRSLIB(1) |

# 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

# AUTHOR¶

David Avis <avis at cs dot mcgill dot ca >

# SEE ALSO¶

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

2020.06.10 | July 2009 |