Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2609.17889

Bounded Integer Quadratic Programming through Parallelepiped Covers and Discrete Convic Optimization

Cinar Ari, Robert Hildebrand

Published Sep 15, 2026• 1 citation
arXivHTMLPDF

Abstract

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 \le 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.

DOI
10.48550/arxiv.2609.17889

Related papers

Subdeterminants and Concave Integer Quadratic Programming

Alberto Del Pia

We consider the NP-hard problem of minimizing a separable concave quadratic function over the integral points in a polyhedron, and we denote by $\Delta$ the largest absolute value of the subdeterminants of the constraint matrix. In this paper we give an algorithm that finds an $\epsilon$-approximate solution for this problem by solving a number of integer linear programs whose constraint matrices have subdeterminants bounded by $\Delta$ in absolute value. The number of these integer linear programs is polynomial in the dimension $n$, in $\Delta$, and in $1/\epsilon$, provided that the number $k$ of variables that appear nonlinearly in the objective is fixed. As a corollary, we obtain the first polynomial-time approximation algorithm for separable concave integer quadratic programming with $\Delta \le 2$ and $k$ fixed. In the totally unimodular case $\Delta = 1$, we give an improved algorithm that only needs to solve a number of linear programs that is polynomial in $1/\epsilon$ and is independent of $n$, provided that $k$ is fixed.

arXiv:1810.02763•SIAM Journal on Optimization•Jan 1, 2019•8 citations

Rational Jacobi Rotations and the Complexity of Approximating Mixed Integer Quadratic Programming

Alberto Del Pia

We present an algorithm that finds an epsilon-approximate solution to a mixed integer quadratic programming (MIQP) problem, and that runs on a Turing machine in time polynomial in the size of the instance and in 1/epsilon, provided that the number of integer variables and the number of negative eigenvalues of the Hessian of the objective function are fixed. Unless P=NP, both restrictions are necessary, so this completes the characterization of the complexity of approximating MIQP in terms of the number of integer variables and the inertia of the Hessian; the result is new already in the purely continuous case. The main ingredient is a polynomial-time simultaneous diagonalization algorithm: it computes a rational change of basis that maps a given ellipsoid, presented in factored form, exactly to a ball, while making the objective function separable up to an arbitrarily small perturbation and preserving the inertia of its Hessian. The classical construction, in which the objective function is made exactly separable, requires a change of basis that is in general irrational, and cannot be carried out on a Turing machine; ours rests instead on rational Jacobi rotations, which we believe to be of independent interest.

arXiv:2607.29386•Jul 31, 2026•0 citations

On the Chvátal-Gomory Closure of Integer Quadratic Programs

Linchuan Wei, Tong Xu, Kim Yu

The integer quadratic moment hull is the closed convex hull of the pairs $(z,zz^{\top})$ with $z\in\mathbb{Z}^n$. We prove that one round of Chvátal-Gomory (CG) cuts applied to its basic semidefinite relaxation recovers this hull exactly if and only if $n\le6$. Our approach identifies its facets with perfect Delaunay polyhedra and characterizes their recovery through depth, the gap between lattice and continuous minima of a defining quadratic after normalization. A facet inequality is valid for the rank-one CG closure exactly when its depth is less than one. We also analyze the complexity of deciding membership in the CG closure and finding violated inequalities. Every rational point outside the CG closure admits a violated CG inequality whose encoding length is polynomial in the input length. Membership is strongly coNP-complete and exact separation is strongly NP-hard. The same reduction proves strong NP-hardness of quadratic split-inequality separation, resolving a conjecture of Burer and Letchford.

arXiv:2610.34053•Oct 25, 2026•0 citations

Ellipsoid Bounds for Convex Quadratic Integer Programming

Christoph Buchheim, Ruth Hübner, Anita Schöbel

Solving convex quadratic integer minimization problems by a branch-and-bound algorithm requires tight lower bounds on the optimal objective value. To obtain such dual bounds, we follow the approach of [C. Buchheim, A. Caprara, and A. Lodi, Math. Program., 135 (2012), pp. 369--395] and underestimate the objective function by another convex quadratic function that can be minimized over the integers by simply rounding its continuous minimizer. In geometric terms, we approximate the sublevel sets of the original objective function by auxiliary ellipsoids having the strong rounding property, introduced by [R. Hübner and A. Schöbel, European J. Oper. Res., 237 (2014), pp. 404--410]. We first consider axisparallel ellipsoids (corresponding to separable convex quadratic functions) and show how to efficiently compute an axisparallel ellipsoid yielding the tightest lower bound, both in the situation where the location of the continuous minimizer is given and in the situation where it varies, as it happens in a branch-and-bound approach. In the latter case, we compute both worst-case and average-case optimal ellipsoids. Moreover, we consider the class of quasi-round ellipsoids (from Hübner and Schöbel). In this case, we do not know whether optimal auxiliary ellipsoids can be computed efficiently. However, we present a heuristic for computing an appropriate quasi-round ellipsoid that still yields valid dual bounds; it turns out that using this approach within a branch-and-bound scheme outperforms the approaches based on axisparallel ellipsoid in terms of running times. We finally combine both approaches by introducing the concept of quasi-axisparallel ellipsoids and present a corresponding extension of the heuristic bound computation.

SIAM Journal on Optimization•Jan 1, 2015•14 citations

Quadratic Combinatorial Optimization Using Separable Underestimators

Christoph Buchheim, Emiliano Traversi

Binary programs with a quadratic objective function are NP-hard in general, even if the linear optimization problem over the same feasible set is tractable. In this paper, we address such problems by computing quadratic global underestimators of the objective function that are separable but not necessarily convex. Exploiting the binary constraint on the variables, a minimizer of the separable underestimator over the feasible set can be computed by solving an appropriate linear minimization problem over the same feasible set. Embedding the resulting lower bounds into a branch-and-bound framework, we obtain an exact algorithm for the original quadratic binary program. The main practical challenge is the fast computation of an appropriate underestimator, which in our approach reduces to solving a series of semidefinite programs. We exploit the special structure of the resulting problems to obtain a tailored coordinate-descent method for their solution. Our extensive experimental results on various quadratic combinatorial optimization problems show that our approach outperforms both CPLEX and the related QCR method as well as the SDP-based software BiqCrunch on instances of the quadratic shortest path problem and the quadratic assignment problem.

INFORMS journal on computing•Aug 1, 2018•19 citations

Global solution of non-convex quadratically constrained quadratic programs

Sourour Elloumi, Amélie Lambert

The class of mixed-integer quadratically constrained quadratic programs (QCQP) consists of minimizing a quadratic function under quadratic constraints where the variables could be integer or continuous. On a previous paper we introduced a method called MIQCR for solving QCQPs with the following restriction: all quadratic sub-functions of purely continuous variables are already convex. In this paper, we propose an extension of MIQCR which applies to any QCQP. Let (P) be a QCQP. Our approach to solve (P) is first to build an equivalent mixed-integer quadratic problem (P∗). This equivalent problem (P∗) has a quadratic convex objective function, linear constraints, and additional variables y that are meant to satisfy the additional quadratic constraints y=xxT, where x are the initial variables of problem (P). We then propose to solve (P∗) by a branch-and-bound algorithm based on the relaxation of the additional quadratic constraints and of the integrality constraints. This type of branching is known as spatial branch-and-bound. Computational experiences are carried out on a total of 325 instances. The results show that the solution time of most of the considered instances is improved by our method in comparison with the recent implementation of QuadProgBB, and with the solvers Cplex, Couenne, Scip, BARON and GloMIQO.

Optimization methods & software•Jul 28, 2017•26 citations
We give an exact algorithm for minimizing an arbitrary rational quadratic polynomial xTQx+cTx+γx^T Q x + c^T x + γxTQx+cTx+γ over the integer points of a bounded rational polyhedron {x:Ax≤b}\{x : Ax \le b\}{x:Ax≤b}. For nnn variables and mmm inequalities, the running time is 2O(nlog⁡(n+1))(m+1)O(n)βO(n)(1+L)O(1),2^{O(n \log(n+1))} (m+1)^{O(n)} β^{O(n)} (1+L)^{O(1)},2O(nlog(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 AAA or QQQ, and LLL is the full input encoding length. The polynomial degree in LLL is absolute; in particular, the encoding of bbb, ccc, 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.
We consider the NP-hard problem of minimizing a separable concave quadratic function over the integral points in a polyhedron, and we denote by Δ\DeltaΔ the largest absolute value of the subdeterminants of the constraint matrix. In this paper we give an algorithm that finds an ϵ\epsilonϵ-approximate solution for this problem by solving a number of integer linear programs whose constraint matrices have subdeterminants bounded by Δ\DeltaΔ in absolute value. The number of these integer linear programs is polynomial in the dimension nnn, in Δ\DeltaΔ, and in 1/ϵ1/\epsilon1/ϵ, provided that the number kkk of variables that appear nonlinearly in the objective is fixed. As a corollary, we obtain the first polynomial-time approximation algorithm for separable concave integer quadratic programming with Δ≤2\Delta \le 2Δ≤2 and kkk fixed. In the totally unimodular case Δ=1\Delta = 1Δ=1, we give an improved algorithm that only needs to solve a number of linear programs that is polynomial in 1/ϵ1/\epsilon1/ϵ and is independent of nnn, provided that kkk is fixed.
We present an algorithm that finds an epsilon-approximate solution to a mixed integer quadratic programming (MIQP) problem, and that runs on a Turing machine in time polynomial in the size of the instance and in 1/epsilon, provided that the number of integer variables and the number of negative eigenvalues of the Hessian of the objective function are fixed. Unless P=NP, both restrictions are necessary, so this completes the characterization of the complexity of approximating MIQP in terms of the number of integer variables and the inertia of the Hessian; the result is new already in the purely continuous case. The main ingredient is a polynomial-time simultaneous diagonalization algorithm: it computes a rational change of basis that maps a given ellipsoid, presented in factored form, exactly to a ball, while making the objective function separable up to an arbitrarily small perturbation and preserving the inertia of its Hessian. The classical construction, in which the objective function is made exactly separable, requires a change of basis that is in general irrational, and cannot be carried out on a Turing machine; ours rests instead on rational Jacobi rotations, which we believe to be of independent interest.
The integer quadratic moment hull is the closed convex hull of the pairs (z,zz⊤)(z,zz^{\top})(z,zz⊤) with z∈Znz\in\mathbb{Z}^nz∈Zn. We prove that one round of Chvátal-Gomory (CG) cuts applied to its basic semidefinite relaxation recovers this hull exactly if and only if n≤6n\le6n≤6. Our approach identifies its facets with perfect Delaunay polyhedra and characterizes their recovery through depth, the gap between lattice and continuous minima of a defining quadratic after normalization. A facet inequality is valid for the rank-one CG closure exactly when its depth is less than one. We also analyze the complexity of deciding membership in the CG closure and finding violated inequalities. Every rational point outside the CG closure admits a violated CG inequality whose encoding length is polynomial in the input length. Membership is strongly coNP-complete and exact separation is strongly NP-hard. The same reduction proves strong NP-hardness of quadratic split-inequality separation, resolving a conjecture of Burer and Letchford.
Solving convex quadratic integer minimization problems by a branch-and-bound algorithm requires tight lower bounds on the optimal objective value. To obtain such dual bounds, we follow the approach of [C. Buchheim, A. Caprara, and A. Lodi, Math. Program., 135 (2012), pp. 369--395] and underestimate the objective function by another convex quadratic function that can be minimized over the integers by simply rounding its continuous minimizer. In geometric terms, we approximate the sublevel sets of the original objective function by auxiliary ellipsoids having the strong rounding property, introduced by [R. Hübner and A. Schöbel, European J. Oper. Res., 237 (2014), pp. 404--410]. We first consider axisparallel ellipsoids (corresponding to separable convex quadratic functions) and show how to efficiently compute an axisparallel ellipsoid yielding the tightest lower bound, both in the situation where the location of the continuous minimizer is given and in the situation where it varies, as it happens in a branch-and-bound approach. In the latter case, we compute both worst-case and average-case optimal ellipsoids. Moreover, we consider the class of quasi-round ellipsoids (from Hübner and Schöbel). In this case, we do not know whether optimal auxiliary ellipsoids can be computed efficiently. However, we present a heuristic for computing an appropriate quasi-round ellipsoid that still yields valid dual bounds; it turns out that using this approach within a branch-and-bound scheme outperforms the approaches based on axisparallel ellipsoid in terms of running times. We finally combine both approaches by introducing the concept of quasi-axisparallel ellipsoids and present a corresponding extension of the heuristic bound computation.
Binary programs with a quadratic objective function are NP-hard in general, even if the linear optimization problem over the same feasible set is tractable. In this paper, we address such problems by computing quadratic global underestimators of the objective function that are separable but not necessarily convex. Exploiting the binary constraint on the variables, a minimizer of the separable underestimator over the feasible set can be computed by solving an appropriate linear minimization problem over the same feasible set. Embedding the resulting lower bounds into a branch-and-bound framework, we obtain an exact algorithm for the original quadratic binary program. The main practical challenge is the fast computation of an appropriate underestimator, which in our approach reduces to solving a series of semidefinite programs. We exploit the special structure of the resulting problems to obtain a tailored coordinate-descent method for their solution. Our extensive experimental results on various quadratic combinatorial optimization problems show that our approach outperforms both CPLEX and the related QCR method as well as the SDP-based software BiqCrunch on instances of the quadratic shortest path problem and the quadratic assignment problem.
The class of mixed-integer quadratically constrained quadratic programs (QCQP) consists of minimizing a quadratic function under quadratic constraints where the variables could be integer or continuous. On a previous paper we introduced a method called MIQCR for solving QCQPs with the following restriction: all quadratic sub-functions of purely continuous variables are already convex. In this paper, we propose an extension of MIQCR which applies to any QCQP. Let (P) be a QCQP. Our approach to solve (P) is first to build an equivalent mixed-integer quadratic problem (P∗). This equivalent problem (P∗) has a quadratic convex objective function, linear constraints, and additional variables y that are meant to satisfy the additional quadratic constraints y=xxT, where x are the initial variables of problem (P). We then propose to solve (P∗) by a branch-and-bound algorithm based on the relaxation of the additional quadratic constraints and of the integrality constraints. This type of branching is known as spatial branch-and-bound. Computational experiences are carried out on a total of 325 instances. The results show that the solution time of most of the considered instances is improved by our method in comparison with the recent implementation of QuadProgBB, and with the solvers Cplex, Couenne, Scip, BARON and GloMIQO.