Mixed Integer Polynomial Optimization  – Algorithms and Complexity for Linear and Non-Linear Cases when the Dimension is Fixed

(Joint AMD and OR Seminar)

Robert Hildebrand — Virginia Tech

Integer Programming (or Integer Optimization) is the problem if optimizing an objective function over a set of feasible points that have the restriction that some variables must take integer values.  Integer linear programming (optimizing a linear function over linear constraints and integer constraints) is NP-Hard, while the continuous counterpart, Linear Programming, is polynomial time solvable.  Since the linear case is NP-Hard, the non-linear case of integer programming is also NP-Hard.  The story becomes much different when the dimension is considered a fixed number.  For instance, what is the complexity of integer linear programming when there are only 3 variables?   Lenstra proved in the 80’s that in fact, for any fixed dimension, integer linear programming can be solved in polynomial time.  This result hinges on the lattice basis reduction algorithms such as the famous LLL algorithm.    Surprisingly, the question of complexity in fixed dimension is very unclear even for quadratic integer programming.  We will survey Lenstra-type algorithms for integer programming and show recent results on convex and non-convex mixed integer programming.