Estimating the number of vertices of a polyhedron

Given a polyhedron P by a list of inequalities we develop unbiased estimate s of the number of vertices and bases of P. The estimates are based on appl ying tree estimation methods to the reverse search technique. The time to g enerate an unbiased estimate is essentially bounded by the time taken to so lve a linear program on P with the simplex method. Computational experience is reported. The method can be applied to estimate the output size of othe r enumeration problems solvable by reverse search. (C) 2000 Elsevier Scienc e B.V. All rights reserved.