November 30, 1998                                          Copyright(C) 1998

  David Avis          avis@cs.mcgill.ca       http://www.cs.mcgill.ca/~avis

  • 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 (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'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 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:

    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

    File Formats

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

    allbases cache n digits n                // placed before the begin statement// estimates k geometric                 // H-representation  or voronoi option only //               This indicates ray  0   r0   r 1 ...   rn-1is incident with vertex  1   v0   v 1 ...   vn-1.  For the quadrant, the output is: maxdepth k maximize                                              // H-representation  only //
    minimize  mindepth k printcobasis  k restart  V# R# B# depth {facet #s or vertex/ray #s} startingcobasis i1 i2 i ... in-1 volume                                              // V-representation  only // voronoi                                              // V-representation  only //

    Estimation

    maxdepth d
    estimates k seed n lrs n < filename
     

     Linear Programming

    maximize a0 a1 ... an-1                                           // H-representation  only // minimize a0 a1 ... an-1                                             // H-representation  only //

    Volume Computation

    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.

    Voronoi Diagrams

    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:

    p1  , p2  , ...., pn-1     ->    (p1 2  +   p22 +  ...   +  pn-12  ) - 2 p1  x1  - 2 p2  x2 - .... - 2  pn-1 xn -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 * 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).
    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: To remove input points that are not vertices from a V-representation or redundant inequalities from an H-representation use the command: 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.

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

    Digits must be at most 2295  Change MAX_DIGITS and recompile Input Polyhedron does not have full dimension
    If input is a cone, change to H-representation, or add the origin 1 0 0 ... 0 Invalid Co-basis - does not have correct rank Maximize/minimize only valid for H-representation No begin line No data in file No feasible solution Starting cobasis indices must be distinct and in range 1 .. m Trying to restart from infeasible dictionary

    Hints and Comments

    H- vs V- representation

     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 estimatesoption and choose the representation with fewest estimated bases.
     

    Redundancy vs Degeneracy

    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!

    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 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
    x3 <= 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, 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.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.