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

摘要

An arbitrary 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 Rn×[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 Rn×[0,1], and the other phase of the algorithm constitutes a pivoting procedure, which generates n-dimensional simplices in either Rn×{0} or Rn×{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 in Rn×{0}, the algorithm within a finite number of iterations either yields an integer point of the simplex or proves that no such point exists.