A new feature of the basic package is the nonnegative option that speeds up the solution of problems with H-representation:
b+Ax >= 0, x>=0Note: The origin must be a vertex of the feasible region for Version 4.1.
This distribution also comes with three arithmetic lpackages: lrsmp, lrslong and lrsgmp . The library lrsmp is essentially the same extended precision package included in earlier distributions. lrslong is an implementation using long integer arithmetic, which is considerably faster, but does no overflow checking. lrsgmp is an interface to GNU MP which must be installed first. Binaries are produced for all arithmetic packages using the distributed make file.
Most of the functions required for lrs and redund are included in the library lrslib. This is compiled with either of the arithmetic packages. One of the purposes of supplying a library is to allow simple customization of the reverse search procedure. The program lrs.c is the reverse search driver, and supplies each output vector to the user. It can be customized to prune the search according to various criteria, eg., if the value of some objective function falls below some value, or if an integer vector is produced etc.
The installation procedure has been simplified, and the package is distributed as a compressed tar file. Included is a makefile for various configurations and some typical input files. Binaries are also included for some platforms.
There are new options: incidence ,
which lists all inequalities (resp. vertices/rays) which are
incident with the current output vertex/ray (resp. facet). and truncate which prunes the search tree
everytime a vertex different from the starting vertex is reached.
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 . 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.
Another program 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. A package for volume computation called Vinci has been developped by Enge. A comprehensive general source of related infomation are Erickson's Computational Geometry Pages.
In version 4.0, polyhedra handled by lrs need not be full dimensional and may contain input linearities and redundant columns . lrs accepts either integer or rational input, and produces integer or rational output. All computations are done exactly using either extended precision arithmetic or fixed long integer arithmetic. In the latter case no overflow checking is performed, and the user is advised to check results using the extended precision version. Since it is a pivot based method, lrs 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:
These programs 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/redund were helpful.
The output should contain (along with other comment lines beginning with a "*")
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:
{list of inequalities }
end
{options}
name is a user supplied name for the
polytope. If the line H-representation 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. 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
a0 + a1 x1 + ... + 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.
For example, the square centred at the origin with side length
two has inequalities
1 + x1 >= 0 1+ x2 >=0 1-x 1 >= 0 1-x2 >=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
{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 v0 v 1 ...
vn-1
Each ray is given in the form
0 r0 r 1 ... rn-1
where r0 r 1 ... r n-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.
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 x1 >= 0 and x2 >= 0 :
quadrant
*positive quadrant
H-representation
begin
2 3 rational
0 1 0
0 0 1
end
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//
This option automatically switches on printcobasis , so see below for a description of this option first.#incidence
Can be used with printcobasis n. (Ver 4.2b)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. Eg:
V#1 R#0 B#1 h=0 facets 12 14 15 16 : 9 10 11 13 I#8 det= 8
1 0 0 0 1
The vertex 0 0 0 1 satisfies 8 input inequalities as equations, as indicated by I#8 : those with indices 12,14,15,16 are in the cobasis, and those with indices 9, 10, 11, 13 are in the basis. For a ray:
V#1 R#5 B#1 h=0 facets 5 9* 10 11 12 13 : 2 3 4 I#8 det= 8
0 1 1 0 0 1 1
Here the ray 1 1 0 0 1 1 lies on 8 inequalities, with indices 5 10 11 12 13 in basis and 2 3 4 in cobasis. The starred index 9* indicates that the ray is terminated by the input inequality 9. This inequality is in the cobasis and defines the vertex from which the ray starts.For input V-representation, indices of all input vertices/rays that lie on the facet that is about to be output:
F#5 B#3 h=2 vertices/rays 7 8* 11 13 15 : 1 3 5 9 I#8 det= 16
1 -1 0 0 0
The facet generated by inequality x1 <= 1 contains 8 input vertices, as indicated by I#8: those with indices 7,11,13,15 are in the cobasis, and those with indices 1 3 5 9 are in the basis.The starred index 8* indicates 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.
The same as printcobasis. Included for compatability with cdd.linearity k i1 i2 i ... ik
The input contains k linearities in rows i1 i2 i ... ik of the input file are equations. See Linearities.maxdepth k
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
F#5 B#4 h=3 vertices/rays 2 3 4
5* det= 8
1 0 0 -1
enter
restart 5 4 3 2 3 4 5
Note that if some cobasic index is
followed by a "*", then the index only, without the "*",
is included in the restart line.
Caution: When restarting, output from the restart
dictionary may be duplicated, and the final totals of number
of vertices/rays/facets may reflect this.
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. See here for a description of how to use this option.verbose
Print slightly more detailed information about the run.volume // V-representation only //
lrsgmp An
interface to GNU MP which must be installed first.
lrslib also has two build in packages that do not need separate
installation, and can be build by % make allmp
lrsmp Extended precision arithmetic
lrslong Fixed
length long integer arithmetic. No
overflow checking
It is about 5-10 times faster than lrsmp and 4-5 times faster than
lrsgmp.
The standard make gives binaries lrs/redund
with lrsgmp, and lrs1/redund1
with lrslong.
Since no overflow checking is performed for lrs1/redund1
results should be confirmed by using one of the other
arithmetic packages.
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
*Estimated total running time=0.0 secs
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=6 bases=7 volume=8.88889
*Total number of tree
nodes evaluated: 10
*Estimated total
running time=0.0 secs
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.
An unbiased estimate of the volume of the polytope is also
given. The estimate was formed by evaluating 7 tree nodes.
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.
The command line argument is an integer n which will be the seed and overrides a seed given as an option.
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.
lrsnash computes all Nash equilibria (NE) for a two person noncooperative game are computed using two interleaved reverse search vertex enumeration steps.
The input for the problem are two m by n matrices A,B of integers or rationals. The first player is the row player, the second is the column player.
If row i and column j are played, player 1 receives Ai,j and player 2 receives Bi,j.
and one of the options maximize or minize:
maximize a0 a1 ... an-1 // H-representation only //
To print the dictionary at a few key points also include the option:
verbose
New
in
V4.2. Dual variables are now printed at
termination. If the linearity option is used, only a partial list
of dual variables will be given.
Dual
variable
yi refers to inequality number i in the input.
volume // V-representation only //
will cause the volume to be computed. For input cube.ext, the
output is:
*Volume=8
The triangulation can be output by adding also the option verbose.
This would give the output:
F#0 B#1
h=0 vertices/rays 4 6 7 8 I#8 det= 8
1
1
0 0
1
0
1 0
1
0
0 1
F#3 B#2
h=1 vertices/rays 4 5 6 7 I#8 det= 8
F#3 B#3
h=2 vertices/rays 3 4 5 7 I#8 det= 8
1
-1 0 0
F#4 B#4
h=3 vertices/rays 2 3 4 5 I#8 det= 8
1
0
0 -1
F#5 B#5
h=4 vertices/rays 1 2 3 5 I#8 det= 8
F#5 B#6
h=2 vertices/rays 2 4 5 6 I#8 det= 8
1
0 -1 0
end
*Sum of
det(B)= 48
*Volume= 8
Each of the 6 bases corresponds to a simplex.
The first simplex is composed of vertices 4 6 7 8, second simplex
is 4 5 6 7, etc.
If the volume option is applied to an H-representation, the results are not predictable. If the option is applied to a V-representation of a polytope that is not full dimensional, the volume of a projected polytope is computed. The projection used is to the lexicographically smallest coordinate subspace, see Avis, Fukuda, Picozzi (2002).
For polytopes given by a H-representation, it will first be
necessary to compute the V-representation.
p1 , p2 , ...., p n-1 -> (p1 2 + p22 + ... + pn-12 ) - 2 p1 x 1 - 2 p2 x2 - .... - 2 p n-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 - place immediately after end statement //
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).
To remove input points that are not vertices from a V-representation or redundant inequalities from an H-representation use the command:
Note: Versions of redund prior to this release failed to remove redundancy from the starting basis.
linearity k i1 i2
i ... ik
The input file contains k linearities. If the input is a H-representation, the rows i1 i2 i ... ik of the input file are equations. For a V-representation, the rows with these indices should begin with zero in column one, and will be interpreted as lines rather than rays. Linearities defined on the input vertices of a V-representation are not defined, but the program will accept them and produce some output. Each of the indice ik must be a distinct number between 1 and m. With an H-representation, linearities are useful for enumeration of vertices on a facet or lower dimensional subspace. For example the file:cube_ridge
*cube of side 2 centred at the origin
H-representation
linearity 2 1 5
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
endcauses vertices to be enumerated on the ridge which is the intersection of the two facets
x1 = -1 and x2 = 1
so the output is the pair of vertices
cube_ridge
*Input linearity in row(s) 1 5
V-representation
begin
2 4 rational
1 -1 1 1
1 -1 1 -1
endSpecifying linearities in this way will often produce redundancy , especially if the dimension of the problem is reduced considerably. As a preprocessing step, it is useful to apply to remove any redundancy by redund. In the case of the above problem the output produced by redund is:
cube
*Input linearity in row(s) 1 5
*row 2 was redundant and removed
*row 4 was redundant and removed
H-representation
linearity 2 1 2
begin
4 4 rational
1 1 0 0
1 0 -1 0
1 0 0 1
1 0 0 -1and two redundant halfspaces were removed.
Redundant columns are closely related to linearities. If we examine the V-representation of cube_ridge above we can see that it is just a line segment in 3 dimensional space. Further, columns 2 and 3 are multiples of column 1. If lrs is applied to this file, the column redundancies give rise to two linearities, so the output will appear as the H-representation given above: geometrically the intersection of two planes (the linearities) with two half-planes (defining the endpoints of the line segment).
In general, the representation of the linearity space is not unique, however the one produced by lrs should be the same as that produced by cdd.
The following error messages are produced by lrs . They are arranged in alphabetic order.
Cannot find linearity in the basis
The linearity option was specified but a basis cannot be created. Check the linearity indices are all less than n-1 and are disitinct.
Data type must be integer of rational
Usually means that end of file was reached before enough input data was read.
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!
For degenerate inputs, pivot based methods for vertex/ray enumeration such as lrs may generate the same output ray many times. An output is only printed when it occurs with a lexicographically minimum basis. This removes all duplicate vertices, but rays may still be output more than once. This is due to the fact that duplicate geometric rays cannot always be detected without storing the output. Since V-representations are automatically lifted to a higher dimension, this will not happen for facet enumeration. Unless the allbases option is specified, lrs makes checks in order to remove duplicates. 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).
D. Avis, lrs: A Revised Implementation of the Reverse Search
Vertex Enumeration Algorithm,
http://cgm.cs.mcgill.ca/~avis/doc/avis/Av98a.ps
In: Polytopes - Combinatorics and Computation, Ed. G.
Kalai and G. Ziegler, Birkhauser-Verlag (2000) 177-198.
D. Avis, "Computational Experience with the Reverse Search Vertex Enumeration Algorithm," Optimization Methods and Software, (1998 (to appear)). http://cgm.cs.mcgill.ca/~avis/doc/avis/Av98b.ps
D. Avis, D. Bremner, and R. Seidel, "How Good are Convex Hull Algorithms?," Computational Geometry: Theory and Applications, Vol 7,pp.265-301(1997). http://cgm.cs.mcgill.ca/~avis/doc/avis/ABS96a.ps
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).
http://cgm.cs.mcgill.ca/~avis/doc/avis/AD94a.ps
In: Information Processing Letters, (2000) V. 73, pp.
137-143.
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). http://cgm.cs.mcgill.ca/~avis/doc/avis/AF92b.ps
D. Avis, K. Fukuda and S. Picozzi, "On Canonical Representations of Convex Polyhedra", Mathematical Software, ICMS 2002, Ed. A. Cohen, X-S Gao, N. Takayama, World Scientific, pp.350-360 (2002) http://cgm.cs.mcgill.ca/~avis/doc/avis/AFP02a.psD. Avis, G. Rosenberg, R. Savani, B. von Stengel, "Enumeration of Nash Equilibria for Two-Player Games", Economic Theory 42(2009) 9-37 pdf
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. http://www.cs.unb.ca/profs/bremner/pd/