Groupe d’études et de recherche en analyse des décisions

G-92-15

Partial Pivoting in Vertex Enumeration

, et

The off-line vertex enumeration problem for polytopes consists in determining all vertices of a given polytope P. The on-line vertex enumeration problem consists in determining all vertices of where H is a given half-space, assuming vertices of P are known. The off-line problem can be solved by searching the adjacency graph of P, pivoting iteratively from a tableau corresponding to a vertex of P to a tableau corresponding to an adjacent unexplored vertex. Improving on a result of Dyer (1983), we first show that this can be done in O (mn ) time, where m is the number of facets, n is the dimension and the number of vertices of P. Adjacent vertices of a vertex for which a tableau is known can be determined using only two columns of that tableau each time, i.e., by partial pivoting. We discuss and compare Mattheiss' algorithm (1973) and the barred pivot strategy of Dyer (1983) which both use partial pivoting. Next we propose a new algorithm in which the number of vertices for which the whole tableau must be built is reduced. This is attained by using hash coding to detect adjacencies between such vertices and their neighbors as well as between pairs of these neighbors. Computational results are reported. Finally we note that the on-line vertex enumeration problem can be stated as an off-line problem after elimination of a variable. This strategy is compared theoretically and/or empirically with recent algorithms for on-line vertex enumeration due to Falk and Hoffman (1976, 1986), Horst, de Vries and Thoai (1988), Thieu, Tam and Ban (1983) and Chen, Hansen and Jaumard (1991).

, 39 pages