IFIP TC 7 / 2013 - Minisymposia



  • Robert Weismantel, ETH Zürich, Switzerland  
"Mixed Integer Convex Optimization"

This talk deals with algorithms and complexity results about the minimization of convex functions over mixed integer points in convex regions.
This  topic is quite novel and today only few non-trivial algorithmic methods exist that can cope with problems of this generality. We  survey current state of art, both when the number of integer
variables is constant and variable.
We discuss results about the speed of convergence of oracle algorithms that iteratively solve special integer subproblems with a constant approximation factor. Despite the generality of the underlying  setting we show how to detect efficiently w.r.t. our oracle assumptions feasible solutions whose objective function value is close to the optimal value.
We also show how to prove that  such  proximity results are best possible up to a polynomial factor.