Bounded Integer Quadratic Programming through Parallelepiped Covers and Discrete Convic Optimization

Abstract

We give an exact algorithm for minimizing an arbitrary rational quadratic polynomial $x^T Q x + c^T x + \gamma$ over the integer points of a bounded rational polyhedron $\{x : Ax \le b\}$. For $n$ variables and $m$ inequalities, the running time is $$2^{O(n \log(n+1))} (m+1)^{O(n)} \beta^{O(n)} (1+L)^{O(1)},$$ where $\beta$ is one plus the maximum binary encoding length of an entry of $A$ or $Q$, and $L$ is the full input encoding length. The polynomial degree in $L$ is absolute; in particular, the encoding of $b$, $c$, and $\gamma$ enters only this fixed-degree factor. Our algorithm refines the integral parallelepiped cover of Goemans and Rothvoss into cells with controlled displacement sets. On each cell, either an integer displacement of negative quadratic value rules out every point as a global minimizer, or the quadratic identity supplies a separation oracle for the convex hull of each integer objective sublevel set. The integer-query feasibility theorem of Hildebrand and Goess then finds the cell minimum. A refinement through scaled lattices solves the displacement search, and a localization argument separates the encoding dependence of the constraint matrix and quadratic part from that of the remaining data. Combining the bounded algorithm with the unboundedness test of Ari and Hildebrand extends the method to arbitrary rational polyhedra.