1LRSLIB(1)                         lrslib 7.1                         LRSLIB(1)
2
3
4

NAME

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

SYNOPSIS

11       lrs [input-file] [output-file]
12
13       redund [input-file] [output-file]
14
15       mpirun -np num-proc mplrs input-file [output-file] [options]
16
17       lrsnash [options] [input-file]
18
19       hvref/xvref [input-file]
20

DESCRIPTION

22       A polyhedron can be described by a list of inequalities
23       (H-representation) or as by a list of its vertices and extreme rays
24       (V-representation).  lrslib is a C library containing programs to
25       manipulate these representations.  All computations are done in exact
26       arithmetic.
27
28       lrs converts an H-representation of a polyhedron to its
29       V-representation and vice versa, known respectively as the vertex
30       enumeration and facet enumeration problems (see Example (1) below).
31       lrs can also be used to solve a linear program, remove linearities from
32       a system, and extract a subset of columns.
33
34       redund removes redundant inequalities in an input H-representation and
35       outputs the remaining inequalities.  For a V-representation input it
36       outputs all extreme points and extreme rays. Both outputs can be piped
37       directly into lrs.  redund is a link to lrs which performs these
38       functions via the redund and redund_list options.
39
40       mplrs is Skip Jordan's parallel wrapper for lrs/redund.
41
42       lrsnash is Terje Lensberg's application of lrs for finding Nash-
43       equilibria in 2-person games.
44
45       hvref/xvref produce a cross reference list between H- and V-
46       representations.
47

ARITHMETIC

49       From version 7.1 lrs/redund/mplrs use hybrid arithmetic with overflow
50       checking, starting in 64bit integers, moving to 128bit (if available)
51       and then GMP.  Overflow checking is conservative to improve
52       performance: eg. with 64 bit arithmetic, a*b triggers overflow if
53       either a or b is at least 2^31, and a+b triggers an overflow if either
54       a or b is at least 2^62.  Typically problems that can be solved in
55       64bits run 3-4 times faster than with GMP and inputs solvable in
56       128bits run twice as fast as GMP.
57
58       Various arithmetic versions are available and can be built from the
59       makefile:
60
61

NOTES

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

AUTHOR

67       David Avis <avis at cs dot mcgill dot ca >
68

SEE ALSO

70       lrs(1), mplrs(1), lrsnash(1),
71
72
73
74
75July 2009                         2020.06.10                         LRSLIB(1)
Impressum