Campus Event Calendar

Event Entry

What and Who

Simplicial algorithms for (linear) integer programming

Hans van Maaren
TU Delft
AG1 Mittagsseminar
AG 1, AG 2  
AG Audience

Date, Time and Location

Wednesday, 10 December 97
60 Minutes


Simplicial algorithms provide a powerful tool in fixed point

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.


Alexander Bockmayr
--email hidden
passcode not visible
logged in users only

Tags, Category, Keywords and additional notes

Integer Programming