# lrslib - Man Page

### Name

lrslib: Convert between representations of convex polyhedra, remove redundant inequalities, find minimum representations, 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]*

**minrep** *[input-file] [output-file]*

**fel** *[input-file] [output-file]*

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

**lrsnash** *[options] [input-file]*

**hvref/xvref** *[input-file]*

**polyv** *[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(1) 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(1) 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.

minrep(1) performs the same functions as redund(1) but in addition searches for hidden linearities in the input. These are made explicit in the output which is a minimum representation of the polyhedron.

fel(1) projects an input H-representation onto a given set of variables using Fourier-Motzkin elimination. For a V-representation it extracts the specified columns. The output is non-redundant and can be can be piped directly into *lrs*. *fel* is a link to *lrs* which performs these functions via the **eliminate** and **project** options.

mplrs(1) is Skip Jordan's parallel wrapper for *lrs/redund/minrep/fel*.

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

hvref(1) xvref(1) produce a cross reference list between H- and V-representations.

polyv(1) is Skip Jordan's utility to create logical formulas for checking equivalence between H- and V- representations or determining whether a given inequality is redundant after eliminating variables, without eliminating the variables.

### Arithmetic

lrsarith(5) 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), redund(1), minrep(1), mplrs(1), fel(1), lrsnash(1), hvref(1), xvref(1), polyv(1), lrsarith(5)

## Referenced By

fel(1), lrs(1), lrsarith(5), lrsnash(1), lrsscripts(5), mplrs(1), polyv(1), redund(1), xref(1).