Integer Polynomial Optimization in Fixed Dimension

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 polytop...

Full description

Saved in:
Bibliographic Details
Published in:Mathematics of operations research 2006-02, Vol.31 (1), p.147-153
Main Authors: De Loera, Jesus A, Hemmecke, Raymond, Koppe, Matthias, Weismantel, Robert
Format: Article
Language:English
Subjects:
Algorithms
Analysis
approximation algorithms
Approximation theory
Case studies
Coefficients
Computational complexity
FPTAS
Generating function
integer nonlinear programming
Integer programming
integer programming in fixed dimension
Integers
Mathematical lattices
Mathematical optimization
Nonlinear programming
Objective functions
Optimization algorithms
Polynomials
Polytopes
Rational functions
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0364-765X
1526-5471
DOI:10.1287/moor.1050.0169