Vertex enumeration and counting for certain classes of polyhedra

Vertex enumeration (VE) algorithms explore the problem of listing some or all solutions that lie at corners of a convex polyhedron defined by a set of linear inequalities. Many algorithms have been developed for general polytopes. The most successful of these, from both an empirical and theoretical viewpoint, are based on pivoting. Dyer [24] gives an algorithm for simple polytopes which runs in time O (mn^2) per vertex. In this thesis we concentrate on the VE problem for certain special classes of polyhedron. We also address the problem of (approximately) counting the vertices without listing them. Pivoting algorithms rely on the correspondence between vertices and feasible bases and are consequently inefficient in the presence of a high degree of degeneracy such as frequently occurs in network polyhedra. Provan [79] gives a high-level description of a VE algorithm for such polyhedra which has running time that is quadratic in the number of vertices. W e describe an implementation of Provan's algorithm, present some computational results on transportation and assignment polytopes and discuss some practical difficulties with the algorithm. We then present an algorithmic description of a VE method via the dual Fourier-Motzkin (F-M) elimination method. One of the difficulties with F-M is that the number of constraints introduced in eliminating variables grows exponentially; we show that, for linear inequality systems with at most two variables per constraint, denoted LI(2), the growth is exponential in the number of variables but linear in the number of constraints. We go on to prove results which characterize the basis structure for LI(2) and dual LI(2) systems and hence develop a new pivoting algorithm for enumerating vertices of polyhedra associated with dual LI(2) systems. Counting the vertices of general polyhedra is #P-complete [24] and thus approximate counting procedures are of interest. In particular, some fpras for counting vertices of polyhedra associated with 0-1 Permanent, Down Sets, Independent Sets, 0-1 Knapsack Problems, 2 by n transportation problems, matroids and matchings in a non-bipartite graph are developed.