Enumerating extreme points of a highly degenerate polytope

In the standard algorithm for enumerating all the EPs of a polytope, degeneracy causes difficulty. The problem lies in the fact that in a degenerate case it is not straightforward, as opposed to a non-degenerate case, to find all the neighbors of an EP by pivoting operation with respect to the simplex tableau associated with that EP. This paper gives a recursive method for finding all the neighboring EPs of a degenerate EP. Based on this method, the authors develop an algorithm that explicitly accounts for degeneracy. They then revise this to obtain the second algorithm that exploit ‘contractibility’ to accelerate computation. These algorithms are explained in depth usng a numerical example, and computational experience is briefly commented.