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)