Exact quadratic convex reformulations of mixed-integer quadratically constrained problems

Abstract

We propose a solution approach for the general problem (QP) of minimizing a quadratic function of bounded integer variables subject to a set of quadratic constraints. The resolution is based on the reformulation of the original problem (QP) into an equivalent quadratic problem whose continuous relaxation is convex, so that it can be effectively solved by a branch-and-bound algorithm based on quadratic convex relaxation. We concentrate our efforts on finding a reformulation such that the continuous relaxation bound of the reformulated problem is as tight as possible. Furthermore, we extend our method to the case of mixed-integer quadratic problems with the following restriction: all quadratic sub-functions of purely continuous variables are already convex. Finally, we illustrate the different results of the article by small examples and we present some computational experiments on pure-integer and mixed-integer instances of (QP). Most of the considered instances with up to 53 variables can be solved by our approach combined with the use of Cplex.

1 Introduction

In this paper, we aim at the exact solution of mixed-integer quadratically constrained programs. For this, we first consider the pure integer case, i.e. the following program (QP):

where

$$\begin{aligned} f_r(x) = \langle Q_r, xx^T \rangle + c_r^Tx \quad \forall \,\, r = 0, \ldots , m \end{aligned}$$

with $\langle A , B \rangle = {\sum _{i=1}^n}{\sum _{j=1}^n} a_{ij}b_{ij}$, and for $r = 0, \ldots , m$, $Q_r$ is a symmetric $n \times n$ matrix, $c_r \in {\mathbb {R}}^{n}$, $b_r \in {\mathbb {R}}$, $I=\{1,\ldots ,n\}$. Variables $x_i$ are integers and are bounded by $u_i \in {\mathbb {N}}$ and $\ell _i \in {\mathbb {N}}$. Without loss of generality, we shall suppose $\ell _i=0$ since it is possible to change variable $x_i$ into $x_i-\ell _i$. We assume the feasible domain of (QP) to be non-empty.

This general program trivially contains the case where there are quadratic equalities, since an equality can be replaced by two inequalities. It also contains the case of linear constraints since a linear equality is a quadratic constraint with a zero quadratic part.

Program (QP) belongs to the class of ${\mathcal {NP}}$-hard [13] Mixed-Integer Non Linear Programs (MINLP). General approaches to solve MINLP are based on global optimization techniques [5, 11, 12, 16, 23, 24]. More specific methods are also available to solve quadratically constrained programs, where all variables are continuous [2, 4, 17, 21]. These approaches can handle binary quadratic programming using identity $x_i^2 = x_i$. Hence, they are also able to handle (QP) by applying a binary expansion of each integer variable. This method will have to consider the large size of the equivalent binary quadratic program.

Other methods are available to obtain convex relaxations of mixed-integer quadratically constrained programs. A general technique for computing such relaxations is semi-definite programming [3]. A recent paper [22] proposes several ideas for keeping the tightness of these relaxations while improving their computation times.

References [19] and [20] provide effective approaches for solving mixed-integer quadratic problems with real variables and 0–1 variables. The considered problem consists in optimizing a quadratic function subject to quadratic constraints, but the quadratic parts of the objective function and constraints include only continuous variables. In contrast, the linear parts include both continuous variables and 0–1 variables.

We introduced in [8] the Mixed Integer Quadratic Convex Reformulation (MIQCR) approach. This method handles mixed-integer quadratic problems with linear equality constraints only. The idea of MIQCR is to design the tightest possible equivalent program to (QP) with a convex objective function, within a convex reformulation scheme. This best equivalent problem can be computed using the dual solution of a semidefinite relaxation of the initial problem, and further solved by a branch-and-bound algorithm based on quadratic convex relaxation.

In this paper, we present a method to solve (QP) based on the reformulation of the original problem into an equivalent quadratic problem whose continuous relaxation is convex. This new method handles quadratic constraints. At this aim, we consider a different reformulation scheme than in MIQCR. This scheme allows further extension to the case where some of the variables are continuous.

The structure of the paper is as follows. In Sect. 2, we introduce a new family of equivalent formulations to (QP). Each of these equivalent formulations has a convex continuous relaxation.

In Sect. 3, we focus on finding the tightest equivalent formulation within this family. We show that this best equivalent formulation can be deduced from a semidefinite relaxation to (QP), and that, surprisingly, it consists in linearizing all the constraints.

In Sect. 4, we study the equality constrained case. After a brief recall of the MIQCR method, we highlight its links with our current work. Moreover, we prove another interesting result: for equality constraints, any linear or quadratic convex reformulation of these constraints can be used to build the best reformulation.

In Sect. 5, we show how the whole framework can be extended to the case of mixed-integer variables, with the restriction that the quadratic sub-functions of purely continuous variables are already convex.

Throughout this paper, we present some small numerical examples to illustrate different aspects of the method. In Sect. 6, we present computational results on various instances of (QP) to show the effectiveness of the approach. Section 7 draws a conclusion.

Notation

The following notation is used throughout the paper. We denote by v(P) the optimal value of a mathematical program (P). For a vector $u \in {\mathbb {R}}^n$, diag(u) denotes a diagonal matrix whose ${ i}{\mathrm{th}}$ diagonal element equals $u_i$. We denote by ${\mathcal {S}}_n$ the set of $n \times n$ symmetric matrices, by ${\mathcal {S}}_n^+$ the set of positive semidefinite matrices of ${\mathcal {S}}_n$ and $M \succeq 0$ means that $M \in {\mathcal {S}}_n^+$. We also denote by ${\mathbf {0}}_n$ the zero $n \times n$ matrix and by $I^2$ the Cartesian product of a set I by itself.

2 A general family of convex equivalent formulations to (QP)

In this section, we introduce a family of equivalent formulations to (QP). These formulations use additional variables $y_{ij}$ that are enforced, by linear constraints, to be equal to the product $x_ix_j$. Any quadratic function is then formulated as a sum of a quadratic function of the x variables and a linear function of the y variables.

Equivalent formulation of the quadratic functions

We first introduce $n^2$ new variables y that will satisfy $y_{ij}=x_ix_j \quad \forall (i,j) \in I^2$, or, equivalently $Y=xx^T$.

Then, for $r=0, \ldots ,m$ we consider a positive semidefinite matrix $S_r \in {\mathcal {S}}_n^+$ and replace the quadratic function $f_r(x)$ by a convex function $f_{r,S_r}(x,Y)$ that is equal to $f_r$ under the condition $Y=xx^T$. We define function $f_{r,S_r}(x,Y)$ as follows :

$$\begin{aligned} f_{r,S_r}(x,Y) = \langle S_r, xx^T \rangle +c_r^Tx + \langle Q_r - S_r , Y \rangle \quad \quad \forall \,\, r = 0, \ldots ,m \end{aligned}$$

Hence, problem (QP) is equivalently stated as:

Because matrices $S_r$ are positive semidefinite, functions $f_{r,S_r}(x,Y)$ are convex.

Linearization of the quadratic constraints $Y=xx^T$ [7]

We now concentrate our effort on replacing Constraints (3) together with (1) and (2) by a set of linear inequalities. For this, each variable $x_i$ is replaced by its unique binary decomposition $x_i = \sum _{k=0}^{\lfloor \log (u_i)\rfloor } 2^k t_{ik}$, we can then express the product $y_{ij}$ of two variables $x_i$ and $x_j$ as a linear function of the products of a variable x by a variable t: $y_{ij} = \sum _{k=0}^{\lfloor \log (u_i)\rfloor } x_j2^k t_{ik}$. These products are then linearized by replacing them with a variable z and adding the appropriate linear constraints. To get closer to the convex hull, we furthermore add the McCormick inequalities [18]. We obtain the following set $P_{xYzt}$:

where $E=\{(i,k) \,:\, i=1,\ldots ,n,\,\,k=0,\ldots \lfloor \log (u_i) \rfloor \}$. The number of binary variables is $N=|E|= n+ {\sum _{i=1}^n}(\lfloor \log (u_i)\rfloor )$ and the number of real variables is $n+n^2 +nN$, so that the set $P_{xYzt}$ has $O( nN )$ variables and constraints.

The family of integer convex quadratic equivalent formulations to (QP)

To sum up, for any set of positive semidefinite matrices $S_r$ ($r=0, \ldots ,m$), we replace Constraints (1)-(3) by the set $P_{xYzt}$. We obtain the following equivalent problem to (QP):

Hence, we built an infinite family of equivalent problems to (QP).

The advantage of $({ QP}_{S_0, \ldots , S_m})$ is that the only non-convexity comes from the integrality constraints $t_{ik} \in \{0, 1\}$. Relaxing these constraints leads to a quadratic convex optimization problem which optimal value can be computed in polynomial time. Hence, problem $({ QP}_{S_0, \ldots , S_m})$ can for example be handled by a mixed-integer quadratic programming solver which performs a branch-and-cut algorithm to solve it.

This general family of reformulations includes two extreme cases. The first one is $S_r=Q_r$, when all $Q_r$ matrices are already positive semidefinite. In that case, functions $f_r(x)$ are left unchanged. The second one is when all $S_r$ are zero-matrices. In this case, the reformulation consists in replacing each product of two x variables by a Y variable. This amounts to a complete linearization [1], a classical approach in discrete quadratic optimization.

3 Computing the best convex equivalent formulation

In this section, we will focus on finding the positive semidefinite matrices $S^*_0, \ldots , S^*_m$ such that the continuous relaxation bound of problem $({ QP}_{S_0, \ldots , S_m})$ is as tight as possible.

Let us first recall a result already proved in [8] (Theorem 1). In $P_{xYzt}$, replace the integrality constraints $t_{ik} \in \{0, 1\}$ by $t_{ik} \in [0, 1]$ and project the obtained polyhedron on variables x and Y. The projected polyhedron is the following $\overline{P}_{xY}$:

Hence, since variables z and t are not in the objective function, the continuous relaxation optimal value of $({ QP}_{S_0, \ldots , S_m})$ can be computed by solving the following smaller problem $({ RQP}_{S_0, \ldots , S_m})$ with x and Y variables only:

We want to find positive semidefinite matrices $S_0^*, \ldots , S_m^*$ such that the continuous relaxation value of $({ QP}_{S_0^*, \ldots , S_m^*})$ is maximized. This amounts to solving the following problem $({ CP})$:

3.1 Finding an optimal solution to $({ CP})$

Here, we prove that an optimal solution to $({ CP})$ can be deduced from a dual solution of the following program $({ SDP})$ which is also a semidefinite relaxation of (QP). More precisely, to build $({ SDP})$ we perform a classical semidefinite relaxation of (QP), and we add McCormick inequalities (13)–(16) [18], and inequalities (17) that are satisfied since $x_i \in {\mathbb {N}}$.

Theorem 1

The optimal value of $({ CP})$ is equal to the optimal value of $({ SDP})$.

Proof

$\diamond$ Let us firstly prove that $v({ CP}) \le v({ SDP})$

Let $\bar{S}_0 ,\ldots , \bar{S}_m \in {\mathcal {S}}_n^+$ be any feasible solution to $({ CP})$. To prove that $v({ CP}) \le v({ SDP})$ we prove that from any feasible solution $(\bar{X},\bar{x})$ to $({ SDP})$, we can build a feasible solution (x, Y) to $({ RQP}_{\bar{S}_0, \ldots , \bar{S}_m})$ with a lower objective value, i.e., satisfying $\langle \bar{S}_0, \bar{x}\bar{x}^T\rangle +c_0^T\bar{x} + \langle Q_0 - \bar{S}_0 , \bar{X} \rangle \le f(\bar{X}, \bar{x})$.

• i) Take $x=\bar{x}$. Variables Y can be seen as a symmetric matrix, so we can take $y_{ij}=\bar{X}_{ij}$, $\forall (i,j) \in I^2$. We prove that this solution (x, Y) is feasible to $({ RQP}_{\bar{S}_0, \ldots , \bar{S}_m})$. Constraints(4)-(9) are obviously satisfied. We now prove that Constraints (10) are satisfied. We have:

  

• ii) Prove that $\langle \bar{S}_0, \bar{x}\bar{x}^T\rangle +c_0^T\bar{x} + \langle Q_0 - \bar{S}_0 , \bar{X} \rangle - \langle Q_0 , \bar{X} \rangle - c_0^T\bar{x} \le 0$ or that $\langle \bar{S}_0 , \bar{x}\bar{x}^T -\bar{X} \rangle \le 0$. This last inequality follows from $\bar{S}_0 \succeq 0$ and $\bar{x}\bar{x}^T - \bar{X}\preceq 0$.

$\diamond$ Let us secondly prove that $v({ CP}) \ge v({ SDP})$ or equivalently $v({ CP}) \ge v({ DSDP})$ where $({ DSDP})$ is the dual of $({ SDP})$. The following problem $({ DSDP})$ is the dual of $({ SDP})$:

where $\alpha \in {\mathbb {R}}^m_+$ are the dual variables associated to constraints (12), and $\varPhi ^i$, $i=1,\ldots ,4$ are the positive semidefinite matrices built from the dual variables $\theta$ associated with constraints (13), (14), (15), (16), respectively. For instance, if $\theta ^1_{ij}$ is the dual variable associated to constraint (13), then $\varPhi ^1_{ij} = \varPhi ^1_{ji} = \frac{\theta ^1_{ij}}{2}$ for $i<j$, and $\varPhi ^1_{ii} = \theta ^1_{ii}$. $\varphi$ are the dual variables associated to constraints (17). As mentioned in Constraint (21) we have $\varPhi = \varPhi ^1 + \varPhi ^2 - \varPhi ^3- \varPhi ^4- diag(\varphi )$.

Let $(\bar{\alpha },\bar{\varPhi }^1,\bar{\varPhi }^2,\bar{\varPhi }^3, \bar{\varPhi }^4,\bar{\varphi })$ be a feasible solution to $({ DSDP})$ and, by Constraint (21), let $\bar{\varPhi }= \bar{\varPhi }^1+\bar{\varPhi }^2-\bar{\varPhi }^3-\bar{\varPhi }^4 - diag(\bar{\varphi })$, then we build the following positive semidefinite matrices:

$(\bar{S}_0, \ldots ,\bar{S}_m)$ form a feasible solution to $({ CP})$. The objective value of this solution is equal to $v({ RQP}_{\bar{S}_0, \ldots , \bar{S}_m})$.

We now prove that $v({ RQP}_{\bar{S}_0, \ldots , \bar{S}_m}) \ge v({ DSDP})$. For this, we prove that for any feasible solution $(\bar{x},\bar{Y})$ to $({ RQP}_{\bar{S}_0, \ldots , \bar{S}_m})$, the associated objective value is not smaller than $g(\bar{\alpha },\bar{\varPhi })$. Denote by $\varDelta$ the difference between the objective values, i.e., $\varDelta = \langle \bar{S}_0 ,\bar{x}\bar{x}^T \rangle +c_0^T\bar{x} + \langle Q_0 - \bar{S}_0 , \bar{Y} \rangle - g(\bar{\alpha },\bar{\varPhi })$. We below prove that $\varDelta \ge 0$

$$\begin{aligned} \varDelta&= \langle \bar{S}_0 , \bar{x}\bar{x}^T \rangle +c_0^T\bar{x} + \langle Q_0 - \bar{S}_0 , \bar{Y} \rangle + \displaystyle {\sum _{r=1}^m \bar{\alpha }_r} b_r+ \langle \bar{\varPhi }^3, uu^T \rangle \\&\ge c_0^T\bar{x} - \langle \displaystyle {\sum _{r=1}^m} \bar{\alpha }_r Q_r + \bar{\varPhi } , \bar{Y} \rangle +\displaystyle {\sum _{r=1}^m \bar{\alpha }_r} b_r+ \langle \bar{\varPhi }^3, uu^T \rangle \quad \text{ since } \bar{S}_0 \succeq 0\\&= c_0^T\bar{x} + \displaystyle {\sum _{r=1}^m} \bar{\alpha }_r ( b_r - \langle Q_r , \bar{Y} \rangle ) - \langle \bar{\varPhi }, \bar{Y} \rangle + \langle \bar{\varPhi }^3, uu^T \rangle \\&\ge c_0^T\bar{x} + \displaystyle {\sum _{r=1}^m} \bar{\alpha }_r c^T_r \bar{x} - \langle \bar{\varPhi }, \bar{Y} \rangle + \langle \bar{\varPhi }^3, uu^T \rangle \end{aligned}$$

as $c_r^T \bar{x} + \langle Q_r ,\bar{Y} \rangle \le b_r$ and $\bar{\alpha }_r \ge 0$. Moreover, by Constraint (21) we get:

$$\begin{aligned} \varDelta&\ge c_0^T\bar{x} + \displaystyle {\sum _{r=1}^m} \bar{\alpha }_r c^T_r \bar{x} - \langle \bar{\varPhi }^1 + \bar{\varPhi }^2 - \bar{\varPhi }^3 - \bar{\varPhi }^4 - diag(\bar{\varphi }) , \bar{Y} \rangle + \langle \bar{\varPhi }^3, uu^T \rangle \\&\ge c_0^T\bar{x} + \displaystyle {\sum _{r=1}^m} \bar{\alpha }_r c^T_r \bar{x} - \langle \bar{\varPhi }^1, \bar{Y} \rangle - \langle \bar{\varPhi }^2, \bar{Y} \rangle + \langle \bar{\varPhi }^3, \bar{Y} + uu^T\rangle \\&\quad +\, \langle \bar{\varPhi }^4, \bar{Y} \rangle + \langle diag(\bar{\varphi }), \bar{Y} \rangle \end{aligned}$$

By Constraints (4)–(9), and since all the coefficients of $\bar{\varPhi }^1,\bar{\varPhi }^2 ,\bar{\varPhi }^3,\bar{\varPhi }^4$, and $\bar{\varphi }$ are non-negative, we get:

$$\begin{aligned} \varDelta&\ge c_0^T\bar{x} + \displaystyle {\sum _{r=1}^m} \bar{\alpha }_r c^T_r \bar{x} - \langle \bar{\varPhi }^1, \bar{x}^Tu \rangle - \langle \bar{\varPhi }^2, \bar{x}^Tu \rangle + \langle \bar{\varPhi }^3, 2\bar{x}^Tu \rangle + \bar{\varphi }^T \bar{x} \\&\ge \Bigl ( c_0 + \displaystyle {\sum _{r=1}^m} \bar{\alpha }_r c_r - (\bar{\varPhi }^1 + \bar{\varPhi }^2 -2 \bar{\varPhi }^3)^Tu + \bar{\varphi } \Bigr )^T \bar{x} \\&\ge 0 \qquad \quad \text{ since } \bar{x} \ge 0 \text{ and } \text{ by } \text{ Constraint } \text{(20). } \end{aligned}$$

$\square$

From the proof of Theorem 1, we can characterize an optimal solution to $({ CP})$.

Corollary 1

An optimal solution $S^*_r$, $r = 0,\ldots , m$ to $({ CP})$ amounts to linearizing the constraints by taking

$$\begin{aligned} S^*_r={\mathbf {0}}_n \quad \text { for } r=1, \ldots , m \end{aligned}$$

and, for the objective function, we take

$$\begin{aligned} S^*_0 = Q_0 + \displaystyle {\sum _{r=1}^m} \alpha ^*_r Q_r + \varPhi ^* \end{aligned}$$

where $\alpha ^*_r$ and $\varPhi ^*$ are computed from an optimal solution of the dual $({ DSDP})$ of the semidefinite programming problem $({ SDP})$:

• i) $\alpha ^*$ is the vector of optimal dual variables associated with constraints (12) of $({ SDP})$,

• ii) $\varPhi ^*_{ij}$ are computed as $\varPhi _{ij}^* = \varPhi _{ij}^{1*}+ \varPhi _{ij}^{2*}- \varPhi _{ij}^{3*}- \varPhi _{ij}^{4*}$, for $i \ne j$, and $\varPhi _{ii}^* = \varPhi _{ii}^{1*}+ \varPhi _{ii}^{2*}- \varPhi _{ii}^{3*} - \varPhi _{ii}^{4*} - \varPhi _{i}^{5*}$, where $\varPhi ^{1*}$, $\varPhi ^{2*}$, $\varPhi ^{3*}$, $\varPhi ^{4*}$ are the symmetric matrices built from the optimal dual variables associated with constraints (13), (14), (15), (16), respectively, and $\varPhi ^{5*}$ the vector of dual variables associated with constraints (17).

To sum up, let us write the optimal equivalent formulation:

A discussion on the optimal equivalent formulation

An important fact is that the continuous relaxation value of program $({ QP}^*)$ is equal to the optimal value of the semi-definite relaxation $({ SDP})$. Hence, in a branch-and-bound algorithm for solving $({ QP}^*)$, the root-node gap is the same as the SDP-relaxation gap which is known to be strong. In [6], quadratic programs with continuous bounded variables are considered and this SDP relaxation, without Constraints (17) which is specific to the integer variables case, is called “Shor plus RLT” relaxation. It is recalled in [6] that this relaxation dominates six other considered SDP relaxations. It is further shown that it provides the same bound as the doubly nonnegative relaxation.

In presence of a linear inequality $a^T x \le b$, we consider it as a quadratic constraint with a zero quadratic part. Moreover, in order to improve the tightness of the relaxation, we add the following quadratic inequality $x^Taa^Tx \le b^2$.

3.2 A solution algorithm for (QP)

From Theorem 1 and Corollary 1, we can deduce Algorithm 1 to solve (QP).

3.3 Illustrative examples

In this section, we first examine the solution of an example by Algorithm 1. Then, we show on a convex example that Algorithm 1 can lead to a tighter continuous relaxation bound than the direct solution by Cplex [14].

Illustration of Algorithm 1

Consider the following example whose optimal value is equal to $-1872$ for $x^*=(9,0,20,14)$:

Following Algorithm 1, we first solve the semidefinite relaxation $({ SDP}_{Ex})$:

We obtain the following optimal dual solution:

• $\alpha _1^* = 0.3773$

• $\varPhi ^* = {\left( \begin{array}{cccc} 0 &{}\quad 0.31 &{}\quad -0.18 &{}\quad 0 \\ 0.31 &{}\quad 1.32 &{}\quad -1.00 &{}\quad -1.36 \\ -0.18 &{}\quad -1.00 &{}\quad 3.61 &{}\quad 0.89 \\ 0 &{}\quad -1.36&{}\quad 0.89 &{}\quad 0 \end{array}\right) }$

We build matrix $S_0^* = Q_0 + \alpha ^*_1 Q_1 + \varPhi ^*$, and we get: and then $Q_0 - S_0^* = {\left( \begin{array}{cccc} -3.02 &{}\quad -0.31 &{}\quad 0.18&{}\quad 0 \\ -0.31 &{}\quad -3.21 &{}\quad -0.51 &{}\quad 0.61 \\ 0.18 &{}\quad -0.51 &{}\quad -3.61 &{}\quad -0.89 \\ 0 &{}\quad 0.61 &{}\quad -0.89 &{}\quad -0.75 \\ \end{array}\right) }$

Then, to solve (Ex), we reformulate it into the following quadratic program with linear constraints $(Ex^*)$

The continuous relaxation value of $(Ex^*)$ is equal to $-1887.32$, the initial gap is thus of 0.82 %. The continuous relaxation value of the complete linearization (i.e. $S_0 = {\mathbf {0}}_n$) of (Ex) is equal to $-2148.83$ leading to a gap of 14.79 %.

Improving the continuous relaxation bound for already convex instances

Through this instance, we illustrate the interest of using our algorithm for convex instances. We consider the instance available at www.cedric.cnam.fr/~lamberta/Library/IQCP_MIQCP/convex_instance.dat. This instance has 30 binary variables, 1 quadratic and convex inequality constraint and a linear objective function. For this instance we obtain the following results:

• Optimal value of the instance: 0

• Optimal value of the continuous relaxation: $-8.18$

• Optimal value of the continuous relaxation after reformulation by a complete linearization (i.e. $S_r={\mathbf {0}}_{n}$, $r=0, \ldots , m$): $-34.41$

• Optimal value of the continuous relaxation after reformulation by our algorithm: $-3.078$

The continuous relaxation of this instance is a convex problem. Hence, a first bound $b_1$ can be computed by solving this problem. Our approach computes a bound $b_2$ such that $b_2 \ge b_1$ and possibly $b_2 > b_1$ as in this example. Observe that $b_1$ is the minimum of a linear function subject to one quadratic constraint, while $b_2$ is the minimum of a quadratic function subject to linear constraints.

4 The case of equality constraints

In this section, we study the case where the initial problem contains some quadratic equality constraints. First, we briefly recall the MIQCR method [8] for the purely integer case. This method can handle the following class of problems:

By use of a scalar parameter $\alpha$ and of a matrix parameter $\varPhi$, we build the following family of quadratic equivalent formulations to (P):

We then compute the parameters $\alpha ^*$ and $\varPhi ^*$ that give the tightest possible equivalent program to (P), and where the reformulated objective function is convex. These best parameters are deduced from the dual solution of a semidefinite problem that is similar to $({ SDP})$.

Below, we highlight the links between our current work and the MIQCR method. We show that, in the case of linear equality constraints, our reformulation $({ QP}^*)$ can be viewed as an extension of the MIQCR method. Then, we prove that, unlike for quadratic inequalities, any positive semidefinite matrices can be used to reformulate the quadratic equalities to obtain the tightest equivalent formulation.

4.1 Application of our new method in the presence of quadratic equalities and links to the MIQCR method

Without loss of generality, we consider that the two first inequalities in (QP) come from a single equality which was previously rewritten as two inequalities. More formally, the quadratic constraints in (QP) are precisely:

and the two first inequalities come from the equality $\langle Q_1, xx^T \rangle + c_1^Tx = b_1$.

The optimally reformulated problem described in Corollary 1 is in this case:

where

$$\begin{aligned} S^*_0 = Q_0 + (\alpha _1^*- \alpha _2^*)Q_1 + \displaystyle {\sum _{r=3}^m} \alpha _r^*Q_r + \varPhi ^* \end{aligned}$$

and the first two inequalities are equivalent to the equality $\langle Q_1, Y \rangle + c_1^Tx = b_1$.

Observation 1

For any feasible solution (x, Y) to problem $({ QP}^*)$, we have:

$$\begin{aligned} f_{0,S^*_0}(x,Y)&= \langle S^*_0 , xx^T \rangle + c^T_0 x + \langle Q_0 - S^*_0, Y \rangle \\&= \langle Q_0 , xx^T \rangle + c_0^Tx + \langle S_0^* -Q_0 , xx^T- Y \rangle \\&= \langle Q_0 , xx^T \rangle +c_0^Tx + \langle \varPhi ^* , xx^T- Y \rangle +\, \displaystyle {\sum _{r=3}^m} \alpha ^*_r \langle Q_r, xx^T- Y \rangle \\&\quad +(\alpha ^*_1-\alpha ^*_2) \langle Q_1, xx^T- Y \rangle \\&= \langle Q_0 , xx^T \rangle +c_0^Tx + \langle \varPhi ^* , xx^T- Y \rangle + \displaystyle {\sum _{r=3}^m} \alpha ^*_r \langle Q_r, xx^T- Y \rangle \\&\quad +\, (\alpha ^*_1-\alpha ^*_2) \Bigl ( \langle Q_1, xx^T \rangle + c_1^Tx - b_1 \Bigr ) \end{aligned}$$

We can notice that the last term of the above calculation is the initial equality constraint multiplied by an unsigned scalar parameter $\nu = \alpha ^*_1 - \alpha ^*_2$. Hence, if equality constraints are considered in the initial formulation and when we build the optimal solution $(S^*_0, \ldots , S^*_m)$ as in Corollary 1, it amounts to explicitely integrating equality constraints into the objective function multiplied by a scalar parameter.

Observation 1 brings us back to the spirit of MIQCR. Indeed, in the MIQCR method, we integrate in the objective function a set of quadratic functions multiplied by a scalar parameter $\alpha$. Thus, for the equality case, this new family of convex reformulations can be viewed as an extension of the MIQCR method.

4.2 Optimal equivalent reformulations for equality constraints

Here, we start by considering a slightly different reformulation scheme where we explicitly integrate the quadratic inequalities into the objective function. We show that, within this scheme, the equivalent reformulated equalities can be any convex functions.

Without loss of generality, we consider the case of just one equality which corresponds to the first two inequalities. Following the same developments as in Sect. 3, we obtain the corresponding relaxed problem $({ RQP}_{\nu , S_0,S_1,S'_1,S_3 \ldots , S_m})$ where the equality constraint is lifted in the objective function weighted by a scalar $\nu$:

Finding the best formulation amounts to solving problem $({ CP}')$:

We prove in Theorem 2 that when quadratic equalities are explicitely integrated in the objective function, in an optimal solution to $({ CP}')$, matrices $S_1$ and $S'_1$ associated to the equality constraint can be any positive semidefinite matrices.

Theorem 2

Let $(\nu ^*,S^*_0, S^*_1, S^{'*}_1,S^*_3, \ldots ,S^*_m)$ be an optimal solution to $({ CP}')$, then for any semi-definite matrices $\bar{S}_1$, $\bar{S}'_1$, the solution $(\nu ^*,S^*_0,\bar{S}_1,\bar{S}'_1,S^*_3, \ldots ,S^*_m)$ is also an optimal solution to $({ CP}')$.

Proof

To prove that, in an optimal solution to $({ CP}')$, matrices $S_1$ and $S'_1$ can be any semi-definite matrices, we prove that solving $({ CP}')$ is equivalent to solving the following problem $({ CP}^1)$:

where $({ RQP}^1_{\nu , S_0,S_3 \ldots , S_m})$ is $({ RQP}_{\nu , S_0,S_1,S'_1,S_3 \ldots , S_m})$ without Constraints (24) and (25).

$\diamond$ We first prove that $v(CP') \ge v(CP^1)$. This follows from the immediate observation that $v({ RQP}_{\nu , S_0,S_1,S'_1,S_3 \ldots , S_m}) \ge v({ RQP}^1_{\nu ,S_0,S_3, \ldots , S_m})$.

$\diamond$ We now prove that $v({ CP}') \le v({ CP}^1)$, or equivalently that $v({ DCP}') \le v({ CP}^1)$, where $({ DCP}')$ is the following problem:

where $({ RQP}^2_{\nu , S_0,S_1,S_1',S_3 \ldots , S_m,\lambda _1,\lambda _2})$ is:

$({ DCP}')$ is obtained from $({ CP}')$ by dualizing Constraints (24) and (25). By convexity, $({ DCP}')$ and $({ CP}')$ have the same optimal values.

Let $(\nu ^*,S^*_0, S^*_1, S^{'*}_1,S^*_3, \ldots ,S^*_m,\lambda ^*_1,\lambda ^*_2)$ be an optimal solution to $({ DCP}')$. We build the following feasible solution $(\bar{\nu },\bar{S}_0,\bar{S}_3, \ldots , \bar{S}_m)$ to $({ CP}^1)$:

• $\bar{S}_0 = S^*_0 + \lambda ^*_1S^*_1 + \lambda ^*_2 S^{'*}_1 + (\lambda ^*_2 - \lambda ^*_1)Q_1$

• $\bar{S}_r = S^*_r$,   $r= 3, \ldots , m$

• $\bar{\nu } = \nu ^* + \lambda ^*_1 - \lambda ^*_2$

$(\bar{\nu },\bar{S}_0,\bar{S}_3, \ldots , \bar{S}_m)$ is feasible to $({ CP}^1)$. Indeed, $\bar{S}_r$, $r= 3, \ldots , m$ are positive semidefinite matrices. Moreover, $\bar{S}_0 + \bar{\nu } Q_1 =S^*_0 + \lambda ^*_1S^*_1 + \lambda ^*_2 S^{'*}_1 +(\lambda ^*_2 - \lambda ^*_1) Q_1+ (\nu ^* + \lambda ^*_1 - \lambda ^*_2)Q_1 = S^*_0 + \nu ^*Q_1 + \lambda ^*_1S^*_1 + \lambda ^*_2 S^{'*}_1$ is positive semidefinite since $S^*_0 + \nu ^*Q_1 \succeq 0$, $S^*_1,S^{'*}_1 \succeq 0$ and $\lambda ^*_1, \lambda ^*_2 \ge 0$.

The objective function value of the associated problem $({ RQP}^1_{\bar{\nu }, \bar{S}_0,\bar{S}_3 \ldots , \bar{S}_m})$ is:

Therefore, $v({ RQP}^1_{\bar{\nu }, \bar{S}_0,\bar{S}_3 \ldots , \bar{S}_m}) = v({ RQP}^2_{\nu ^*, S^*_0,S^*_1,S^{'*}_1,S^*_3 ,\ldots , S^*_m,\lambda ^*_1,\lambda ^*_2})$ as these two problems have the same objective functions and the same set of constraints. $\square$

Let us now state Corollary 2 that, as claimed in the beginning of the section, shows that for any equivalent reformulated equality constraints the value of the best reformulation is reached.

Corollary 2

$v({ CP}') = v({ SDP}) = v({ CP})$

Proof

We know by Theorem 1 that $v({ CP}) = v({ SDP})$. Moreover, by convexity and by dualizing the first two inequalities of $({ SDP})$ which are equivalent to the equality $\langle Q_{1}, X\rangle + c^T_{1}x = b_1$, we obtain $v({ SDP}) = v({ CP}^1)$. Thus, as $v({ CP}') = v({ CP}^1)$ by Theorem 2, we obtain $v({ CP}') = v({ SDP})$. $\square$

5 Extension to the mixed-integer case

In this section, we study the case where some of the variables in the initial problem are continuous. More formally, we aim to solve the following problem:

where $\forall \,\, r \in \{ 0, \ldots , m\}$, $f_r(x) = \langle Q_r , xx^T \rangle + c^T_r x$, $Q_r \in {\mathcal {S}}_N$, $c_r \in {\mathbb {R}}^{N}$, $b_r \in {\mathbb {R}}$, $I=\{1,\ldots ,n\}$, $J=\{n+1,\ldots ,N\}$, and $u_i \in {\mathbb {N}}\, (i \in I)$, $u_j \in {\mathbb {R}}\, (j \in J)$.

We denote by ${\fancyscript{H}}$ the set of pairs of indices of variables x involving at least one integer variable:

$$\begin{aligned} {\fancyscript{H}}= \{(i,j) \in I^2 \cup (I \times J) \cup (J \times I) \} \end{aligned}$$

Definition 1

For any matrix $A \in {\mathcal {S}}_N$, we define the following decomposition of A into two matrices $M_A \in {\mathcal {S}}_N$ and $C_A \in {\mathcal {S}}_N$ such that:

$$\begin{aligned} A = M_A + C_A \end{aligned}$$

where the terms of $M_A$, for $(i,j) \in J^2$, are zeros and the terms of $C_A$, for $(i,j) \in {\fancyscript{H}}$, are zeros.

An illustration of Definition 1 is presented in Fig. 1. The aim of this definition is to formalize the decomposition of the quadratic function $x^TAx$ into the sum of the quadratic sub-function with the real variables only $x^TC_Ax$ and the other quadratic sub-function $x^TM_Ax$. Of course, for any vector x, $x^TAx=x^TM_Ax+ x^TC_Ax$.

Fig. 1

Decomposition of a matrix A into matrices ${ M_A}$ and ${ C_A}$

Assumption 1

We make the assumption that for all $r=0, \ldots , m$, $C_{Q_r} \succeq 0$, i.e. the quadratic sub-functions $x^TC_{Q_r}x$ of real variables are convex functions.

In the following, we first present the extension of Algorithm 1 to the case where $C_{Q_r} = {\mathbf {0}}_{N}$ for $r=1, \ldots , m$, i.e., in the constraints, there are no quadratic sub-functions of real variables. Then, we deduce an algorithm to solve $({ MQP})$ in the more general case where the quadratic sub-functions of real variables are convex functions.

5.1 The case where the quadratic sub-functions of real variables of constraints are zero-functions ($C_{Q_0} \succeq 0$, and for $r=1, \ldots , m$, $C_{Q_r} = {\mathbf {0}}_{N}$)

In this section, we suppose that, in the constraints, there are no quadratic terms involving two real variables, i.e. that $\forall r=1, \ldots , m$, $C_{Q_r} = {\mathbf {0}}_{N}$. We now present our algorithm following the same reasoning steps as for the pure integer case.

As in Sect. 2, we introduce additional variables $y_{ij}$, but these variables are defined only for $(i,j) \in {\fancyscript{H}}$ (set of indices of products involving at least one integer variable). Furthermore, we consider semidefinite matrices $S_0, \ldots , S_m \in {\mathcal {S}}_N$ such that for all $r=0, \ldots , m$, $S_r = M_{S_r} + C_{S_r}$ with $C_{S_r} = {\mathbf {0}}_{N}$.

The following program $({ MQP}_{S_0, \ldots , S_m})$ is equivalent to $({ MQP})$:

where $P'_{xYzt}$ is:

We now define the semidefinite program $({ SDP}')$ which is obtained from $({ SDP})$ by replacing in Constraints (13)–(16) $(i,j) \in I^2$ by $(i,j) \in {\fancyscript{H}}$. This substitution amounts to not considering these constraints for pairs of real variables.

Theorem 3

Let $(\alpha ^*,\varPhi ^*)$ be an optimal dual solution to $({ SDP}')$, where $\varPhi ^*$ is the symmetric matrix built as described in Theorem 1 from the optimal dual variables associated to new Constraints (13)–(16), and $\alpha ^*$ is the vector of optimal dual variables associated to Constraints (12). We build $S^*_0$ as follows:

$$\begin{aligned} S^*_0 = M_{S^*_0} + C_{S^*_0}\,\quad \mathrm{where}\,M_{S^*_0} = M_{Q_0} + \displaystyle {\sum _{r=1}^m} \alpha ^*_r M_{Q_r} + M_{\varPhi ^*}\,\mathrm{and}\,C_{S^*_0} = C_{Q_0} \end{aligned}$$

The optimal value of $({ MQP}^*)= ({ MQP}_{S^*_0, {\mathbf {0}}_N, \ldots ,{\mathbf {0}}_N})$ is equal to the optimal value of $({ SDP}')$.

The proof can be deduced from the proof of Theorem 1.

5.2 The case where the quadratic sub-functions of real variables are arbitrary convex functions ($\forall r=0, \ldots , m$, $C_{Q_r} \succeq 0$)

To handle this case, we propose to first build the problem $({ MQP}1)$ from $({ MQP})$ by replacing constraints

$$\begin{aligned} c_r^T x + \langle M_{Q_r} , xx^T\rangle + \langle C_{Q_r} , xx^T\rangle \le b_r\quad&r=1,\ldots ,m \end{aligned}$$

by

$$\begin{aligned} c_r^T x + \langle M_{Q_r} , xx^T\rangle \le b_r&\quad r=1,\ldots ,m \end{aligned}$$

Although $({ MQP}1)$ is a relaxation of $({ MQP})$ (as a consequence of Assumption 1), we do not use this fact in the following.

Now, $({ MQP}1)$ falls in the case of Sect. 5.1. So, one can apply the reformulation of Sect. 5.1 to $({ MQP}1)$. We obtain a program $({ MQP}1^*)$ equivalent to $({ MQP}1)$ and whose continuous relaxation is a convex problem.

Finally, in each constraint of $({ MQP}1^*)$, we add back the quadratic sub-functions of real variables $\langle C_{Q_r} , xx^T \rangle$ and obtain problem $({ MQP}^*)$ as an equivalent problem to $({ MQP})$. More formally, the constraints of $({ MQP}^*)$ have the following form:

$$\begin{aligned} c_r^T x +\langle M_{Q_r} , Y \rangle + \langle C_{Q_r} , xx^T \rangle \le b_r \end{aligned}$$

The sequence of transformations is illustrated in Fig. 2. The algorithm is presented in Algorithm 2, where Step 1 corresponds to item (i) of Fig. 2, Step 2 to item (ii), and Step 3 to item (iii).

Fig. 2

Illustration of the sequence of transformations

5.3 An illustrative example

We consider here the same example as for the pure-integer case (Sect. 3.3) where we relax the integrality constraint of variable $x_4$. This example, which we call $({ MEx})$, has an optimal value equal to $-1884.97$ for $x^*= (9,0,20,14.7)$:

Following Algorithm 2, we first solve the semidefinite relaxation $({ SDP}'_{{ MEx}})$:

The optimal value of $({ SDP}'_{{ MEx}})$ is equal to $-2031.995$. We obtain the following optimal dual solution:

• $\alpha _1^* = 0$

• $\varPhi ^* = {\left( \begin{array}{cccc} 1.89 &{}\quad 0.51 &{}\quad -0.21 &{}\quad 0.49 \\ 0.51 &{}\quad 2.20 &{}\quad 0.04 &{}\quad -0.95\\ -0.21 &{}\quad 0.04 &{}\quad 3.48 &{}\quad 1.01 \\ 0.49 &{}\quad -0.95&{}\quad 1.01 &{}\quad 0 \end{array}\right) }$

We build matrix $S_0^* = Q_0 + \alpha ^*_1 Q_1 + \varPhi ^*$, and we obtain: and thus $Q_0 - S_0^* = {\left( \begin{array}{cccc} -1.89 &{}\quad -0.51 &{}\quad 0.21&{}\quad -0.49 \\ -0.51 &{}\quad -2.20 &{}\quad -0.04 &{}\quad 0.95 \\ 0.21 &{}\quad -0.04 &{}\quad -3.48 &{}\quad -1.01 \\ -0.49 &{}\quad 0.95 &{}\quad -1.01 &{}\quad 0 \\ \end{array}\right) }$

Then, to solve $({ MEx})$, we reformulate it into the following quadratic program with a quadratic constraint $({ MEx}^*)$

The continuous relaxation value of $({ MEx}^*)$ is equal to $-1910.03$, the initial gap is thus of $1.33\,\%$.

6 Computational results

In this section, we present experiments on pure-integer (QP) and mixed-integer $({ MQP})$ quadratically constrained programs. We randomly generate pure-integer instances (${ IQCP_m}$, $m = 0, 1, 5$) and mixed-integer instances (${ MIQCP_m}$, $m = 1$) where m denotes the number of quadratic inequalities. All instances are available at www.cedric.cnam.fr/lamberta/Library/iqcpmiqcp.html [15]. Both for pure-integer $({ IQCP_m})$ and mixed integer $({ MIQCP_m})$ instances we compare an exact algorithm applied to our best reformulation $({\textit{QP}}^{*}/{\textit{MQP}}^{*})$ and an exact algorithm applied to the complete linearization $({ LP}/{ LQP})$ defined by taking $S_r = {\mathbf {0}}_n$ , for $r = 0, \ldots ,m$. More precisely, $({ LP})$ and $({ LQP})$ consist in linearizing all quadratic terms involving an integer variable and keeping all the products of two real variables. In the pure integer case, $({ LP})$ has a linear objective function and linear constraints. In the mixed case, $({ LQP})$ has a quadratic objective function and quadratic constraints, where the quadratic terms of all functions are the initial convex sub-functions of real variables.

Experimental environment:

Our experiments were carried out on a laptop with an Intel core i7 processor of 2 GHz and 8 GB of RAM using a Linux operating system.

For solving the semidefinite programs $({ SDP})$ and $({ SDP}')$ we use CSDP [9], where programs are solved with a precision of $10^{-6}$.

For solving convex reformulated programs $({ QP}^*)$, $({ MQP}^*)$, $({ LP})$, and $({ LQP})$, we use the solver Cplex version 12.5.0 [14], where programs are solved with a precision of $10^{-8}$ and a time limit of 3 h. For our experiments, we use the multithreading mode of Cplex with up to 4 threads.

Legends of Tables 1, 2, 3 and 4:

• Name: c_N_n_i, where c is the class of the instance, N is the number of variables, n is the number of integer variables and i the index of the instance.

• Opt: The optimal solution value of the instance or the best known solution which is obtained within the time limit of 3 h.

• Cont: The optimal value of the continuous relaxation of the reformulated problem.

• Gap: $\displaystyle \left| \frac{Opt - Cont }{Opt} \right| * 100$.

• Ref CPU (Reformulation CPU) : CPU time in seconds for solving $({ SDP})$ with CSDP [9].

• Cplex CPU : CPU time in seconds for solving $({ QP}^*)$, $({ MQP}^*)$, $({ LP})$, or $({ LQP})$ with Cplex [14].

• Tot CPU (Total CPU) : Ref CPU + Cplex CPU, for reformulations $({ QP}^*)$ and $({ MQP}^*)$, and Cplex CPU for reformulations $({ LP})$ and $({ LQP})$. The Total CPU time is limited to 3 h. If the optimum is not found within this time, we present the final gap $(g \%)$, $g = \displaystyle \left| \frac{Opt - b }{ Opt} \right| * 100$ where b is the best bound obtained within the time limit.

• Nodes: Number of nodes visited by the branch-and-bound algorithm.

Table 1 Results for the exact solution of instances $({ IQCP_1})$ by $({ QP}^*)$ and $({ LP})$

Table 2 Results for the solution of instances of class $({ IQCP_5})$ by $({ QP}^*)$ and $({ LP})$

Table 3 Results for the solution of instances of class $({ IQCP_0})$ by $({ QP}^*)$

Table 4 Results for the solution of instances of class $({ MIQCP_1})$ by $({ MQP}^*)$ and $({ LQP})$

6.1 Computational experiments on pure-integer instances

Instances $({ IQCP_m})$ with quadratic inequality constraints ($m = 1$ and $m=5$)

Our experiments were carried out on inequality constrained pure-integer instances of class $({ IQCP_m})$. Each instance consists of minimizing a quadratic function subject to m quadratic inequality constraints.

We generate instances where the coefficients of $({ IQCP_m})$ are randomly generated as follows:

• $\ell _i=0$ and $u_i=20$, for all $i \in I = \{1, \ldots , n \}$.

• The coefficients of $Q_0$ are integers uniformly distributed in the interval $[-5,5]$ with a density of 75 %. More precisely, $\forall (i,j) \in I^2 : i \le j$, we generate $q_{0ij} \in [-5,5]$, then $q_{0ji} = q_{0ij}$. We observe that the number of negative eigenvalues of the generated matrices is always close to 50 %.

• The coefficients of $Q_r$ are integers uniformly distributed in the interval [0, 10] with a density of 25 %. More precisely, $\forall (i,j) \in I^2 : i \le j$, we generate $q_{rij} \in [0,10]$, then $q_{rji} = q_{rij}$.

• $b_r =\lfloor 0.1 * ({\sum \nolimits _{i=1}^n\sum _{j=1}^n} q_{rij} u_i u_j) \rfloor$.

In these experiments, we fixed $m=1$ and $m=5$. For class $({ IQCP_1})$, we generate instances with $n= 10, 20, 30$, or 40, and for class $({ IQCP_5})$ we generate instances with $n = 10, 20$, or 30. For each n we generate 10 instances obtaining a total of 70 instances.

In Table 1, we compare the solution of instances of class $({ IQCP_1})$ by reformulations $({ LP})$ and $({ QP}^*)$. We can observe that the initial gap obtained with the reformulation $({ QP}^*)$ is always much smaller than the gap obtained by the reformulation $({ LP})$. More precisely, this gap is divided by a factor of 44 in average over all the instances. As a consequence, the number of nodes visited during the branch-and-bound algorithm is significantly smaller with reformulation $({ QP}^*)$ in comparison with reformulation $({ LP})$. Finally, reformulation $({ QP}^*)$ is faster than reformulation $({ LP})$ for instances with 20 variables or more. Moreover, reformulation $({ LP})$ is unable to solve instances of sizes 30 or 40.

In Table 2, we present results of class $({ IQCP_5})$. The initial gap is much smaller with $({ QP}^*)$ than with $({ LP})$ since it is divided by a factor of about 13.5. However, this improvement is not as significant as in the case of instances $({ IQCP_1})$. We can also notice that the average gap increases with sizes of problems for reformulation $({ LP})$, while it remains quite stable for reformulation $({ QP}^*)$. Regarding the total CPU time, we find that both approaches are comparable for instances with 10 or 20 variables. However, the solution of instances with 30 variables is much faster with reformulation $({ QP}^*)$ than with reformulation $({ LP})$. Thus $({ QP}^*)$ solves eight instances of 30 variables, out of 10, while $({ LP})$ solves none of them. We do not present results for $n=40$ because for this size the reformulation phase becomes too difficult with the SDP solvers available to us. Indeed, standards SDP solvers were not able to solve $({ SDP})$ for all the considered instances.

Influence of the percentage of negative eigenvalues on our algorithm on instances of class $({ IQCP_0})$

We also experiment our algorithm on instances of class $({ IQCP_0})$ where we vary the percentage of negative eigenvalues in order to evaluate the impact of this parameter on our algorithm. We generate these instances as in [10]. More precisely, we generate random objective functions as follows: given a percentage $p \in [0, 100]$, we choose n numbers $\mu _i$, where the first $\lfloor pn/100 \rfloor$ are chosen uniformly at random from $[-1, 0]$ and the remaining ones are chosen uniformly at random from [0, 1]. Next, we generate n vectors of dimension n each, now choosing all entries uniformly at random from $[-1, 1]$, and orthonormalize them to obtain vectors $v_i$. The coefficient matrix $Q_0$ is then calculated as $Q_0 = \sum _{i=1}^n\mu _i v_i v_i^T$. Therefore, the parameter p makes it possible to control whether the matrix $Q_0$ is positive semidefinite ($p = 0$), negative semidefinite ($p = 100$) or indefinite. We randomly generate vector $c_0$ in $[-1,1]$, $\ell _i = -10$ and $u_i = 10$ for all $i = 1, \ldots , n$. Then, we replace $x_i$ by $x_i+10$ in order to obtain $0 \le x_i \le 20$. The number of variables n was set to 10, 30, or 50. For each percentage of negative eigenvalues p out of $\{10, 30, 50, 70, 90\}$ and for each n we created 10 instances obtaining a total of 150 instances.

In Table 3 we present results for class $({ IQCP_0})$. For this class of problems, we can observe that 147 instances over the 150 considered were solved by reformulation $({ QP}^*)$ within the time limit of 3 h. We can first notice that the percentage of negative eigenvalues does not influence the average reformulation time of our algorithm, while the average Cplex time is impacted. We observe that hardest instances are those with 30 and 50 % of negative eigenvalues. Indeed, this time is multiplied by about 12 for these instances in comparison to instances with 90 % of negative eigenvalues and by about 2 in comparison to instances with 10 and 70 % of negative eigenvalues. For these instances, we do not present results of the reformulation $({ LP})$, i.e. complete linearization. Indeed, this method solves only instances of size $n=10$ within the time limit. Moreover, the average initial gap over all these instances of reformulation $({ LP})$ is about 252.5 %, while that of reformulation $({ QP}^*)$ is about 9.5 %.

6.2 Computational experiments on mixed-integer instances

Our experiments were carried out on inequality constrained mixed-integer instances of class $({ MIQCP_m})$. Each instance consists of minimizing a quadratic function subject to m quadratic inequality constraints.

For this class, we fixed $m=1$ (one quadratic inequality), and we generate instances with 13, 27, 40, and 53 variables, with about $\frac{1}{4}$ of real variables and $\frac{3}{4}$ of integer variables. For $r=0,1$, matrices $Q_r$ are equal to $M_{Q_r} + C_{Q_r}$, where $M_{Q_r}$ and $C_{Q_r}$ are defined as in Sect. 5. The coefficients of $({ MIQCP_1})$ are randomly generated as follows:

• $\ell _i=0$ and $u_i=10$, for all $i \in I \cup J$.

• The coefficients of $M_{Q_0}$ are integers uniformly distributed in the interval $[-20,20]$ with a density of 75 %. To generate coefficients of $C_{Q_0}$ so that $C_{Q_0}$ is positive semi-definite, we generate a matrix $C_A$, where the elements of the non-zero block are integers uniformly distributed in the interval [0, 5] with a density of 100 %, and $C_{Q_0} = C_A C^T_A$.

• The coefficients of $M_{Q_1}$ are integers uniformly distributed in the interval [0, 10] with a density of 25 %. To generate coefficients of $C_{Q_1}$ such that $C_{Q_1}$ is positive semi-definite, we generate a matrix $C_A$, where the elements of the non-zero block are integers uniformly distributed in the interval [0, 3] with a density of 100 %, and $C_{Q_1} = C_A C^T_A$.

• $b_1 =\lfloor 0.1 * ({\sum \nolimits _{i=1}^n\sum _{j=1}^n} q_{1ij} u_i u_j) \rfloor$.

For each $n = 13, 27, 40$, or 53 we generate 10 instances obtaining a total of 40 instances for class $({ MIQCP_1})$.

In Table 4, we compare the solution of instances of class $({ MIQCP_1})$ by reformulations $({ LQP})$ and $({ MQP}^*)$. These results reveal a similar trend as for class $(IQCP_1)$. More precisely, the initial gap obtained with the reformulation $({ MQP}^*)$ is much tighter than the gap obtained by the reformulation $({ LQP})$ (improved on average by a factor 10), and the number of nodes is smaller with reformulation $({ MQP}^*)$ in comparison with reformulation $({ LQP})$. For these instances, reformulation $({ LQP})$ is faster than reformulation $({ MQP}^*)$ for the smallest instances, with $N=13,27$ or 40 when we consider the reformulation time plus the solution time. However, the total solution time of $({ MQP}^*)$ is highly penalized by the CPU time for solving $({ SDP}')$. For larger instances, with $N=53$, $({ MQP}^*)$ is faster than $({ LQP})$, since it solves all the considered instances in less than 3 h of CPU time, while reformulation $({ LQP})$ is able to only solve 5 instances out of 10.

7 Conclusion

In this paper, we considered the general problem of minimizing a quadratic function subject to equality and/or inequality quadratic constraints. Variables can be integer or continuous but the sub-functions of pure continuous variables must be convex. The general idea of our approach is to reformulate this problem as an equivalent quadratic program whose continuous relaxation is convex. This makes it easier to globally solve the problem by branch-and-bound. We show that the reformulation which provides the best continuous relaxation is obtained by solving a semidefinite relaxation of the original problem.

We report computational results on 220 instances. These results show that in the pure integer case the method allows us to solve almost all the considered instances with up to 40 variables and one or five inequality quadratic constraints in less than three hours of computation time. Regarding the mixed-integer case, the method can handle instances with 40 integer variables, 13 continuous variables, and one inequality constraint in less than 3 h of computation time.

A perspective of this work is to extend our approach to any mixed-integer quadratic program.