Curvature batching for integer and mixed-integer quadratic programming

Abstract

We give an explicit algorithm for integer quadratic programming with running time $(nL{)}^{O(n^2)}\mathrm{poly}(\varphi )$, where $n$ is the number of variables, $L$ bounds the absolute entries of the constraint and quadratic matrices, and $\varphi$ is the total input encoding length. The linear objective and constraint right-hand sides enter only through $\varphi$. The algorithm refines Lokshtanov's branching framework. Small integer kernel directions identify optima near constraint boundaries. When all chosen basis directions have nonnegative curvature, their gradient values can be imposed in one batch. The quadratic form then vanishes on the remaining kernel, and the residual problem is an integer linear program. Thus determinant growth after the batch does not feed into further branching. Over a polytope, the method extends to mixed-integer quadratic programming with $q$ continuous variables in time $(nL{)}^{O(n^2(q+1{)}^2)}\mathrm{poly}(\varphi )$, without a convexity assumption on the continuous block. We also decide and certify integer and mixed-integer unboundedness in $(m+n{)}^{O(n)}\mathrm{poly}(\varphi )$ time for arbitrary rational polyhedra with $m$ inequalities. Noncopositivity on polyhedral cones and integer unboundedness are W[1]-hard in the dimension and admit no $(m+\varphi {)}^{o(n)}$ algorithm under ETH, matching the linear order of dimension in the recession-test exponent. Companion results give a right-hand-side-independent bound for concave integer minimization and explicit runtimes for applications of IQP.