Abstract:
This talk deals with the problem of optimizing polynomial functions over the lattice points in a polyhedron when the number of variables is a constant.
We explain why the problem is already hard in dimension two for polynomial functions of degree four. Then we will discuss in detail how to solve the problem in polynomial time when the function is a quadratic polynomial in two variables [1].
Further complexity results about optimizing homogeneous polynomials and cubic polynomials over the integer points in polyhedra in dimension two will be presented too [2].
In arbitrary but fixed dimension the maximization of a positive polynomial over the lattice points in a polyhedron remains computationally challenging. We show that there exists an FPTAS for approximating the optimal value [3] that is based on algorithms for counting the number of lattice points in polyhedra [4].

References:
[1] A. Del Pia, R. Weismantel, Quadratic Integer Programming in the plane, Proceedings of SODA 2014.
[2] R. Hildebrand, A. Del Pia, R. Weismantel,K. Zemmer, Minimizing cubic and homogeneous polynomials over integers in the plane, Manuscript 2014.
[3] R. Hemmecke, M. K\"oppe, J. De Loera, R. Weismantel, Integer polynomial optimization in fixed dimension, Mathematics of Operations Research 31, 2006, 147 -- 153.
[4] A. Barvinok, Polynomial time algorithm for counting integral points in polyhedra when the dimension is fixed, Mathematics of Operations Research 19, 1994, 769 -- 779.