An arbitrary starting homotopy-like simplicial algorithm for computing an integer point in a class of polytopes

An arbitrary starting homotopy-like simplicial algorithm is developed for computing an integer point in a polytope given by P = {x | Ax ≤ b} satisfying that each row of A has at most one positive entry. The algorithm is derived from an introduc tion of an integer labeling rule and an application of a triangulation of the space Rn × [0, 1]. It consists of two phases, one of which forms an (n + 1)-dimensional pivoting procedure and the other an n-dimensional pivoting procedure. Starting from an arbitrary integer point in Rn ×{0}, the algorithm interchanges from one phase to the other, if necessary, AND follows a finite simplicial path that either leads to an integer point in the polytope or proves that no such point exists. © 2009 Society for Industrial and Applied Mathematics.