Computing an integer point of a simplex with an arbitrary starting homotopy-like simplicial algorithm

An arbitary starting homotopy-like simplicial algorithm is developed for computing an integer point of an n-dimensional simplex. The algorithm is derived from the use of an integer labeling rule and a triangulation of Rⁿ and times [0,1], and consists of two interchanging phases. One phase of the algorithm constitutes a homotopy simplicial algorithm, which generates (n + 1)-dimensional simplices in Rⁿ and times [0,1], and the other phase of the algorithm constitutes a pivoting procedure, which generates n-dimensional simplices in either Rⁿ and times {0} or Rⁿ and times {1}. The algorithm varies from one phase to the other. When the matrix defining the simplex is in the so-called canonical form, starting at an arbitrary integer point Rⁿ and times {0}, the algorithm within a finite number of iterations either yields an integer point of the simplex or proves that no such point exists. © 2001 Elsevier Science B.V. All rights reserved.