Mixed integer polynomial programming

Friday, July 29, 2005 - 9:45am - 10:30am
EE/CS 3-180
Robert Weismantel (Otto-von-Guericke-Universität Magdeburg)
This talk deals with mixed integer optimization problems defined by
linear constraints and a polynomial function as the objective function.
We present motivating examples, illustrate techniques that reduce
the problem to a mixed integer linear program and discuss complexity results.
An algorithm is prersented that is based on Barvinok's rational
function theory, i.e., lattice points in polyhedra
are encoded through rational functions.
It turns out that under the assumption that the number of variables is fixed,
our algorithm leads to a fully polynomial time approximation scheme.
The results of this talk are based on joint work with
Raymond Hemmecke, Matthias Koeppe and Jesus De Loera.