Print out cryptic but detailed trace, dictionaries etc. starting at #B=startingbasis and ending at #B=endingbasis. debug 0 0 gives a complete trace.

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.

Estimate the output size. Used in conjunction with maxdepth - see Estimation.

With this option, each ray is printed together with the vertex with which it is incident. They output has the form:

   0   r₀   r ₁ ...   r_n-1* 1   v₀   v ₁ ...   v_n-1

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 .

This option automatically switches on printcobasis , so see below for a description of this option first.
Can be used with printcobasis n. (Ver 4.2b)

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 x₁ <= 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.

The input contains k linearities in rows i₁ i₂ i ... i_k of the input file are equations. See Linearities.

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.

 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.

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                                  

Every k'th cobasis is printed. If k is omitted, the cobasis is printed for each vertex/ray/facet that is output. For a long run it is useful to print the cobasis occasionally so that the program can be restarted if necessary.
H-representation:  If the input is an H-representation the cobasis is a list the indices of the inequalities from the input file that define the current vertex or ray. For example, with input cube.ine a typical output is:
V#5 R#0 B#5 h=1 facets  3 4 5 I#3 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. I#3 means that this vertex is incident with 3 input inequalities, ie. it is non-degenerate. See option  incidence above for more information.
For rays, a cobasis is also printed. In this case the cobasis is the cobasis of the vertex from which the ray emanates. One of the indices is starred, this indicates the inequality to be dropped from the cobasis to define the ray. For example the output:
V#1 R#6 B#4 h=1 facets  2 4* 5 7 I#3 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 I#3 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:
F#5 B#4 h=3 vertices/rays  2 3 4 5* I#3 det= 8
 1  0  0 -1
There have been 5 facets output up to this point, and 4 bases have been computed. This facet is defined by the vertices in positions 2,3,4 in the input file. The additional cobasis index 5* appears because a V-representation is lifted to one higher dimension before processing, and this index fills out the cobasis. I#3 means that this facet is incident with 3 input vertices/rays, ie. it is non-degenerate. See option incidence above for more information.
To initiate lrs from this facet all 4 indices must be given in this order (omit the *), eg.
startingcobasis 2 3 4 5
Similarly, all 4 indices must be given in order to restart from this facet:
restart 5 4 3 2 3 4 5

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.
For H-representation inputs, if the number of integer vertices is known then the integervertices n option may also be included. This will ensure that the final integer vertex count is correct.

To restart from the following cobasis when 2 integer vertices have already been found:

V#5 R#0 B#5 h=1 facets  3 4 5 det=1
enter:
restart 5 0 5 1 3 4 5
integervertices 2

For a V-representation input:


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.

This allows the user to specify a known cobasis for beginning the reverse search. i₁ i₂ 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, 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

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.

Print slightly more detailed information about the run.

Compute volume - see section Volume Computation.

Compute Voronoi diagram - see section Voronoi Diagrams.

Arithmetic packages     (Major update in v.7.0)          

  lrslong   Fixed length long integer arithmetic. 64-bit and 128-bit(when the compiler supports it) with overflow checking
  lrsgmp   An interface to GNU MP  which must be installed first from https://gmplib.org/.

If your C compiler does not support 128-bit integers you should install lrs/redund with '% make lrs64' .

Overflow checking is conservative to improve performance:
eg. with 64 bit arithmetic, a*b triggers overflow if either a or b is at least 2^31, and a+b triggers an overflow if either a or b is at least 2^62.
% make single

produces the binaries :

 lrs1/redund1/lrsnash1                        fixed 64 bit, stop on overflow                           
 lrs2/redund2/lrsnash2                        fixed 128 bit, stop on overflow
 lrsgmp/redundgmp/lrsnashgmp      gmp extended precison arithmetic
  
and if the FLINT package has been installed ( available at  http://www.flintlib.org/  )    

 lrsflint/redundflint                                FLINT multiple precison arithmetic
                                                                    

 lrs1/lrs2 produce a restart file that can be used instead of redoing the whole run from the beginning

If you remove the flag -DSAFE in the makefile then (mp)lrs1 and (mp)lrs2 will not  do overflow checking and will run about 10% faster.
However, if overflow occurs the results are unpredictable: caveat emptor!

% make singlemplrs             produces the binaries :

  mplrs1  64 bit integers with overflow checking. Terminates when overflow condition is detected.
  mplrs2 128 bit integers with overflow checking. Terminates when overflow condition is detected.
  mplrsgmp(default mplrs) use only gmp extended precison arithmetic (same as lrs in lrslib-062)

(mp)lrs1 runs 3-5 times faster than (mp)lrs on highly combinatorial polytopes.
(mp)lrsflint performed similarly to (mp)lrsgmp even on combinatorial polytopes.
Experimental results will be reported at a later date.

In this case 64 bit arithmetic was sufficient to compute all vertices.

---

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:

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

Using the estimator:  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. 
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.

mplrs: installation and usage

Fourier Elimination (Due to several bug reports, this program should not be used. Caveat emptor!)

lrsnash installation and usage (Nash equilibria for 2-person matrix games)                                          

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 A_i,j and player 2 receives B_i,j.

  Linear Programming             

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

             and one of the options maximize or minize:

maximize a₀ a₁ ... a_n-1                                           // H-representation  only //

 simply maximizes the function  a₀ + a₁ x ₁ + ... + 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:

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 y_i refers to inequality number i in the input.

Volume and triangulation

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.

Voronoi diagrams

p₁  , p₂  , ...., p _n-1     ->    (p₁ ²  +   p₂² +  ...   +  p_n-1²  ) - 2 p₁  x ₁  - 2 p₂  x₂ - .... - 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 - 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).
 
 

---

  redund: extreme point enumeration and eliminating redundant Inequalities

To remove input points that are not vertices from a V-representation or redundant inequalities from an H-representation use the command:

% redund filename

Linearities   

linearity  k  i₁ i₂ i ... i_k

The input file contains k linearities. If the input is a H-representation, the rows i₁ i₂ i ... i_k 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 i_k 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
end

causes vertices to be enumerated on the ridge which is the intersection of the two facets

x₁ = -1   and   x₂ = 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
end

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

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

Timing and interrupts

Error messages and troubleshooting

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

lrs does not handle floating point data, change to integer or rational input.

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.

Usually means that end of file was reached before enough input data was read.

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.

LP operations can only be performed on H-representations.

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

The input file is incorrect, please check File Formats.

The input is an H-representation of an infeasible system.

The startingcobasis option has been used, but the indices supplied were not valid: i.e. distinct numbers between 1..m.

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.

mplrs/plrs error messages

Error: lponly option not supported - use lrs!         (The simplex method does not run in parallel!)

---

Hints and comments

H- vs V- representation

Redundancy vs Degeneracy

Even with redundant input removed a polyhedron may be highly degenerate. In distribution 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 cp6.ine is a polytope with 368 facets in  16 dimensions. It has 32 vertices, but computing these required the evaluation of 4,844,923,002 bases!(see Avis-Jordan, 2017)

Memory considerations

Geometric Rays

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

---

Acknowledgements and References

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