Download

Open access

Author

Zemmer, Kevin

Date

2017Type

- Doctoral Thesis

ETH Bibliography

yes
Altmetrics

Download

Abstract

The problem of optimizing multivariate scalar polynomial functions over mixed-integer points in polyhedra is a generalization of the well known Linear Programming (LP) problem. While LP problems have been shown to be polynomially solvable, their extension to mixed-integer points, known as Mixed-Integer Linear Programming (MILP), is NP-hard. However, if the number of integer variables is fixed, MILP is polynomially solvable.
We develop algorithms for (mixed-)integer programming problems with a fixed number of variables for several classes of objective functions that are polynomials of fixed degree at least two, with some additional assumptions. With this, we are able to provide new complexity results for the given classes of problems.
The first result deals with minimizing cubic polynomials over the integer points of a polyhedron in dimension two. We show that this problem is solvable in time polynomial in the input size by providing an explicit algorithm, thus extending a previous result that showed this for quadratic polynomials. We prove this for both bounded and unbounded polyhedra.
The second result deals with minimizing homogeneous polynomials over the integer points of a polyhedron in dimension two. We provide an algorithm for solving this problem in time polynomial in the input size if the degree of the polynomial is fixed and the polyhedron is bounded. This result still holds when the function is the translation of a homogeneous function, even when the resulting function is not homogeneous and the translation vector is not known. We also show that if the polyhedron is unbounded, then a solution of minimal size to this problem can have exponential size in the input size.
The third result deals with minimizing quadratic polynomials over the mixed-integer points of polyhedra in fixed dimension. We show that this problem is solvable in time that is polynomial in the size of the input and the maximum absolute values of the matrices defining the constraints and the objective function. We also combine this with previous results to derive a similar result for quadratic functions defined by a low-rank matrix in variable dimension.
The fourth result also deals with minimizing quadratic polynomials over the integer points of a polyhedron in fixed dimension. We present a fully polynomial-time approximation scheme (FPTAS) for this problem when the objective function is homogeneous and the matrix defining it has at most one positive or at most one negative eigenvalue Show more

Permanent link

https://doi.org/10.3929/ethz-b-000241796Publication status

publishedExternal links

Search via SFX
Contributors

Examiner: Weismantel, RobertExaminer: Del Pia, Alberto

Publisher

ETH ZurichSubject

Operations Research; Mathematical Optimization; Integer Optimization; Polynomial Optimization; Fixed DimensionOrganisational unit

03873 - Weismantel, Robert
More

Show all metadata
ETH Bibliography

yes
Altmetrics