Integer Polynomial Optimization in Fixed Dimension
- 1 February 2006
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 31 (1), 147-153
- https://doi.org/10.1287/moor.1050.0169
Abstract
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.Keywords
Other Versions
This publication has 9 references indexed in Scilit:
- Effective lattice point counting in rational convex polytopesJournal of Symbolic Computation, 2004
- Short rational functions for toric algebra and applicationsJournal of Symbolic Computation, 2004
- A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 ProgrammingMathematics of Operations Research, 2003
- Minimizing polynomial functionsPublished by American Mathematical Society (AMS) ,2003
- Global Optimization with Polynomials and the Problem of MomentsSIAM Journal on Optimization, 2001
- Integer Optimization on Convex Semialgebraic SetsDiscrete & Computational Geometry, 2000
- A Polynomial Time Algorithm for Counting Integral Points in Polyhedra When the Dimension is FixedMathematics of Operations Research, 1994
- Integer Programming with a Fixed Number of VariablesMathematics of Operations Research, 1983
- There Cannot be any Algorithm for Integer Programming with Quadratic ConstraintsOperations Research, 1973