1lrslib(5)                         lrslib 7.2                         lrslib(5)
2
3
4
5   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
10   Synopsis
11       lrs [input-file] [output-file]
12
13       redund [input-file] [output-file]
14
15       fel [input-file] [output-file]
16
17       mpirun -np num-proc mplrs input-file [output-file] [options]
18
19       lrsnash [options] [input-file]
20
21       hvref/xvref [input-file]
22
23       checkpred [input-file]
24
25   Description
26       A polyhedron can be described by a list of inequalities
27       (H-representation) or as by a list of its vertices and extreme rays
28       (V-representation).  lrslib is a C library containing programs to
29       manipulate these representations.  All computations are done in exact
30       arithmetic.
31
32       lrs(1) converts an H-representation of a polyhedron to its
33       V-representation and vice versa, known respectively as the vertex
34       enumeration and facet enumeration problems (see Example (1) below).
35       lrs can also be used to solve a linear program, remove linearities from
36       a system, and extract a subset of columns.
37
38       redund(1) removes redundant inequalities in an input H-representation
39       and outputs the remaining inequalities.  For a V-representation input
40       it outputs all extreme points and extreme rays. Both outputs can be
41       piped directly into lrs.  redund is a link to lrs which performs these
42       functions via the redund and redund_list options.
43
44       fel(1) projects an input H-representation onto a given set of variables
45       using Fourier-Motzkin elimination.  For a V-representation it extracts
46       the specified columns.  The output is non-redundant and can be can be
47       piped directly into lrs.  fel is a link to lrs which performs these
48       functions via the eliminate and project options.
49
50       mplrs(1) is Skip Jordan's parallel wrapper for lrs/redund/fel.
51
52       lrsnash(1) is Terje Lensberg's application of lrs for finding Nash-
53       equilibria in 2-person games.
54
55       hvref(1) xvref(1) produce a cross reference list between H- and V-
56       representations.
57
58       checkpred(1) is Skip Jordan's utility to create and verify logical
59       formulas for determining whether a given inequality is redundant after
60       eliminating variables, without eliminating the variables.
61
62
63   Arithmetic
64       lrsarith(5) From version 7.1 lrs/redund/mplrs use hybrid arithmetic
65       with overflow checking, starting in 64bit integers, moving to 128bit
66       (if available) and then GMP.  Overflow checking is conservative to
67       improve performance: eg. with 64 bit arithmetic, a*b triggers overflow
68       if either a or b is at least 2^31, and a+b triggers an overflow if
69       either a or b is at least 2^62.  Typically problems that can be solved
70       in 64bits run 3-4 times faster than with GMP and inputs solvable in
71       128bits run twice as fast as GMP.
72
73       Various arithmetic versions are available and can be built from the
74       makefile.
75
76
77   Notes
78       User's guide for lrslib
79           http://cgm.cs.mcgill.ca/~avis/C/lrslib/USERGUIDE.html
80
81   Author
82       David Avis <avis at cs dot mcgill dot ca >
83
84   See Also
85       lrs (1), mplrs(1), fel(1), lrsnash(1), hvref(1), xvref(1),
86       checkpred(1), lrsarith(5)
87
88
89
90
91January 2022                      2022.01.19                         lrslib(5)
Impressum