Simplicial algorithms for (linear) integer programming

approximations of continuous mappings. They are widely used, for example,
in the approximation of zero's of multivariate complex polynomials.
Although the applications concern topological issues, the underlying
combinatorics is that of Sperner's Lemma.

In this talk we show how to extend Sperner's Lemma such as to make
it useful for integer programming. Key concepts are triangulations,
labeling rules defined by the polytopes to investigate and unimodular
transformations. We show that, given a simplex in Euclidean space,
a path of integer lattice points can be followed which terminates in a
lattice point of the simplex, or terminates in a so called completely
labeled member of the triangulation, in which case it is demonstrated
that the simplex involved has no integer lattice point.

The above procedure is a new attack to integer programming. There are no
obvious relations to branch and bound or to cutting planes. Through the
unimodular transformation there is a tiny link with the test-set approach.
We shall present some computational experiments. The talk is based
on joint work with Chuangyin Dang. A paper on this shall appear in
Mathematics of Operations Research before summer of next year.