VERTEX ENUMERATION OF POLYHEDRA
Caio Lopes Assad, Gudélia Morales, José Árica · Pesquisa Operacional · 2022
The vertex enumeration problem of a polyhedron P in ℜn , given by m inequalities, is widely discussed in the literature. In this work it is introduced a new algorithm to solve it. The algorithm is based on lexicographic pivoting and the worst-case time complexity is Omm+n2×minm,n which is OmnVP for the case of non-degenerate polyhedra, where VP is the number of vertices of P. The proposed algorithm was coded in Matlab and numerical experiments performed for several randomly generated problems show its efficiency.