Hidden Convexity via Symmetric Displacement Covers: Mixed-Integer Quadratic Programming and Integer Cubic Programming in Fixed Dimension
Abstract
We give exact polynomial-time algorithms in fixed dimension for mixed-integer quadratic programming over arbitrary rational polyhedra and for integer cubic programming over bounded rational polyhedra. The quadratic objective may be indefinite; the algorithm detects infeasibility, certifies unboundedness, or returns an exact minimizer. For an instance with N variables and m constraints, the running time is 2O(Nlog N) times (m+ 1)O(N) times a factor in which the binary encoding lengths of the coefficients are raised to a power O(N); for pure integer problems, and for mixed-integer problems with integral right-hand side and linear term, only the constraint and quadratic matrices enter this factor, while the right-hand side and linear term enter polynomially. This replaces the dependence on coefficient magnitudes in earlier fixed-parameter results by dependence on encoding length, and the exponent O(N) is optimal under the exponential time hypothesis. For cubic objectives, integer minimization over a bounded polyhedron was previously known to be polynomial only in dimension two. Our algorithm extends to any polynomial whose second directional derivatives are concave in position, which includes cubics with an added concave quartic form. Both algorithms rest on a hidden convexity of such objectives on bounded lattice sets, exposed by a cover of the feasible integer points by reflecting cells. For quadratics, a negative-curvature integer displacement excludes a cell, and otherwise supporting inequalities on its integer points permit exact optimization through an integer-query separation oracle. For cubics and the broader class, negative curvature at a query point yields a linear cut valid for every global minimizer in the cell, and supporting inequalities among the remaining admissible points play the same role.
Related
- One-Cut Risk Profiles under Quadratic Loss: Discrete Convexity, Continuous Limits, and Higher Dimensions
- Hidden Convexity of the Joint Range of Three Quadratic Forms and Applications
- Almgren frequency and Agmon convexity on rotationally symmetric Cartan-Hadamard manifolds
- Long-time and large-population limits of displacement monotone linear-quadratic Nash systems
- Hidden Convexity in Multi-Retailer Cold-Chain Allocation: A Cholesky-Spectral Second-Order Cone Programming Approach
BibTeX
@misc{ari2026hidden,
title = {{Hidden Convexity via Symmetric Displacement Covers: Mixed-Integer Quadratic Programming and Integer Cubic Programming in Fixed Dimension}},
author = {Cinar Ari and Robert Hildebrand},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.18266},
eprint = {2609.18266},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.18266},
}
RIS
TY - UNPB
TI - Hidden Convexity via Symmetric Displacement Covers: Mixed-Integer Quadratic Programming and Integer Cubic Programming in Fixed Dimension
AU - Cinar Ari
AU - Robert Hildebrand
PY - 2026
DA - 2026/09/23
PB - arXiv
DO - 10.48550/arxiv.2609.18266
UR - https://arxiv.org/abs/2609.18266
AB - We give exact polynomial-time algorithms in fixed dimension for mixed-integer quadratic programming over arbitrary rational polyhedra and for integer cubic programming over bounded rational polyhedra. The quadratic objective may be indefinite; the algorithm detects infeasibility, certifies unboundedness, or returns an exact minimizer. For an instance with N variables and m constraints, the running time is 2O(Nlog N) times (m+ 1)O(N) times a factor in which the binary encoding lengths of the coefficients are raised to a power O(N); for pure integer problems, and for mixed-integer problems with integral right-hand side and linear term, only the constraint and quadratic matrices enter this factor, while the right-hand side and linear term enter polynomially. This replaces the dependence on coefficient magnitudes in earlier fixed-parameter results by dependence on encoding length, and the exponent O(N) is optimal under the exponential time hypothesis. For cubic objectives, integer minimization over a bounded polyhedron was previously known to be polynomial only in dimension two. Our algorithm extends to any polynomial whose second directional derivatives are concave in position, which includes cubics with an added concave quartic form. Both algorithms rest on a hidden convexity of such objectives on bounded lattice sets, exposed by a cover of the feasible integer points by reflecting cells. For quadratics, a negative-curvature integer displacement excludes a cell, and otherwise supporting inequalities on its integer points permit exact optimization through an integer-query separation oracle. For cubics and the broader class, negative curvature at a query point yields a linear cut valid for every global minimizer in the cell, and supporting inequalities among the remaining admissible points play the same role.
ER -