### Michel Baes (Institute for Operations Research, ETH Zurich)

#### Oracle-based methods for mixed-integer convex optimization

*Joint work with A. Del Pia, Y. Nesterov, S. Onn, T. Oertel, C. Wagner, and R. Weismantel.*

*Tuesday 25 September 2012 at 13.00, JCMB 6206*

##### Abstract

We address the problem of minimizing a convex function f over a convex set,
with the extra constraint that some variables must be integer. This problem,
even when f is a piecewise linear function, is NP-hard.

We study two algorithmic approaches to this problem, postponing its hardness
to the realization of an oracle. If this oracle can be realized in polynomial
time, then the problem can be solved in polynomial time as well.

This first oracle is devised for problems where f is smooth and strongly convex
that has to be minimized over the integers of a given polytope. It consists of
a black-box algorithm that solves some special quadratic integer problems with
a constant approximation factor. We describe a few situations where we can
implement the needed black-box procedure efficiently.

The second one, called improvement oracle, can be used for Lipschitz continuous
functions f to minimize over a convex set, where some variables must also be
integers. We show how this oracle can be implemented efficiently, that is, in
O(ln(B)) approximate minimizations of f over the continuous variables, where B
is a known bound on the absolute value of the integer variables.

### Seminars by year

*Current*
*2016*
*2015*
*2014*
*2013*
*2012*
*2011*
*2010*
*2009*
*2008*
*2007*
*2006*
*2005*
*2004*
*2003*
*2002*
*2001*
*2000*
*1999*
*1998*
*1997*
*1996*