Bounded Integer Quadratic Programming through Parallelepiped Covers and Discrete Convic Optimization
Abstract
We give an exact algorithm for minimizing an arbitrary rational quadratic polynomial xT Q x + cT x + γ over the integer points of a bounded rational polyhedron {x : Ax ≤ b}. For n variables and m inequalities, the running time is 2O(n log(n+1)) (m+1)O(n) βO(n) (1+L)O(1), where β 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 γ 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.
Related
- A sequential quadratic programming method for optimization with expectation objective functions, deterministic inequality constraints and robust subproblems
- Learning to Solve Mixed-Integer Nonlinear Programming with Neural Networks and Sequential Quadratic Programming Refinement
- Adaptive Variance-Reduced Stochastic Sequential (Quadratic Constrained) Quadratic Programming
- cuPDQPx: A GPU-Accelerated Restarted Halpern PDHG for Large-Scale Convex Quadratic Programming
- Recent Developments in HPR Methods for Large-Scale Convex Composite Quadratic Programming
BibTeX
@misc{ari2026bounded,
title = {{Bounded Integer Quadratic Programming through Parallelepiped Covers and Discrete Convic Optimization}},
author = {Cinar Ari and Robert Hildebrand},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.17889},
eprint = {2609.17889},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.17889},
}
RIS
TY - UNPB
TI - Bounded Integer Quadratic Programming through Parallelepiped Covers and Discrete Convic Optimization
AU - Cinar Ari
AU - Robert Hildebrand
PY - 2026
DA - 2026/09/15
PB - arXiv
DO - 10.48550/arxiv.2609.17889
UR - https://arxiv.org/abs/2609.17889
AB - We give an exact algorithm for minimizing an arbitrary rational quadratic polynomial x^T Q x + c^T x + γ over the integer points of a bounded rational polyhedron {x : Ax ≤ b}. For n variables and m inequalities, the running time is 2^O(n log(n+1)) (m+1)^O(n) β^O(n) (1+L)^O(1), where β 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 γ 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.
ER -