NAME¶
lrslib - Convert between represetations of convex polyhedra.
SYNOPSIS¶
lrs
input.ine
lrs
input.ine | lrsbuffer
lrsfourier
file.ine [fileout]
redund
input.ine
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).
lrs is a C program that converts a
H-representation of a polyhedron to its V-representation, and vice
versa. These problems are known respectively at the
vertex
enumeration and
convex hull problems.
Fukuda's
FAQ page[1] contains a more detailed introduction to the
problem, along with many useful tips for the new user.
lrsbuffer can remove some duplicate output.
redund finds redundant
inequalities in the input.
File formats were developed jointly with Komei Fukuda and are compatible with
cdd[2].
The input for
lrs is a H- or V- representation of a polytope.
name
{representation line}
{options}
{ linearities[3]}
begin
m n rational
{input matrix}
end
{options}
name is a user supplied name for the polytope. Comments may appear
before the begin or after the end, and to avoid interpretation as an option,
should begin with a special character such as "*" or "#".
name is a user supplied name for the polytope.
representation
line is either "H-representation" or
"V-representation". If is omitted, H-representation is
assumed. The input coefficients are read in free format, and are not
checked for type. Coefficients are separated by white space. m is the number
of rows and n the number of columns of the input matrix.
H-representation¶
The integer m is the number of inequalities, and the integer n is
the dimension of the input +1. A list of inequalities contains the
coefficients of inequalities of the form
a0 + a1x1+ ... + an-1 xn-1 >= 0.
This inequality is input as the line
a0 a1... an-1
The coefficients can be entered as integers or rationals in the format x/y.
V-representation¶
The integer m is the number of vertices and rays, and the integer n
is the dimension of the input +1. Each vertex is given in the form
1 v0 v 1... vn-1
Each ray is given in the form
0 r0 r 1... rn-1
where r0 r 1... rn-1is a point on the ray.
There must be at least one vertex in each file. For bounded polyhedra there will
be no rays entered. The coefficients can be entered as integers or rationals
in the format x/y.
Note for cdd users:
lrs uses essentially the same file format as
cdd. Files prepared for
cdd should work with little or no
modification. Note that the V-representation corresponds to the
"hull" option in
cdd. Options specific to
cdd can be
left in the input files and will be ignored by
lrs. Note the
input files for
lrs are read in free format, after the line
m n
rational,
lrs will look for exactly m*n rationals or integers
separated by white space (blank, carriage return, tab etc.).
lrs
will not "drop" extra columns of input if n is less than the number
of columns supplied.
Basic Options¶
Almost all options are placed
after the end statement, maintaining
compatibility with
cdd. Where this is not the case, it will be
mentioned explicitly.
allbases This option instructs
lrs to list each vertex (or facet)
for each of its bases.
Output Duplication[4]
.[5] This option is
often combined with printcobasis.
bound x Use with H-representation - for lrs or nash Either
the maximize or minimize option should be selected. x is an integer or
rational. For maximization (resp. minimization) the reverse search tree is
truncated whenever the current objective value is less (resp. more) than
x.
cache n lrs stores the latest n dictionaries in the reverse
search tree. This speeds up the backtracking step, but requires more memory.
debug startingbasis endingbasis Print out cryptic but detailed
trace, dictionaries etc. starting at #B=startingbasis and ending at
#B=endingbasis.
debug 0 0 gives a complete trace.
digits n placed before the begin statement n is the maximum
number of decimal digits to be used. If this is exceeded the program
terminates with a message (it can usually be restarted). The
default is set to about 100 digits. At the end of a run a message is given
informing the user of the maximum integer size encountered. This may be used
to optimize memory usage and speed on subsequent runs (if doing estimation for
example).
dualperturb If lrs is executed with the maximize or minimize option, the
reverse search tree is rooted at an optimum vertex for this function.If there
are mulitiple optimum vertices, the output will often not be complete. This
option gives a small perturbation to the objective to avoid this. A warning
message is given if the starting dictionary is dual degenerate.
estimates k Estimate the output size. Used in conjunction with maxdepth -
see
Estimation.[6]
geometric // H-representation or voronoi option only //
With this option, each ray is printed together with the vertex with which it
is incident. For more information see Geometric Rays in
Hints and
Comments[5] .
incidence This option automatically switches on
printcobasis , so
see below for a description of this option first. Can be used with
printcobasis n. (Ver 4.2b) .PP For input H-representation, indices of all
input inequalities that contain the vertex/ray that is about to be output. For
a simplicial face, there is no new output, since these indices are already
listed. Otherwise, the additional tight inequalities are listed after a colon.
.PP For input V-representation, indices of all input vertices/rays that lie on
the facet that is about to be output. A starred indexindicates that this
vertex is also in the cobasis, but is not contained in the facet. It
arises due to the lifting operation used with input V-representations.
#incidence The same as printcobasis. Included for compatability with
cdd.
linearity k i1i2 i ... ik
The input contains k linearities in rows
i1i2i
... i kof the input file are equations. See
Linearities.[3]
maxdepth k The search will be truncated at depth k. All bases with depth
less than or equal to k will be computed. k is a non-negative
integer, and this option is used for estimates - see
Estimation.[6]
Note: For H-representations, rays at depth k will not be reported. For
V-representations, facets at depth k will not be reported.
maximize a0 a1...
an-1 // H-representation only //
minimize a0 a1...
an-1 // H-representation only //
If used with lrs the starting vertex maximizes (or minimizes) the function
a0 + a1x1+ ... + an-1 xn-1.The dualperturb option may be needed to avoid dual
degeneracy.See Nash Equilibria and
Linear Programming[7]
maxoutput n Limits number of output lines produced (either vertices+rays
or facets) to n
mindepth k Backtracking will be terminated at depth k, for k a
non-negative integer. This can be used for running reverse search on subtrees
as separate processes, e.g. in a distributed computing environment.
nonnegative // This option must come before the begin statement//
//H-representation only // Bug: Can only be used if the origin is a
vertex of the polyhedron For problems where the input is an
H-representation of the form b+Ax>=0, x>=0 (ie. all variables
non-negative, all constraints inequalities) it is not necessary to give the
non-negative constraints explicitly if the nonnegative option is used. This
option cannot be used for V-representations, or with the linearity option (in
which case the linearities will be treated as inequalities). This option may
be used with redund , but the implied nonnegativity constraints are not tested
themselves for redundancy. To test everything it is necessary to enter the
nonnegativity constraints explicitly in the input file. (In Ver 4.1, the
origin must be a vertex).
printcobasis k;Modified in lrs 4.0 Every k'th cobasis is printed.
If k is omitted, the cobasis is printed for each vertex/ray/facet that is
output. For a long run it is useful to print the cobasis occasionally so that
the program can be restarted if necessary.
H-representation: If
the input is an H-representation the cobasis is a list the indices of the
inequalities from the input file that define the current vertex or ray. See
option
incidence above for more information. For rays, a cobasis
is also printed. In this case the cobasis is the cobasis of the vertex from
which the ray emanates. One of the indices is starred, this indicates the
inequality to be dropped from the cobasis to define the ray. Alternatively, if
the
allbasesoption is used, all cobases will be printed out.
V-representation: If the input is a V-representation, the cobasis is a
list of the input vertices /rays that define the current facet. See option
incidence above for more information. To initiate
lrs from this
facet all 4 indices must be given in this order (omit the *).
printslack New in Ver 4.2 ; // Use with H-representation // lrs prints a
list of the indices of the input inequalities that are satisfied strictly for
the current vertex, ie. corresponding slack variable is positive. If
nonnegative is set, the list will also include indices n+i for each decision
variable xi which is positive.
project Used by
lrsfourier[8]
only.
restart V# R# B# depth {facet #s or vertex/ray #s} Modified in
lrs4.0
lrs can be restarted from any known cobasis. The calculation
will proceed to normal termination. All of the information is contained in the
output from a
printcobasis option. The
order of the indices is
very important, enter them exactly as they appear in the output from the
previously aborted run.
startingcobasis i1i2i ... in-1 This
allows the user to specify a known cobasis for beginning the reverse search.
i1i2i ... in-1 is a list of
the inequalities (for H-representation) or vertices/rays (for
V-representation) that define a cobasis. If it is invalid, or this option is
not specified,
lrs will find its own starting cobasis. The reverse
search tree is truncated(pruned) whenever a new vertex is encountered.
Note: This does note necessarily produce the set of all vertices adjacent to
the optimum vertex in the polyhedron, but just a subset of them.
verbose Print slightly more detailed information about the run.
volume // V-representation only // Compute volume - see section
Volume Computation.[9]
voronoi // V-representation only - place immediately after end
statement // Compute Voronoi diagram - see section
Voronoi
Diagrams.[10]
NOTES¶
- 1.
- FAQ page
- 2.
- cdd
- 3.
- linearities
- 4.
- Output Duplication
- 5.
- 6.
- Estimation.
- 7.
- Linear Programming
- 8.
- lrsfourier
- 9.
- Volume Computation.
- 10.
- Voronoi Diagrams.