Introduction

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*.
*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
self-dual, 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's
*cdd* package, which performs the same transformations using a
version of the *double description method*. *cdd* can also
be used in conjunction with *lrs *as a pre-processor for projections
to subspaces, or as a post processor for computing the entire face lattice.
Another program using the same file format is the primal-dual method *pd,*
developed by Bremner,
Fukuda and Marzetta(1997). It is essentially dual to *lrs,*
and is very efficient for computing H-representations of simple polyhedra,
and V-representations of simplicial polyhedra. It will compute the volume
of a polytope given by an H-representation. 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.. H-representations
of non-simple polyhedra, and V-representations of non-simplicial 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 V-representation
- Solving LP problems for a polyhedron given by a H-representation
- 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.2.c, buffer.c, cube.ine, cube.ext
- Compile using the command
- Compile
*buffer.c*using the command - Test the program by typing:

**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

**gcc -O -o buffer buffer.c**

**lrs < cube.ine**

This will convert the H-representation of a cube given cube by 6 the
six inequalities -1 <= x_{i }<= 1 , i=1,2,3 given by the
input:

**cube**

***cube of side 2 centred at the origin**

**H-representation**

**begin**

**6 4 rational**

**1 1 0 0**

**1 0 1 0**

**1 0 0 1**

**1 -1 0 0**

**1 0 -1 0**

**1 0 0 -1**

**end**

The output should contain (along with other comment lines beginning with a "*")

**cube**

**V-representation**

**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 co-ordinate +/- 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:

**lrs < cube.ext**

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:

**buffer maxline maxbuffer**

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*:

**lrs < filename | buffer**

File Formats

Example files can be found in the directories ine and ext at the ftp site (ftp://mutt.cs.mcgill.ca/pub/C).

The input for* lrs* is a H- or V- representation of a polytope.
These files have the following formats:

H-representation

begin

m n rational

{list of inequalities }

end

{options)

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_{n-1}
x_{n-1} >= 0.

This inequality is input as the line

a_{0 }a_{1 }... a_{n-1}

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
1-x_{1 }>= 0
1-x_{2 }>=0

and would be represented by the input file

**square**

***centred square of side 2**

**H-representation**

**begin**

**4 3 rational**

**1 1 0**

**1 0 1**

**1 -1 0**

**1 0 -1**

**end**

V-representation

begin

m n rational

{list of vertices and extreme rays}

end

{options)

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_{n-1}

Each ray is given in the form

0 r_{0 } r _{1 }...
r_{n-1}

where r_{0 } r _{1 }... r_{n-1}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**

**V-representation**

**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**

**V-representation**

**begin**

**3 3 rational**

**1 0 0**

**0 1 0**

**0 0 1**

**end**

Its H-representation contains the inequalities x_{1 }>= 0
and x_{2} >= 0 :

**quadrant**

***positive quadrant**

**H-representation**

**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 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.

*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
lex-min 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 **
// H-representation 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_{n-1}* 1 v_{0 } v _{1 }...
v_{n-1}

This indicates ray 0 r_{0 } r _{1
}... r_{n-1}is incident with vertex 1
v_{0 } v _{1 }... v_{n-1}.
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
non-negative integer, and this option is used for estimates - see Estimation.

**Note**: For H-representations, rays at depth
k will not be reported. For V-representations, facets at depth k will not
be reported.

**maximize **
// H-representation only //

**minimize**

**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.

**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.

**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. 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 lex-min) 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.

**V-representation**: If the input is a V-representation, 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_{n-1}**

This allows the user to specify a known cobasis
for beginning the reverse search. **i _{1
}i_{2 }i ... i_{n-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,

**volume **
// V-representation only //

Compute volume - see section Volume Computation.

**voronoi **
// V-representation only //

Compute Voronoi diagram - see section Voronoi Diagrams.

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 **estimates**
option:

**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.

**H-representation: **If the input is an H-representation, the program
gives an unbiased estimate of the number of vertices and rays in
the V-representation, and the total number of bases that will be
computed by *lrs. *For the H-representation *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 V-representation 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.

**V-representation:** If the input is
a V-representation, the program gives an unbiased estimate of the number
of facets in the H-representation, and the total number of bases that *lrs*
will compute. For V-representation *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 H-representation 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 V-representation 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 V-representation
can be processed as an H-representation and vice-versa (this is an application
of duality). Hence facet estimates for a V-representation can also be obtained
by running the problem as an H-representation 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 H-representation , **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
H-representation of the cube. Similarly, estimates for an input
H-representation of a polytope containing the origin may be obtained by
processing the file as a V-representation. The output will be essentially
the same, but the number of bases computed may be very different, see the
subsection H- vs V-representation.
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 H-representations,
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.

*lrs* can be used to solve linear programming problems in rational
arithmetic when the input is an H-representation. The option:

**maximize a _{0}
a_{1 }... a_{n-1}**
// H-representation only //

simply maximizes the function a_{0} + a_{1 }x_{1
}+ ... + a_{n-1} x_{n-1}

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_{n-1}**
// H-representation only //

*lrs* can be used to compute the volume of a polytope given as
a V-representation. The option

**volume **
// V-representation 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 H-representation, the results are not predictable.

For polytopes given by a H-representation, it will first be necessary to
compute the V-representation. Alternatively the program *pd *
may be used, which works directly with the H-representation.

*lrs* can be used the compute the V-vertices of a Voronoi diagram
of a set of data points in n-1 dimensional space. To do this we use a standard
lifting procedure (see, e.g., Edelsbrunner, "Algorithms in Combinatorial
Geometry," pp 296-297) . Each point is mapped to a half space tangent
to the parabaloid in n dimensions, by the mapping:

p_{1 } , p_{2 } , ...., p_{n-1}
-> (p_{1 }^{2 }+
p_{2}^{2 }+ ... + p_{n-1}^{2 }
) - 2 p_{1} x_{1 } - 2 p_{2 } x_{2
}- .... - 2 p_{n-1 }x_{n -1 } + x _{n}>=
0

*lrs* is applied to the H-representation so created. This
transformation is performed automatically for a V-representation if the

**voronoi
**// V-representation 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 V-representation.

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 *** **is**
**the 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).

**vor7-3**

***6 Voronoi vertices and 5 rays**

***7 input data points**

**V-representation**

**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

**V-representation**

**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 H-representation. 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 V-representation or redundant inequalities from an H-representation 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 non-redundant, see the section Redundancy vs Degeneracy.

**Warning:** The origin will not be removed from a V-representation
even if it is not a vertex.

*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 (ctrl-C)
ditto

HUP
ditto

*lrs* also provides timing information, unless compiled with the option
-DOMIT_TIMES.

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 H-representation,
or add the origin 1 0 0 ... 0**

The input polyhedron does not have dimension n-1.
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 V-representations
- note that at least one vertex must be supplied, or else the problem can
be run as a H-representation.

**Invalid Co-bas**is - 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 H-representation**

LP operations can only be performed on H-representations.

**No begin line**

Input file does not contain a begin line. See File Formats.

**No data in file**

The input file is incorrect, please check File Formats.

**No feasible solution**

The input is an H-representation 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

*lrs* is programmed to manipulate H-representations
directly. A file presented as a V-representation is processed by lifting
it to a cone in one higher dimension, which is treated internally as a
H-representation. If the input file is a polytope which contains the origin,
then the user has two options. Submit it as a V-representation and have
it processed as just described, or submit it as a H-representation, 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 V-representation may run more quickly
as a H-representation, and sometimes more slowly. To decide which representation
to use for a large problem, the user can run the **estimates**
option and choose the representation with
fewest estimated bases.

For an H-representation, 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 V-representation
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 pre-processing the input files. See section Extreme
Point Enumeration and Redundant Inequalities for instructions on how
to do this. This pre-processing is unnecessary if it is known that the
input is non-redundant.

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!

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 **cache**
option. 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.

A minimum V-representation 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 non-negative 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:

**V-representation**

******* 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:

**V-representation**

**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, "A C Implementation of the Reverse Search Vertex Enumeration Algorithm," in RIMS Kokyuroku 872, ed. H. Imai, Kyoto University (May 1994). ftp://mutt.cs.mcgill.ca/pub/doc/avis/Av94a.ps.gz

D. Avis, D. Bremner, and R. Seidel, "How Good are Convex Hull Algorithms?," Computational Geometry: Theory and Applications, Vol 7,pp.265-301(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. 179-190 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. 295-313 (1992). ftp://mutt.cs.mcgill.ca/pub/doc/avis/AF92b.ps.gz

D. Bremner, K. Fukuda and A. Marzetta, Primal-Dual Methods for Vertex
and Facet Enumeration, 13th ACM

Symposium on Computational Geometry SCG 1997, 49-56.