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.
Current 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996
