Abstract:
This talk deals with the problem of optimizing nonlinear functions over the lattice points in convex or polyhedral sets. We present several algorithmic schemes that become polynomial time algorithms for special cases of the general problem or when the number of variables is constant. Particular attention is given to nonlinear objective functions that are (quasi) convex or (quasi) concave. For the minimization of concave functions over integer points in polyhedra of fixed dimension the following result is the key tool: Shevchenko (1981) and Hayes and Larman (1983) proved that the number of vertices of the integer hull of a rational polyhedron is polynomial in fixed dimension. Hartmann (1989) developed an algorithm for computing the integer hull.
For the minimization of convex functions over integer points in polyhedra or in convex sets of fixed and variable dimension several important results are known and will be presented in this talk. We discuss several recent results about the speed of convergence of oracle algorithms that iteratively solve special integer subproblems either exactly or 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.

References:
[1] T. Oertel, Ch. Wagner, R. Weismantel, Integer convex minimization by mixed integer linear optimization, Operations Research letters 42, 2014, 424 -- 428.
[2] M. Baes, T. Oertel, C. Wagner, R. Weismantel, Mirror-descent methods in mixed-integer convex optimization, in ``Facets of Combinatorial Optimization", eds. M. J\"unger, G. Reinelt, Algorithms and Combinatorics Series, Springer, 2013, 101 -- 130.
[3] V.N. Shevchenko (1981), On the number of extreme points in integer programming, Kibernetica (2), 133-134.
[4] A.C. Hayes and D.G. Larman (1983), The vertices of the knapsack polytope, Discrete Applied Mathematics 6 (2), 135 - 138.
[5] M.E. Hartmann (1989), Cutting planes and the complexity of the integer hull, PhD Thesis, Dept. of OR and IE, Cornell University, Ithaca, NY