User's Guide for lrs  Version 3.2 a
November 30,
1998
Copyright(C) 1998
Introduction
Installation
File Formats
Basic Options
Estimation
Linear Programming
Volume Computation
Voronoi Diagrams
Extreme
Point Enumeration and Redundant Inequalities
Timing and Interrupts
Error Messages and
Troubleshooting
Hints and Comments
Acknowledgements and References
Introduction
A polyhedron can be described by a list of inequalities (Hrepresentation)
or as by a list of its vertices and extreme rays (Vrepresentation).lrs
is
a C program that converts a Hrepresentation of a polyhedron to its
Vrepresentation,
and vice versa. These problems are known respectively at the vertex
enumeration and convex hull problems.
lrs is based on
the reverse search algorithm of Avis
and Fukuda(1992), modified to use lexicographic pivoting and
implemented in rational arithmetic. See Avis(1998a)
for
a technical description, and Avis(1998b)
for some computational experience. The input files are in Polyhedra
format, developed by Fukuda and the author. The format is
essentially
selfdual, and the output file produced can be read in as an input
file,
with very minor modifications, to perform the reverse transformation.
This
format is compatible with that used in Fukuda'scddpackage,
which performs the same transformations using a version of the double
description method. cdd can also be used in
conjunction
with lrs as a preprocessor for projections to subspaces, or
as
a post processor for computing the entire face lattice. Another program
using the same file format is the primaldual method pd,
developed
by Bremner, Fukuda and
Marzetta(1997).
It is essentially dual to lrs, and is very efficient for
computing
Hrepresentations of simple polyhedra, and Vrepresentations of
simplicial
polyhedra. It will compute the volume of a polytope given by an
Hrepresentation.
The cdd manual contains a more detailed introduction to the
problem,
along with many useful tips for the new user. Another program for based
on the double description method is Christof and Loebel's porta,
and a versatile tool for the algorithmic treatment of polytopes is
Gawrilow and Joswig's polymake
package. Barber et al.'s qhull
and some visualization programs, can be found at the Geometry
Center. A package for volume computation has been developped by
Bueeler
and Enge.
A comprehensive general source of related infomation are Erickson's Computational
Geometry Pages.
Polyhedra handled by lrs must be full dimensional and
contain
at least one vertex. lrs accepts either integer or
rational
input, and produces integer or rational output. All computations are
done
exactly using extended precision arithmetic. Since it is a pivot based
method, it can be very slow for degenerate inputs: i.e..
Hrepresentations
of nonsimple polyhedra, and Vrepresentations of nonsimplicial
polyhedra.
On the other hand, it does not store the vertices/ rays or facets
produced,
so for very large problems it may be the only method that can solve the
problem. A discussion of various vertex enumeration/convex hull
methods
and the types of polyhedra that cause them to behave badly is contained
in Avis,
Bremner
and Seidel( 1997).
Additional functions of lrs include:

Estimating the number of vertices/rays or facets of a polytope, and
estimating
the total running time

Computing the volume of a polytope given by a Vrepresentation

Solving LP problems for a polyhedron given by a Hrepresentation

Computing the Voronoi vertices and rays for an input set of data points

The ability to suspend and restart execution at any time
This program can be distributed freely under the GNU GENERAL PUBLIC
LICENSE.
Please read the file COPYING carefully before using. Please
inform
the author of any interesting applications for which lrs was
helpful.
Installation

Access the ftp site (ftp://mutt.cs.mcgill.ca/pub/C)
and copy at least the files lrs3.2a.c, buffer.c, cube.ine,
cube.ext

Compile using the command
gcc O o lrs lrs3.2a.c
or if you have a 64 bit machine (e.g.. DEC Alpha)
gcc O DB64 o lrs lrs3.2a.c
If you have trouble compiling, try compile option
DOMIT_SIGNALS and/or DOMIT_TIMES

Compile buffer.c using the command
gcc O o buffer buffer.c

Test the program by typing:
cube
Vrepresentation
begin
***** 4 rational
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
end
This is a list of the 8 vertices with each coordinate +/
1.
The ***** should be replaced by the actual number, 8, of vertices.
Since
lrs
does not save the output produced, it does not know this value until
the
execution terminates. This output is now essentially the same as file
cube.ext.
To complete the test type:
Now the output produced is essentially the file
cube.ine,
with the inequalities appearing in a different order.
The program buffer is optional. It is used to remove duplicate
line
in the output they may occur if the input is not a polytope or a
pointed
cone. For such unbounded polyhedra, rays may appear in the output
more than once. The program takes two optional integer parameters:
It builds a circular buffer of maxbuffer (default 50) lines of maxline
(default 5000)characters each. If an output line is already in the
buffer,
it is not output. To use buffer, pipe the output from lrs:
File Formats
The input for lrs is a H or V representation of a polytope.
These files have the following formats:
Hrepresentation
name
Hrepresentation
begin
m n rational
{list of inequalities }
end
{options)
name is a user supplied name for the
polytope. If
the line Hrepresentation is omitted, Hrepresentation is
assumed.
The input coefficients are read in free format, and are not checked for
type. Coefficients are separated by white space. Normally this file
would
be saved with filename suffix .ine but this not required.
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 "#".
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
a_{0} + a_{1 }x_{1 }+ ... + a_{n1}
x_{n1} >= 0.
This inequality is input as the line
a_{0 }a_{1 }... a_{n1}
The coefficients can be entered as integers or rationals in the
format
x/y.
For example, the square centred at the origin with side length two
has inequalities
1 + x_{1} >= 0 1+ x_{2
}>=0
1x_{1 }>=
0
1x_{2 }>=0
and would be represented by the input file
square
*centred square of side 2
Hrepresentation
begin
4 3 rational
1 1 0
1 0 1
1 1 0
1 0 1
end
Vrepresentation
name
Vrepresentation
begin
m n rational
{list of vertices and extreme rays}
end
{options)
name is a user supplied name for the polytope.
The line Vrepresentation is required. The input coefficients are
read in free format, and are not checked for type. Coefficients are
separated
by white space. 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 "#".Normally this file would be stored with filename
suffix
.ext, but this is not required.
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 v_{0 } v _{1 }...
v_{n1}
Each ray is given in the form
0 r_{0 } r _{1 }...
r_{n1}
where r_{0 } r _{1 }... r_{n1}is
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.
For example, the unit square centred at the origin has vertices
(1,1) ,(1,1),(1,1),(1,1)
and would be represented by the input file
square
*centred square of side 2
Vrepresentation
begin
4 3 rational
1 1 1
1 1 1
1 1 1
1 1 1
end
The positive quadrant has vertex (0,0) and rays (1,0) (0,1) and is
represented
quadrant
*positive quadrant
Vrepresentation
begin
3 3 rational
1 0 0
0 1 0
0 0 1
end
Its Hrepresentation contains the inequalities x_{1 }>=
0 and
x_{2} >= 0 :
quadrant
*positive quadrant
Hrepresentation
begin
2 3 rational
0 1 0
0 0 1
end
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
Vrepresentation
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 rationallrs
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
lrs has many options to allow various functions to be
performed,
and to modify the output produced. Almost all options are placed after
the end statement, maintaining compatibility with cdd. Where
this
is not the case, it will be mentioned explicitly. All options are
optional.
allbases
This option instructs lrs to list each vertex (or facet) for
each of its bases. Normally a vertex (or facet) is only output when its
lexmin basis is found, to avoid duplications  see section Output
Duplication . This option is
often
combined with printcobasis.
cache n
lrs stores the latest n dictionaries in the reverse
search
tree. This speeds up the backtracking step, but requires more
memory.
If n is set to one, there is no caching and "pure" reverse search is
performed.
The default is n=10. At the end of a run a message gives cache
information.
The output
*Dictionary Cache: max size= 4 misses=
10/1340
Tree Depth=5
indicates that with cache size set to 4, only 10 of the 1340
dictionaries computed were not in the cache during backtracking
and
had to be recomputed. The maximum tree depth was 5, so there would be
no
misses with a cache size of 6. Full caching reduces processing time by
about 40%.
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). The output:
*Max digits= 45/100
indicates that the maximum integer encountered had 45 decimal digits,
and the program allowed up to 100 digit integers.
estimates k
Estimate the output size. Used in conjunction with maxdepth  see Estimation.
geometric
// Hrepresentation or voronoi option only //
With this option, each ray is printed together with the vertex with
which it is incident. They output has the form:
0 r_{0 } r _{1 }...
r_{n1}* 1 v_{0 } v _{1 }...
v_{n1}
This indicates ray 0 r_{0 } r _{1
}...
r_{n1}is incident with vertex 1 v_{0 }
v _{1 }... v_{n1}. For the
quadrant,
the output is:
1 0 0
0 0 1 * 1 0 0
0 1 0 * 1 0 0
This indicates the origin is a vertex, and there are two geometric
rays: (0,t) and (t,0) both adjacent to the origin. For more information
see Geometric Rays in Hints and
Comments.
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 nonnegative integer, and this option is used for estimates  see Estimation.
Note: For Hrepresentations, rays at
depth
k will not be reported. For Vrepresentations, facets at depth k will
not
be reported.
maximize
// Hrepresentation only //
minimize
mindepth k
Backtracking
will be terminated at depth k, for k a nonnegative integer. This can
be
used for running reverse search on subtrees as separate processes, e.g.
in a distributed computing environment.
printcobasis k
Every k'th cobasis is printed. If k is omitted, k=1 is assumed and
all cobases are printed. For a long run it is useful to print the
cobasis
occasionally so that the program can be restarted if necessary.
Hrepresentation: If the
input is an Hrepresentation the cobasis is a list the indices of the
inequalities
from the input file that define the current vertex or ray. For example,
with input cube.ine a typical output is:
V#5 R#0 B#5 h=1 facets 3 4 5 det=1
1 1 1 1
This indicates that the vertex (1,1,1) is
defined
by the 3rd, 4th and 5th facet inequalities in the input file being
satisfied
as equations. It is the B#=5th basis
computed,
and there have been V#=5 vertices and R#=0 rays output up to this point.
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. For example the output:
V#1 R#6 B#4 h=1 facets 2 4* 5 7 det=1
0 1 1 2 1
indicates that the ray (1,1,2,1) emanates from
a vertex with cobasis defined by input inequalities 2 4 5 7 satisfied
as
equations. The ray is defined by dropping the equation with index 4.
Note
that there may not appear any vertex in the output with cobasis 2 4 5
7,
since the corresponding vertex may be degenerate and printed with
another
(the lexmin) cobasis. To find out which vertices correspond to which
rays,
use also the geometric option.
Now the output may appear:
V#1 R#6 B#4 h=1 facets 2 4* 5 7 det=1
0 1 1 2 1 * 1 0 0 0 0
This indicates that the ray is incident to the
origin. Alternatively, if the allbases
option
is used, all cobases will be printed out.
Vrepresentation: If the input is a Vrepresentation, the
cobasis
is a list of the input vertices /rays that define the current facet.
For
example, with input file cube.ext a typical output is:
V#1 F#3 B#4 h=2 vertices/rays 2 3 4
5 det=8
1 0 0 1
Here the output V#1 can
be ignored. There have been 3 facets output up to this point, and 4
bases
have been computed. This facet is defined by the vertices in positions
2,3,4,5 in the input file.
restart V# R# B# depth {facet #s or
vertex/ray
#s}
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.
To restart from cobasis:
V#5 R#0 B#5 h=1 facets 3 4 5 det=1
enter:
restart 5 0 5 1 3 4 5
startingcobasis i_{1 }i_{2 }i
... i_{n1}
This allows the user to specify a known cobasis
for beginning the reverse search. i_{1
}i_{2
}i
... i_{n1}_{ }is a
list
of the inequalities (for Hrepresentation) or vertices/rays (for
Vrepresentation)
that define a cobasis. If it is invalid, or this option is not
specified,
lrs will find its own starting cobasis. For example, with
cube.ine,
the user can start at vertex (1,1,1) by specifying:
startingcobasis 1 3 4
volume
// Vrepresentation only //
voronoi
// Vrepresentation only //
Estimation
The estimation feature of lrs allows estimates to be made of
the output size and running time. These are based on Knuth's technique
for estimating the size of backtracking trees, and are described in Avis
and Devroye(1994). The estimate is unbiased, that is the
expected
value of the estimate is the actual value. To get an estimate use the maxdepth
option to limit the search depth, and the estimatesoption:
maxdepth d
estimates k
This will cause lrs to perform k random probes from each
node of the tree at depth d. k should be at least 1 and d at least
zero.
Hrepresentation: If the input is an Hrepresentation, the
program
gives an unbiased estimate of the number of vertices and rays in
the Vrepresentation, and the total number of bases that will be
computed by lrs. For the Hrepresentation cube.ine,
the options
maxdepth
1 and estimates 1
produce
the output:
*Estimates: vertices=9
rays=0
bases=9
*Total number of tree nodes evaluated: 6
In this case the Vrepresentation of the cube is estimated to have
9 vertices, and it is estimated that lrs will compute a total
of
9 bases. The estimate was based on evaluating 6 tree nodes. Note:
The estimate for the number of rays may be an overestimate if the
polyhedron
is not a cone, since some rays may be duplicated in the output  see
subsection
Output
Duplication.
Vrepresentation: If the input
is
a Vrepresentation, the program gives an unbiased estimate of the
number
of facets in the Hrepresentation, and the total number of bases that lrs
will compute. For Vrepresentation cube.ext, the options maxdepth
0 and estimates 3 produce
the output:
*Estimates: facets=7 bases=8
*Total number of tree nodes evaluated: 7
In this cases it is estimated that the Hrepresentation of the cube
will contain 7 facets, and it is estimated that lrs will
compute
a total of 7 bases to find it. The estimate was formed by evaluating 7
tree nodes. Note: The number of facets estimated may be an
overestimate
if the polyhedron is not bounded  see subsection Output
Duplication.
Voronoi diagrams: Estimates for the number of Voronoi
vertices
and Voronoi rays for a Vrepresentation of a set of data points may be
obtained by combining the voronoi, estimates
and maxdepth options.
Repeated estimates: In order to get estimates with
different
random probes, lrs can be given a seed for the random number
generator.
There are two ways: an option and a command line argument.
seed n
The integer n is used as a seed for the random
number generator.
The command line argument is an integer n which will be the seed
and
overrides a seed given as an option.
lrs n < filename
Using the estimator: The running time of lrs is
proportional
to the number of bases, so an estimate of the number of bases gives an
easy way to estimate the running time for solving the complete problem
by lrs. For the case of polytopes that contain the origin, a
Vrepresentation
can be processed as an Hrepresentation and viceversa (this is an
application
of duality). Hence facet estimates for a Vrepresentation can also be
obtained
by running the problem as an Hrepresentation with the estimates
option.
The estimated number of vertices will be in this case be an unbiased
estimate
for the number of facets for the original problem. So running the
estimator
on the file cube.ext with the header set as Hrepresentation , maxdepth
0 and estimates 3, we
get
the output:
*Estimates: vertices=5
rays=0 bases=9
*Total number of tree nodes evaluated: 8
Since the origin is an interior point, the
estimated
number of vertices is an accurate estimate of the number of facets of
the
Hrepresentation of the cube. Similarly, estimates for an
input
Hrepresentation of a polytope containing the origin may be obtained by
processing the file as a Vrepresentation. The output will be
essentially
the same, but the number of bases computed may be very different, see
the
subsection H vs
Vrepresentation.
For a large problem of this type, it is useful to get estimates for the
number of bases that lrs will compute for both V and
Hrepresentations,
so that simpler problem can be chosen.
The estimates may also be used to judge the feasibility of solving
the
problem using other codes. For example, any code that uses
triangulation/perturbation
to resolve degeneracy will have trouble if the number of bases is huge.
Codes which must store all the output in memory (currently all codes
except
reverse search methods such as lrs) will have trouble if the
estimated
output size is huge.
Linear Programming
lrs can be used to solve linear programming problems in
rational
arithmetic when the input is an Hrepresentation. The option:
maximize a_{0}
a_{1 }... a_{n1}
// Hrepresentation only //
simply maximizes the function a_{0} + a_{1 }x_{1
}+
... + a_{n1} x_{n1}
over the given polyhedron. A optimal vertex is given when it
exists, otherwise for unbounded solutions a vertex and ray is given. A
minimization will be performed if the following option is
specified:
minimize a_{0}
a_{1 }... a_{n1}
// Hrepresentation only //
Volume Computation
lrs can be used to compute the volume of a polytope given as a
Vrepresentation.
The option
volume
// Vrepresentation only //
will cause the volume to be computed. For input cube.ext, the output
is:
*Volume=8
If the volume option is applied
to an Hrepresentation, the results are not predictable.
For polytopes given by a Hrepresentation, it will first be
necessary
to compute the Vrepresentation. Alternatively the program pd
may be used, which works directly with the Hrepresentation.
Voronoi Diagrams
lrs can be used the compute the Vvertices of a Voronoi diagram
of a set of data points in n1 dimensional space. To do this we use a
standard
lifting procedure (see, e.g., Edelsbrunner, "Algorithms in
Combinatorial
Geometry," pp 296297) . Each point is mapped to a half space tangent
to
the parabaloid in n dimensions, by the mapping:
p_{1 } , p_{2 } , ...., p_{n1}
> (p_{1 }^{2 }+
p_{2}^{2
}+ ... + p_{n1}^{2 }
)  2 p_{1} x_{1 }  2 p_{2 } x_{2
} ....  2 p_{n1 }x_{n 1 } + x _{n}>=
0
lrs is applied to the Hrepresentation so created. This
transformation is performed automatically for a Vrepresentation if the
voronoi
// Vrepresentation only //
option is specified.
Note: The input file must consist entirely of data points (no
rays), i.e.. there must be a one in column one of each line. The volume
option
should not be used, since the volume reported will not be the volume of
the original Vrepresentation.
The output will consist of the Voronoi vertices (columns beginning
with a one) and Voronoi rays (columns beginning with zero) for the
Voronoi
diagram defined on the data points. If the printcobasis
option is given, the n "data points"
indices produced will tell which set of input data points corresponds
to
the given Voronoi vertex or ray. In case of degeneracies, a given
Voronoi
vertex may be generated by more than n of the input data points. In
this
case, use of the allbases option
will
cause all sets of n input data points corresponding to a Voronoi
vertex to be printed. For Voronoi rays, the immediately preceding
cobasis is the cobasis of the the Voronoi vertex from which the ray
emanates.
The index followed by a * isthe
data point to drop in order to generate the ray. If the
geometric
option
is given the correspondence between Voronoi rays and Voronoi vertices
will
be produced automatically.
Example: Compute the Voronoi
diagram
of the planar point set (0,0), (2,1), (1,2), (0,4), (4,0), (4,4)
(2,4).
vor73
*6 Voronoi vertices and 5 rays
*7 input data points
Vrepresentation
begin
7 3 integer
1 0 0
1 2 1
1 1 2
1 0 4
1 4 0
1 4 4
1 2 4
end
voronoi
printcobasis
allbases
geometric
The output produced is
Vrepresentation
begin
***** 3 rational
V#1 R#0 B#1 h=0 data points 1 5 7 det=64
1 2 3/2
V#1 R#1 B#1 h=0 data points 1 5* 7 det=64
0 2 1 * 1 2 3/2
V#1 R#2 B#1 h=0 data points 1* 5 7 det=64
0 2 1 * 1 2 3/2
V#1 R#2 B#2 h=1 data points 1 2 5 det=16
1 2 3/2
V#2 R#2 B#3 h=2 data points 1 2 3 det=12
1 5/6 5/6
V#3 R#2 B#4 h=3 data points 1 3 4 det=16
1 3/2 2
V#3 R#3 B#4 h=3 data points 1 3* 4 det=16
0 1 0 * 1 3/2 2
V#4 R#3 B#5 h=2 data points 2 5 6 det=32
1 15/4 2
V#4 R#4 B#5 h=2 data points 2* 5 6 det=32
0 1 0 * 1 15/4 2
V#5 R#4 B#6 h=3 data points 2 3 6 det=20
1 27/10 27/10
V#6 R#4 B#7 h=4 data points 3 4 6 det=32
1 2 15/4
V#6 R#5 B#7 h=4 data points 3* 4 6 det=32
0 0 1 * 1 2 15/4
end
The output contains 6 Voronoi vertices :
(2, 3/2), (5/6,5/6),(3/2,2),(15/4,2),
(27/10,27/10),
(2,15/4).
The Voronoi vertex (2,3/2) appears twice in
the output with data point indices 1 5 7 and 1 2 5. This means that it
is degenerate and is defined by the set of 4 input data point in
positions
1,2,5,7 in the input file. I.e.. it is the centre of an empty
circle
through the four input data points (0,0), (2,1), 4,0),
(2,4).
The other Voronoi vertices appear once each and are defined
respectively
by the data points with indices (i.e..
position
in the input file) 1 2 3, 1 3 4, 2 5 6, 2 3 6
and
3 4 6. The Voronoi diagram has 5 rays
(2, 3/2) + (2t,t),
(2,3/2)+(2t,t),
(3/2,2)+(t,0), (15/4,2)+(t,0),
(2,15/4)+(0,t)
For example, the first ray in the output
appears:
V#1 R#1 B#1 h=0 data points 1 5* 7 det=64
0 2 1 * 1 2 3/2
This means that the ray (2t,t) emanates
from the vertex defined by data points 1 5 7, namely (2, 3/2). The
asterisk
on index 5 indicates that the ray is defined by the data points with
indices
5 and 7, namely (0,0) and (2,4).
Extreme
Point Enumeration and Redundant Inequalities
A convex hull problem that occurs frequently is to enumerate the
extreme
points (vertices) of a given set of input points. This problem is in
fact
much simpler than the problem of finding the facets of the given input
point set. It can be solved by linear programming. The dual
problem
is to remove redundant inequalities from an Hrepresentation. An
input
inequality is redundant if it can be deleted without changing the
polyhedron.
lrs
does not solve these problems , but they can be solved by cdd
using
the vertex_listing and facet_listing options.
Alternatively,
two programs that perform this task are contained in the ftp
site: redund.c and build.c . To use these
programs compile
them with the commands:
gcc O o build
build.c
gcc O o redund redund.c
To remove input points that are not vertices from a Vrepresentation or
redundant inequalities from an Hrepresentation use the command:
build < filename  redund
The resulting file can be used directly with lrs,
or even piped into lrs. In fact, lrs works best if the input is
nonredundant,
see the section Redundancy vs
Degeneracy.
Warning: The origin will not be removed from a
Vrepresentation
even if it is not a vertex.
Timing and Interrupts
lrs handles certain signals unless it is compiled with the
DOMIT_SIGNALS
option. It is possible to interrupt lrs and get the latest
cobasis,
which can be used for restarting the program (useful if the machine is
going down!)
signal
operation
USR1
print current cobasis and continue
TERM
print current cobasis and terminate
INT
(ctrlC)
ditto
HUP
ditto
lrs also provides timing information, unless compiled with the
option DOMIT_TIMES.
Error Messages and Troubleshooting
The most common error occurs from an incorrect input file
specification,
please check the section File Formats carefully.
In particular, lrs does not check the type or number of input
coefficients
specified. After the line
m n rational
you must specify exactly m*n rational
or integer coefficients. They are read in free format,
but
normally each input facet or vertex/ray is begun on a new line.
See
note
for cdd users.
The following error messages are produced by lrs. They
are
arranged in alphabetic order.
Data type must be integer of rational
lrs does not handle floating point data,
change to integer or rational input.
Digits must be at most 2295 Change
MAX_DIGITS
and recompile
The digits option was specified, but the number
of decimal digits is too large (the values shown here is for 64
bit
machines). MAX_DIGITS (default 255) is the maximum number of
array
locations used for extended precision arithmetic. This value should be
increased and lrs recompiled.
Input Polyhedron does not have full dimension
If input is a cone, change to
Hrepresentation,
or add the origin 1 0 0 ... 0
The input polyhedron does not have dimension
n1. Either there is a mistake in the input, or it must be projected
onto
a full dimensional subspace. cdd
has a function for doing this. The second message only appears for
Vrepresentations
 note that at least one vertex must be supplied, or else the problem
can
be run as a Hrepresentation.
Invalid Cobasis  does not have correct
rank
An attempt to restart from an invalid cobasis
has been made. Check that the indices are entered exactly as they
appear
in the previous aborted run.
Maximize/minimize only valid for
Hrepresentation
LP operations can only be performed on
Hrepresentations.
No begin line
No data in file
No feasible solution
The input is an Hrepresentation of an
infeasible
system.
Starting cobasis indices must be distinct and
in range 1 .. m
The startingcobasis option has been used, but
the indices supplied were not valid: i.e. distinct numbers between 1..m.
Trying to restart from infeasible dictionary
An attempt to restart from an invalid cobasis
has been made. Check that the indices are entered exactly in the
order appear in the previous aborted run.
Hints
and Comments
H vs V
representation
lrs is programmed to manipulate
Hrepresentations
directly. A file presented as a Vrepresentation is processed by
lifting
it to a cone in one higher dimension, which is treated internally as a
Hrepresentation. If the input file is a polytope which contains the
origin,
then the user has two options. Submit it as a Vrepresentation and have
it processed as just described, or submit it as a Hrepresentation, and
interpret the output as a list of facet inequalities rather than
"vertices".
Since this will not be lifted, it will be processed in a different way
by lrs. Sometimes a degenerate Vrepresentation may run more
quickly
as a Hrepresentation, and sometimes more slowly. To decide which
representation
to use for a large problem, the user can run the estimatesoption
and choose the representation with fewest estimated bases.
Redundancy vs Degeneracy
For an Hrepresentation, an input is redundant if some inequality can
be
deleted without changing the polyhedron. It is degenerate if (in d
dimensions)
at least one vertex lies on d+1 or more facets. Similarly in a
Vrepresentation
an input is redundant if some input point is not a vertex of the convex
hull. It is degenerate if some facet contains d+1 or more input
points.
Degeneracy causes pivot or triangulation based methods such as
lrs to run slowly. Redundancy is one cause of degeneracy,
but
it can be avoided by preprocessing the input files. See section Extreme
Point Enumeration and Redundant Inequalities for instructions on
how
to do this. This preprocessing is unnecessary if it is known that the
input is nonredundant.
Even with redundant input removed a polyhedron may be highly
degenerate.
In directory ine/metric there
are many highly degenerate combinatorial polytopes. These are difficult
problems for all vertex enumeration/convex hull programs that use
pivoting,
such as lrs. For example, the file ccc7.ine is a
cone
with 63 facets in 21 dimensions. It has 38,780 extreme rays, but
computing
these required the evaluation of 247,271,659 bases!
Memory considerations
The strong point of lrs is that it does
not
save the output produced, so in theory it cannot run out of
memory.
With cache size one all memory is allocated at the beginning, so if lrs
starts running it will not run out of memory. It is possible however
that
the number of digits required to do the calculations exceeds the amount
specified on the digits
option, or the default. In practice, this problem will also arise early
in the computation. In any case, a message is printed and the
calculation
can be restarted. In order to improve performance, some dictionaries
should
be cached. The default of 10 can be overridden by the cacheoption.
If the dictionary is in the cache it does not need to be recomputed
when
backtracking, reducing processing time by about 40%. Since the
cache
is allocated dynamically, a cache size that is too large can
potentially
use up large ammounts of machine memory.
Geometric Rays
A minimum Vrepresentation of a polyhedron is a minimum set of vertices
and rays such that each point in the polyhedron can be expressed as a
convex
combination of vertices plus a nonnegative combination of rays. For
the
cube, if we delete the inequality
x_{3} <= 1, i.e.. the line 1 0 0 1 from file cube.ine,
we get the output:
Vrepresentation
***** 4 rational
1 1 1 1
0 0 0 1
1 1 1 1
1 1 1 1
1 1 1 1
end
indicating the polyhedron is the convex combination of 4 vertices and
1 ray. With the geometric option,
we
get the output:
Vrepresentation
begin
***** 4 rational
1 1 1 1
0 0 0 1 * 1 1 1 1
1 1 1 1
0 0 0 1 * 1 1 1 1
1 1 1 1
0 0 0 1 * 1 1 1 1
1 1 1 1
0 0 0 1 * 1 1 1 1
end
This indicates that geometrically, the polyhedron has 4 parallel
extreme
rays (0,0,t) , one incident to each vertex. With the geometric
option, all rays will be printed. Without the option, lrs tries
to print each ray once, but in some cases duplicates will remain,
see
subsection Output Duplication.
Output Duplication
For degenerate inputs, pivot based methods such as lrs may
generate
the same output vertex/ray/facet many times. Unless the allbases
option
is specified, lrs makes checks in order to remove
duplicates.
An output is only printed when it occurs with a lexicographically
minimum
basis. This removes all duplicate vertices, but rays/facets may still
be
output more than once. This is due to the fact that duplicate geometric
rays cannot always be detected. A warning message is produced when
duplicates
may occur in the output. They can be removed using the program buffer.c.
Two important types of input never produce duplicate output: polytopes
(i.e. bounded polyhedra) and cones (i.e. polyhedra where the origin is
the only vertex).
Acknowledgements and
References
I would like to thank many people for helping with this implementation
project. Komei Fukuda encouraged me from the start, collaborated in
designing
the file formats, and provided many suggestions for improving the code.
David Bremner implemented memory allocation, caching and signals. Jerry
Quinn coded the integer divide routine. Bug reports were provided by
many
users, for which I thank them. In particular Gerardo Garbulsky's
extensive
use of earlier versions suggested many refinements, Ambros Marzetta
demonstrated
the importance of caching and Andreas Enge helped debug the volume
computation.
D. Avis, lrs: A Revised Implementation of the Reverse Search Vertex
Enumeration Algorithm, ftp://mutt.cs.mcgill.ca/pub/doc/avis/Av98a.ps.gz
May 1998.
D. Avis, "Computational Experience with the Reverse Search Vertex
Enumeration
Algorithm," Optimization Methods and Software, (1998 (to appear)).
ftp://mutt.cs.mcgill.ca/pub/doc/avis/Av98b.ps.gz
D. Avis, D. Bremner, and R. Seidel, "How Good are Convex Hull
Algorithms?,"
Computational Geometry: Theory and Applications, Vol
7,pp.265301(1997).
ftp://mutt.cs.mcgill.ca/pub/doc/avis/ABS96a.ps.gz
D. Avis and L. Devroye, "Estimating the Number of Vertices of a
Polyhedron,"
pp. 179190 in Snapshots of Computational and Discrete Geometry, ed. D.
Avis and P. Bose, School of Computer Science, McGill University (1994).
ftp://mutt.cs.mcgill.ca/pub/doc/avis/AD94a.ps.gz
D. Avis and K. Fukuda, "A Pivoting Algorithm for Convex Hulls and
Vertex
Enumeration of Arrangements and Polyhedra," Discrete and Computational
Geometry,
Vol. 8, pp. 295313 (1992). ftp://mutt.cs.mcgill.ca/pub/doc/avis/AF92b.ps.gz
D. Bremner, K. Fukuda and A. Marzetta, PrimalDual Methods for
Vertex
and Facet Enumeration, 13th ACM
Symposium on Computational Geometry SCG 1997, 4956.