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:2607.29386

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

Alberto Del Pia

Published Jul 31, 2026• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2607.29386

Related papers

Bounded Integer Quadratic Programming through Parallelepiped Covers and Discrete Convic Optimization

Cinar Ari, Robert Hildebrand

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.

arXiv:2609.17889•Sep 15, 2026•1 citation

Solving Mixed-Integer Quadratic Programs via Nonnegative Least Squares

Alberto Bemporad

This paper proposes a new algorithm for solving Mixed-Integer Quadratic Programming (MIQP) problems. The algorithm is particularly tailored to solving small-scale MIQPs such as those that arise in embedded hybrid Model Predictive Control (MPC) applications. The approach combines branch and bound (B&B) with nonnegative least squares (NNLS), that are used to solve Quadratic Programming (QP) relaxations. The QP algorithm extends a method recently proposed by the author for solving strictly convex QP's, by (i) handling equality and bilateral inequality constraints, (ii) warm starting, and (iii) exploiting easy-to-compute lower bounds on the optimal cost to reduce the number of QP iterations required to solve the relaxed problems. The proposed MIQP algorithm has a speed of execution that is comparable to state- of-the-art commercial MIQP solvers and is relatively simple to code, as it requires only basic arithmetic operations to solve least-square problems.

IFAC-PapersOnLine•Jan 1, 2015•26 citations

A new Branch and Bound algorithm for MIQPs

Alain Billionnet, Sourour Elloumi, Amélie Lambert

Let (MQP) be a MIQP that consists in minimizing a quadratic function subject to linear constraints. Our approach to solve (MQP) is first to consider (MQP'), an equivalent MIQP that has a convex objective function, additional variables and constraints, and additionnal quadratic constraints. Then, we propose a new Branch and Bound based on the relaxation of the quadratic constraints to solve (MQP'). We perform experiments on pure-and mixed-integer instances of medium size, and show that their solution times are improved by our Branch and Bound in comparison with two existing approaches.

•Jul 9, 2012•0 citations

Embedded Mixed-Integer Quadratic optimization Using the OSQP Solver

Bartolomeo Stellato, Vihangkumar V. Naik, Alberto Bemporad +2 more

We present a novel branch-and-bound solver for mixed-integer quadratic programs (MIQPs) that efficiently exploits the first-order OSQP solver for the quadratic program (QP) sub-problems. Our algorithm is very robust, requires no dynamic memory allocation and is division-free once an initial factorization is computed. Thus, it suitable for embedded applications with low computing power. Moreover, it does not require any assumption on the problem data such as strict convexity of the objective function. We exploit factorization caching and warm-starting to reduce the computational cost of QP relaxations during branch-and-bound and over repeated solutions of parametric MIQPs such as those arising in embedded control, portfolio optimization, and machine learning. Numerical examples show that our method, using a simple high-level Python implementation interfaced with the OSQP solver, is competitive with established commercial solvers.

European Control Conference (ECC)•Jun 1, 2018•48 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

Exact and Heuristic Methods with Warm-start for Embedded Mixed-Integer Quadratic Programming Based on Accelerated Dual Gradient Projection

Vihangkumar V. Naik, Alberto Bemporad

Small-scale Mixed-Integer Quadratic Programming (MIQP) problems often arise in embedded control and estimation applications. Driven by the need for algorithmic simplicity to target computing platforms with limited memory and computing resources, this paper proposes a few approaches to solving MIQPs, either to optimality or suboptimally. We specialize an existing Accelerated Dual Gradient Projection (GPAD) algorithm to effectively solve the Quadratic Programming (QP) relaxation that arise during Branch and Bound (B&B) and propose a generic framework to warm-start the binary variables which reduces the number of QP relaxations. Moreover, in order to find an integer feasible combination of the binary variables upfront, two heuristic approaches are presented: ($i$) without using B&B, and ($ii$) using B&B with a significantly reduced number of QP relaxations. Both heuristic approaches return an integer feasible solution that may be suboptimal but involve a much reduced computation effort. Such a feasible solution can be either implemented directly or used to set an initial upper bound on the optimal cost in B&B. Through different hybrid control and estimation examples involving binary decision variables, we show that the performance of the proposed methods, although very simple to code, is comparable to that of state-of-the-art MIQP solvers.

arXiv:2101.09264•Jan 22, 2021•6 citations
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.
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.
This paper proposes a new algorithm for solving Mixed-Integer Quadratic Programming (MIQP) problems. The algorithm is particularly tailored to solving small-scale MIQPs such as those that arise in embedded hybrid Model Predictive Control (MPC) applications. The approach combines branch and bound (B&B) with nonnegative least squares (NNLS), that are used to solve Quadratic Programming (QP) relaxations. The QP algorithm extends a method recently proposed by the author for solving strictly convex QP's, by (i) handling equality and bilateral inequality constraints, (ii) warm starting, and (iii) exploiting easy-to-compute lower bounds on the optimal cost to reduce the number of QP iterations required to solve the relaxed problems. The proposed MIQP algorithm has a speed of execution that is comparable to state- of-the-art commercial MIQP solvers and is relatively simple to code, as it requires only basic arithmetic operations to solve least-square problems.
Let (MQP) be a MIQP that consists in minimizing a quadratic function subject to linear constraints. Our approach to solve (MQP) is first to consider (MQP'), an equivalent MIQP that has a convex objective function, additional variables and constraints, and additionnal quadratic constraints. Then, we propose a new Branch and Bound based on the relaxation of the quadratic constraints to solve (MQP'). We perform experiments on pure-and mixed-integer instances of medium size, and show that their solution times are improved by our Branch and Bound in comparison with two existing approaches.
We present a novel branch-and-bound solver for mixed-integer quadratic programs (MIQPs) that efficiently exploits the first-order OSQP solver for the quadratic program (QP) sub-problems. Our algorithm is very robust, requires no dynamic memory allocation and is division-free once an initial factorization is computed. Thus, it suitable for embedded applications with low computing power. Moreover, it does not require any assumption on the problem data such as strict convexity of the objective function. We exploit factorization caching and warm-starting to reduce the computational cost of QP relaxations during branch-and-bound and over repeated solutions of parametric MIQPs such as those arising in embedded control, portfolio optimization, and machine learning. Numerical examples show that our method, using a simple high-level Python implementation interfaced with the OSQP solver, is competitive with established commercial solvers.
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.
Small-scale Mixed-Integer Quadratic Programming (MIQP) problems often arise in embedded control and estimation applications. Driven by the need for algorithmic simplicity to target computing platforms with limited memory and computing resources, this paper proposes a few approaches to solving MIQPs, either to optimality or suboptimally. We specialize an existing Accelerated Dual Gradient Projection (GPAD) algorithm to effectively solve the Quadratic Programming (QP) relaxation that arise during Branch and Bound (B&B) and propose a generic framework to warm-start the binary variables which reduces the number of QP relaxations. Moreover, in order to find an integer feasible combination of the binary variables upfront, two heuristic approaches are presented: (iii) without using B&B, and (iiiiii) using B&B with a significantly reduced number of QP relaxations. Both heuristic approaches return an integer feasible solution that may be suboptimal but involve a much reduced computation effort. Such a feasible solution can be either implemented directly or used to set an initial upper bound on the optimal cost in B&B. Through different hybrid control and estimation examples involving binary decision variables, we show that the performance of the proposed methods, although very simple to code, is comparable to that of state-of-the-art MIQP solvers.