Article ID: | iaor200928634 |
Country: | United States |
Volume: | 31 |
Issue: | 1 |
Start Page Number: | 147 |
End Page Number: | 153 |
Publication Date: | Feb 2006 |
Journal: | Mathematics of Operations Research |
Authors: | Weismantel Robert, Kppe Matthias, Hemmecke Raymond, Loera Jess A de |
We classify, according to their computational complexity, integer optimization problems whose constraints and objective functions are polynomials with integer coefficients, and the number of variables is fixed. For the optimization of an integer polynomial over the lattice points of a convex polytope, we show an algorithm to compute lower and upper bounds for the optimal value. For polynomials that are nonnegative over the polytope, these sequences of bounds lead to a fully polynomial–time approximation scheme for the optimization problem.