# On partial convexification cuts for mixed-integer quadratic programs with 0-1 indicators

Rui Ma, Renaud Chicoisne, Pierre Latouche

► To cite this version:

Rui Ma, Renaud Chicoisne, Pierre Latouche. On partial convexification cuts for mixed-integer quadratic programs with 0-1 indicators. 2026. hal-05467202v2

HAL Id: hal-05467202

https://hal.science/hal-05467202v2

Preprint submitted on 23 Jan 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# On partial convexification cuts for mixed-integer quadratic programs with 0—1 indicators

Rui Ma<sup>a,1,*</sup>, Renaud Chicoisne<sup>a,1</sup>, Pierre Latouche<sup>b,c</sup>

<sup>a</sup>Université Clermont Auvergne, CNRS, Mines de Saint-Etienne, Clermont-Auvergne-INP, LIMOS, 1 rue de la Chebarde, Clermont-Ferrand, 63000, Auvergne, France

<sup>b</sup>Université Clermont Auvergne, CNRS, laboratoire LMBP, Campus des Cézeaux, Clermont-Ferrand, 63000, Auvergne, France

<sup>c</sup>Institut Universitaire de France (IUF), 1 rue Descartes, Paris, 75231, France

## Abstract

This paper studies mixed-integer quadratic programming (MIQP) problems with 0–1 indicator constraints. We propose two cut-generation algorithms under three reformulation schemes, which can be seamlessly embedded into a branch-and-bound framework. The algorithms are based on a partial convexification strategy applied to selected subsets of variables, enabling the efficient generation of both quadratic and linear cuts. We provide theoretical insights by characterizing the generated cuts as deepest cuts and by comparing quadratic cuts with their linear counterparts in different variable spaces, thereby bridging convexification theory and practical MIQP solution methods. Furthermore, we develop three practical strengthening techniques that exploit structural properties of the quadratic terms. Extensive computational experiments demonstrate that the proposed cut-generation algorithms meaningfully improve solver performance by accelerating convergence to optimal solutions.

## Keywords:

branch-and-bound, partial convexification, cut-generation, mixed-integer quadratic programming, branch-and-cut

<footnote>* Corresponding author.</footnote>

<footnote>Email addresses: rui.ma@doctorant.uca.fr (Rui Ma), renaud.chicoisne@uca.fr (Renaud Chicoisne), pierre.latouche@uca.fr (Pierre Latouche)</footnote>

<footnote n="1">¹These authors contributed equally to this work.</footnote>
# 1. Introduction

In this paper, we study the mixed-integer quadratic programming problem (MIQP) (1):

$$ \mu := \min_{x,z,\eta} \quad \frac{1}{2}\eta + a^{\top}x + b^{\top}z \qquad (1a) $$

$$ \text{s.t.} \quad \eta \ge x^{\top}Qx, \qquad (1b) $$

$$ x \circ (\mathbf{1} - z) = 0, \qquad (1c) $$

$$ z \in \{0, 1\}^n, \qquad (1d) $$

where $a, b \in \mathbb{R}^n$ are fixed vectors and $Q \in \mathbb{S}_{++}^n$ is a positive definite matrix. There has been growing interest in problem (1), which arises in various areas such as portfolio optimization (Bertsimas and Cory-Wright, 2022), sparse statistical learning (Bertsimas et al., 2016; Hastie et al., 2009), and optimal control (Blackburn et al., 2019; Aguilera et al., 2017). Problem (1) is NP-hard (Chen et al., 2014) due to the exponential search space induced by the indicator constraint (1c). We define the mixed-integer set $\mathcal{S}$ induced by problem (1) as

$$ \mathcal{S} := \{(x, z, \eta) : (1b), (1c), (1d)\}. $$

To study the characterization of $\mathcal{S}$, the disjunctive programming approach (Frangioni et al., 2020; Balas, 1979) provides a theoretical framework for constructing $\mathrm{conv}(\mathcal{S})$ with a conic quadratic structure in an extended space. However, this approach requires introducing an exponential number of copies of the decision variables, resulting in an exponential-size formulation that is computationally intractable in practice.

On the other hand, a widely used approach is to construct convex relaxations that approximate $\mathrm{conv}(\mathcal{S})$, thereby yielding reformulations whose continuous relaxations provide stronger lower bounds. Recently, decomposition methods of the form $x^{\top}Qx = x^{\top}Rx + \sum_{i \in [\ell]} x^{\top}A_i x$, with $\ell \ge 1$, which decompose the quadratic matrix $Q$ into a sum of simpler components $A_i$ while preserving the positive semidefiniteness of $R$, have attracted considerable attention. Notable examples include perspective reformulations (Günlük and Linderoth, 2011, 2010; Aktürk et al., 2009; Frangioni and Gentile, 2006), where each $A_i$ corresponds to a separable positive diagonal compo-
nent linked to the indicator variable $z_i$, typically achieved by replacing the quadratic term $A_i x_i^2$ with its perspective form $A_i x_i^2 / z_i$ for $z_i > 0$. In addition, reformulations based on isolating principal submatrices $A_i$ with a $2 \times 2$ quadratic structure (Han et al., 2023; Gómez, 2021; Anstreicher and Burer, 2021; Atamturk et al., 2021; Atamtürk and Gómez, 2018; Jeon et al., 2017; Zheng et al., 2014) or, more generally, an arbitrary $k \times k$ ($k \le n$) quadratic structure (Wei et al., 2024; Frangioni et al., 2020) have also been studied. Notably, Wei et al. (2024) proved that convexifying the set with all $n \times n$ quadratic structures yields a compact mixed-integer linear reformulation of MIQP (1) in an extended space, which is referred to as MILO in their work. Other structures that have been studied include rank-one decompositions (Wei et al., 2022; Atamtürk and Gómez, 2023; Atamturk and Gomez, 2019) and tridiagonal matrices (Liu et al., 2023). These methods leverage the positive definiteness of $Q$ to approximate $\text{conv}(S)$ in a computationally tractable manner while preserving the structural properties of the original problem.

Another methodology for approximating $\text{conv}(S)$ is the cut-generation framework (Chicoisne, 2020; Gomory, 2009; Günlük and Linderoth, 2008; Sherali et al., 2005; Parija et al., 1999; Stubbs and Mehrotra, 1999; Balas et al., 1993). Its primary objective is to iteratively generate valid inequalities, often referred to as deep cuts, that separate fractional solutions obtained from relaxations lying outside $\text{conv}(S)$, thereby locally strengthening the convex relaxation of the feasible region. For mixed-integer nonlinear programming (MINLP) problems, cut generation constitutes the core mechanism underlying outer-approximation-based (OA) algorithms. To obtain exact optimal solutions, cut-generation techniques are typically integrated with a branch-and-bound (B&B) search, resulting in the branch-and-cut (B&C) framework. In B&C, cuts may be generated globally at the root node or locally within subproblems. The B&C framework is well supported by modern commercial solvers, and existing exact methods for solving problem (1) extensively leverage these solver capabilities (Bertsimas and Van Parys, 2020; Bertsimas et al., 2016; Bourguignon et al., 2015; Cozad et al., 2014).

In this paper, we bridge the gap between state-of-the-art convexification theory for MIQP (1) and its implementation within exact solution frameworks. We develop two families of nontrivial quadratic and linear cut-generation algorithms grounded in partial convexification and separation
theory, and we show that the resulting cuts are among the deepest possible. From an implementation perspective, we translate convexification theory into tractable and software-efficient algorithms that balance relaxation strength and computational performance. As a motivating application, we consider the $l_0$-regularized sparse linear regression problem (2):

$$ \min_{\beta} \frac{1}{2m} \|X\beta - y\|_2^2 + \alpha \|\beta\|_0 + c \|\beta\|_2^2, \quad (2) $$

where $\|\beta\|_0 := |\{j \in [n] | \beta_j \neq 0\}|$, $\beta \in \mathbb{R}^n$ denotes the regression coefficients, $X \in \mathbb{R}^{m \times n}$ is the data matrix, $y \in \mathbb{R}^m$ is the response vector, and $\alpha > 0$ controls the sparsity level. By introducing an indicator variable $z \in \{0, 1\}^n$ to represent the pseudo-norm $\|\beta\|_0$, setting $x := \beta$, $Q := \frac{1}{m}X^\top X + 2cI$, $a := -\frac{1}{m}X^\top y$, and $b := \alpha \mathbf{1}$, and imposing the indicator constraints (1c), problem (2) can be equivalently reformulated as an MIQP (1).

The remainder of this paper is organized as follows. Section 2 introduces the notation and preliminaries. Section 3 presents the theoretical foundation of the proposed cut-generation algorithms. Section 4 presents two families of cut-generation algorithms along with their theoretical formulations and proofs, and introduces an enhanced mixed-integer linear formulation for MILO, denoted as MILO+. Section 5 describes three successive strengthening methods for problem (1). Section 6 reports computational results for the proposed cut-generation algorithms. Finally, Section 7 concludes the paper.

## 2. Notation and preliminaries

Let $[n] := \{1, 2, \dots, n\}$. Given a subset $J \subseteq [n]$, we denote $\bar{J} := [n] \setminus J$. We use $\mathbf{1}_n \in \mathbb{R}^n$ to denote the all-ones vector of dimension $n$, and simply write $\mathbf{1}$ when the dimension is clear from the context. Given vectors $a, b \in \mathbb{R}^n$, $a \circ b$ denotes their Hadamard product. The identity matrix of order $n$ is denoted by $I_n \in \mathbb{R}^{n \times n}$, and we simply write $I$ when the dimension is clear from the context. To facilitate both matrix decompositions indexed by subsets and the enumeration of all principal submatrices, we employ two equivalent representations of the same principal submatrix and impose an order on the collection of all principal submatrices. Given a subset $J \subseteq [n]$ with $|J| = q$, we decompose $Q \in \mathbb{S}_{++}^n$ as $Q = \begin{pmatrix} P & T^\top \\ T & S \end{pmatrix}$, where $P := Q_J \in \mathbb{R}^{q \times q}$ and $S := Q_J \in \mathbb{R}^{(n-q) \times (n-q)}$ denote the principal submatrices of $Q$
indexed by $J$ and $\bar{J}$, respectively, and $T := Q_{\bar{J},J}$ contains the corresponding off-diagonal block. Given a vector $v \in \mathbb{R}^n$ and an index set $J \subseteq [n]$, let $v_J \in \mathbb{R}^{|J|}$ denote the subvector indexed by $J$. Next, considering index sets $J$ and all subsets $N \subseteq J$, let $|J| := q$ and $K := 2^q$, and denote by $\mathbf{e}_k \in \{0,1\}^q$, $k \in [K]$, the indicator vectors corresponding to these subsets. For simplicity, we omit the subscripts associated with the indicator variables and their corresponding principal index sets whenever the context is clear. Without loss of generality, we assume that the elements of the index set $J \subseteq [n]$, as well as all subsets $N \subseteq J$, are ordered increasingly. Each subset $N$ has a unique indicator vector with respect to $J$. To impose an order on all subsets, we arrange the $K$ subsets and their corresponding indicator vectors $\{\mathbf{e}_k\}_{k=1}^K$ in increasing order according to the value of $\text{bin}(k-1)$, which is the binary integer obtained by interpreting an indicator vector as its bit pattern read from the first coordinate to the last.

**Example 1.** Consider $n = 3$, $Q \in \mathbb{R}^{n \times n}$, $J = \{1,3\}$, $K = 2^{|J|} = 4$, and $Q_J = \begin{pmatrix} a & b \\ b & c \end{pmatrix}$, and $v_J = \begin{pmatrix} \bar{a} \\ \bar{b} \end{pmatrix}$. For each $k \in [K]$, let $N \subseteq J$ denote the subset corresponding to $\mathbf{e}_k$.

<table><thead><tr><th>k</th><th>1</th><th>2</th><th>3</th><th>4</th></tr></thead><tbody><tr><td>bin(k - 1)</td><td>00<br>$$ \begin{pmatrix} 0 \\ 0 \end{pmatrix} $$</td><td>01<br>$$ \begin{pmatrix} 0 \\ 1 \end{pmatrix} $$</td><td>10<br>$$ \begin{pmatrix} 1 \\ 0 \end{pmatrix} $$</td><td>11<br>$$ \begin{pmatrix} 1 \\ 1 \end{pmatrix} $$</td></tr><tr><td>e<sub>k</sub></td><td>0</td><td>{3}</td><td>{1}</td><td>{1,3}</td></tr><tr><td>N</td><td>0</td><td>$$ \begin{pmatrix} c \end{pmatrix} $$</td><td>$$ \begin{pmatrix} a \end{pmatrix} $$</td><td>$$ \begin{pmatrix} a & b \\ b & c \end{pmatrix} $$</td></tr><tr><td>Q<sub>N</sub> = Q<sub>k</sub></td><td>empty matrix</td><td>$$ \begin{pmatrix} \bar{b} \end{pmatrix} $$</td><td>$$ \begin{pmatrix} \bar{a} \end{pmatrix} $$</td><td>$$ \begin{pmatrix} \bar{a} \\ \bar{b} \end{pmatrix} $$</td></tr><tr><td>v<sub>N</sub> = v<sub>k</sub></td><td>empty vector</td><td>$$ \begin{pmatrix} \bar{b} \end{pmatrix} $$</td><td>$$ \begin{pmatrix} \bar{a} \end{pmatrix} $$</td><td>$$ \begin{pmatrix} \bar{a} \\ \bar{b} \end{pmatrix} $$</td></tr></tbody></table>

Example 1 illustrates the correspondence among a subset $N \subseteq J$, its indicator vector $\mathbf{e}_k$, the principal submatrix indexed by $N$ and the subvector indexed by $N$. Given a positive definite matrix $Q > 0$ and a principal submatrix $Q_k \in \mathbb{R}^{|N| \times |N|}$, let $\hat{Q}_k^{-1} \in \mathbb{R}^{n \times n}$ denote the matrix obtained by embedding $Q_k^{-1}$ into the original space of $Q$, with all other entries set to zero, and let $\hat{v}_J \in \mathbb{R}^n$ denote the vector obtained by embedding $v_J$ into the original space of $v$, with all other entries set to zero.
**Example 2.** Consider $n = 3$, $Q \in \mathbb{R}^{n \times n}$, $N = \{1, 3\}$. Suppose $Q_k = \begin{pmatrix} a & b \\ b & c \end{pmatrix}$, $Q_k \succ 0$, and $v_k = \begin{pmatrix} \bar{a} \\ \bar{b} \end{pmatrix}$, then

$$Q_k^{-1} = \frac{1}{ac - b^2} \begin{pmatrix} c & -b \\ -b & a \end{pmatrix}, \quad \hat{Q}_k^{-1} = \begin{pmatrix} \frac{c}{ac-b^2} & 0 & \frac{-b}{ac-b^2} \\ 0 & 0 & 0 \\ \frac{-b}{ac-b^2} & 0 & \frac{a}{ac-b^2} \end{pmatrix} \quad \text{and} \quad \hat{v}_k = \begin{pmatrix} \bar{a} \\ \bar{b} \end{pmatrix}.$$

Given a discrete set $S$, we denote by $\text{conv}(S)$ its convex hull. Let $\lambda_+(Q)$ and $\lambda_-(Q)$ denote the largest and smallest eigenvalues of a symmetric matrix $Q$, respectively. In practice, constraint (1c) can be linearized as $-M_i z_i \le x_i \le M_i z_i$ for all $i \in [n]$, where $M_i$ is a big-M constant (Glover, 1975) that bounds the continuous decision variable $x_i$. In the context of reformulating MIQP (1), the MILO formulation (Wei et al., 2024), denoted by (3), is defined as follows:

$$\mu := \min_{z,W} -\frac{1}{2} a^\top W a + b^\top z \quad (3a)$$

$$\text{s.t.} \quad \sum_{k=1}^{n} Q_{ik} W_{ki} = z_i, \quad \forall i \in [n] \quad (3b)$$

$$-M(1-z_i) \le \sum_{k=1}^{n} Q_{ik} W_{kj} \le M(1-z_i), \quad \forall i \ne j \quad (3c)$$

$$|W_{ij}| \le \lambda_+(Q^{-1}) \min\{z_i, z_j\}, \quad \forall (i, j) \in [n]^2 \quad (3d)$$

where the big-M constant is defined as $M := \lambda_+(Q^{-1}) \cdot \max_{i \in [n]} \|Q_{[n],i}\|_2$.

### 3. Partial convexification over selected variables

In this section, we establish the theoretical foundations of the partial convexification strategy for MIQP (1). Based on these foundations, we introduce an auxiliary mixed-integer formulation with semidefinite constraints that captures the strength of the partial convex hull and demonstrate its equivalence to (1). Throughout, we denote by $J \subset [n]$ the index set of selected variables, where $|J| = q \ll n$.
### 3.1. Partial convexification via disjunctive programming

In this subsection, we construct the partial convexification of $S$ within a disjunctive-conic programming framework. We define the set $S_J$ and its convex hull $\text{conv}(S_J)$, and then present a procedure for explicitly deriving $\text{conv}(S_J)$.

Given a positive definite matrix $Q > 0$, by introducing an auxiliary variable $\nu \in \mathbb{R}_+$, constraint (1b) can be extended-reformulated using a Schur-complement-based decomposition as follows:

$$ \eta \ge x^{\top} \begin{pmatrix} T^{\top} S^{-1} T & T^{\top} \\ T & S \end{pmatrix} x + \nu, \quad (4a) $$

$$ \nu \ge x_J^{\top} (P - T^{\top} S^{-1} T) x_J. \quad (4b) $$

Following the same partition based on index sets, we relax the indicator constraint (1c) by enforcing it only on the variables indexed by $J$:

$$ x_J \circ (1 - z_J) = 0, \quad (5a) $$

$$ z_J \in \{0, 1\}^q. \quad (5b) $$

**Definition 1.** We define $S_J$ as

$$ S_J := \{(x_J, z_J, \nu) : (4b), (5a), (5b)\}. $$

The set $S_J$ is obtained by extracting the principal submatrix of $Q$ indexed by $J$, while preserving positive definiteness through the Schur complement (Zhang, 2006). We now recall a result adapted from Proposition 4 in Lodi et al. (2023).

**Proposition 1.** Consider a collection of $K$ nonempty and closed convex sets $S_k$ defined as:

$$ S_k := \{v : A_k v - b_k \in C_k, \quad D_k v = d_k\} $$

where each $C_k$ is a proper cone. If for each $k \in [K]$, $S_k := B_k + U$ where $B_k$
is nonempty, bounded and convex and $\mathcal{U}$ is closed and convex, we have:

$$v := \operatorname{conv} \left( \bigcup_{k=1}^{K} S_k \right) \iff \\ \exists (v_k, \theta_k)_{k \in [K]} \in (\mathbb{R}^n \times \mathbb{R}_+)^K : \left\{ \begin{array}{ll} v = \sum_{k=1}^{K} v_k & \\ 1 = \sum_{k=1}^{K} \theta_k & \\ A_k v_k - \theta_k b_k \in C_k & \forall k \in [K] \\ D_k v_k = \theta_k d_k & \forall k \in [K] \end{array} \right.$$

We now apply Proposition 1 to derive an explicit description of $\operatorname{conv}(S_J)$, which introduces $K = 2^q$ additional variables.

**Proposition 2.** By Theorem 1, $(x_J, z_J, \nu) \in \operatorname{conv}(S_J)$ if and only if there exist $\theta \in \mathbb{R}_+^K$ and $\{\hat{y}_k \in \mathbb{R}^q\}_{k \in [K]}$ such that

$$x_J = \sum_{k=1}^{K} \hat{y}_k, z_J = \sum_{k=1}^{K} \theta_k e_k, \nu \ge \sum_{k=1}^{K} \frac{1}{\theta_k} y_k^\top (P - T^\top S^{-1} T)_k y_k, \sum_{k=1}^{K} \theta_k = 1.$$

*Proof.* For each $k \in [K]$ corresponding to a subset $N \subseteq J$, given $(P - T^\top S^{-1} T)_k > 0$, considering the $K$ rotated second-order cone $S_J^k$ defined by fixing $z_J$ to $e_k$, the quadratic constraint (4b) defining $S_J^k$ can be rewritten as the following rotated second-order conic constraint

$$\left\| \begin{array}{c} 2R_k x_k \\ \nu_k - 1 \end{array} \right\|_2 \le \nu_k + 1, \quad \nu_k \ge 0 \\ \text{i.e.} \quad \left( \begin{array}{c} 2R_k x_k \\ \nu_k \end{array} \right), \nu_k) - \left( \begin{array}{c} 0 \\ 1 \end{array} \right), -1) \in \mathcal{L}_2^{(|N|+1)+1}$$

where $R_k$ is the Choleski cofactor of $(P - T^\top S^{-1} T)_k$, i.e. $(P - T^\top S^{-1} T)_k = R_k^\top R_k$. By applying Theorem 1 we have the union-type convex hull description of $S_J$ such that $(x_J, z_J, \nu) \in \operatorname{conv}(S_J)$ if and only if for all $k \in [K]$ there
exists $(\hat{y}_k, \mathbf{e}_k, \nu_k, \theta_k) \in \mathbb{R}^q \times \mathbb{R}^q \times \mathbb{R}_+ \times \mathbb{R}_+$ such that

$$x_J = \sum_{k=1}^{K} \hat{y}_k, \quad \nu = \sum_{k=1}^{K} \nu_k, \quad z_J = \sum_{k=1}^{K} \theta_k \mathbf{e}_k, \quad \sum_{k=1}^{K} \theta_k = 1, \\ \left\| \begin{array}{l} 2R_k y_k \\ \nu_k - \theta_k \end{array} \right\|_2 \le \nu_k + \theta_k, \quad \forall k \in [K]. \quad (6)$$

Squaring the rotated SOC constraints (6) we obtain $\nu_k \ge y_k^\top (P - T^\top S^{-1} T)_k y_k / \theta_k$. Combining these last inequalities with $\nu = \sum_{k=1}^K \nu_k$ we have

$$\nu \ge \sum_{k=1}^{K} \frac{1}{\theta_k} y_k^\top (P - T^\top S^{-1} T)_k y_k. \quad (7)$$

□

Proposition 2 provides a quadratic-conic representation of $\mathrm{conv}(S_J)$ with $K$ additional variables. Closely related representations have been studied in the literature; see, for example, (Frangioni et al., 2020).

### 3.2. Partial convexification via polyhedral representation

In this subsection, we study partial convexification through a polyhedral representation based on the polytope $\mathcal{P} \subseteq \mathbb{R}^{n+n^2}$ introduced in (Wei et al., 2024).

$$\mathcal{P} := \mathrm{conv} \left\{ (\mathbf{e}_k, \hat{Q}_k^{-1}) : k \in [2^n] \right\}.$$

In what follows, we introduce a lower-dimensional polytope $\mathcal{P}_J$, defined in an extended variable space associated with the index set $J$, and analyze its relationship with $\mathrm{conv}(S_J)$.

**Definition 2.** Given $Q > 0$ and a subset $J \subseteq [n]$ with $|J| = q$, let $M := P - T^\top S^{-1} T > 0$ be the Schur complement defined in Section 3.1. For each $k \in [K]$ with $K = 2^q$, denote $W_k := \hat{M}_k^{-1}$. The polytope $\mathcal{P}_J \subseteq \mathbb{R}^{q+q^2}$ is defined as

$$\mathcal{P}_J := \mathrm{conv} \left\{ (\mathbf{e}_k, W_k) : k \in [K] \right\}.$$

**Corollary 1.** By construction, the polytope $\mathcal{P}_J$ has exactly $K = 2^q$ extreme points $(\mathbf{e}_k, W_k)$. Moreover, $(z_J, W) \in \mathcal{P}_J$ if and only if there exists $\theta \in \mathbb{R}_+^K$
such that

$$z_J = \sum_{k=1}^{K} \theta_k e_k, \quad W = \sum_{k=1}^{K} \theta_k W_k, \quad \sum_{k=1}^{K} \theta_k = 1.$$

We now establish the connection between $\mathrm{conv}(S_J)$ and the polytope $\mathcal{P}_J$.

**Proposition 3.** (Wei et al., 2024) A point $(x, z, \eta)$ belongs to $\mathrm{conv}(S)$ if and only if there exists a matrix $W \in \mathbb{S}_+$ such that

$$\begin{pmatrix} \eta & x^\top \\ x & W \end{pmatrix} \in \mathbb{S}_+^{n+1}, \quad (z, W) \in \mathcal{P}.$$

**Corollary 2.** A point $(x_J, z_J, \nu)$ belongs to $\mathrm{conv}(S_J)$ if and only if there exists a matrix $W \in \mathbb{S}_+$ such that

$$\begin{pmatrix} \nu & x_J^\top \\ x_J & W \end{pmatrix} \in \mathbb{S}_+^{q+1}, \quad (z_J, W) \in \mathcal{P}_J.$$

Corollary 2 establishes a direct link between $\mathrm{conv}(S_J)$ and $\mathcal{P}_J$, showing that partial convexification in the original variable space of (1) is equivalent to applying convexification in the extended space defined by $\mathcal{P}_J$.

### 3.3. A mixed-integer SDP formulation on the partial convex hull

Building on the preceding theoretical results, we propose an auxiliary mixed-integer SDP formulation, denoted by (8), which is derived from the partial convexification strategies introduced in Sections 3.1 and 3.2.

**Proposition 4.** Formulation (8) is equivalent to formulation (1).

$$\min_{x,z,\eta,\nu,W} \quad \frac{1}{2}\eta + a^\top x + b^\top z$$
$$\text{s.t.} \quad \eta \ge x^\top \begin{pmatrix} T^\top S^{-1} T & T^\top \\ T & S \end{pmatrix} x + \nu, \qquad (8a)$$

$$\begin{pmatrix} \nu & x_J^\top \\ x_J & W \end{pmatrix} \in \mathbb{S}_+^{q+1}, \qquad (8b)$$

$$(z_J, W) \in \mathcal{P}_J, \qquad (8c)$$

$$(1c), (1d)$$
*Proof.* Let $(x^*, z^*, \eta^*) \in \mathcal{S}$ be feasible for formulation (1). Fix the index set $J$ and let $N := \{j \in J : z_j^* = 1\}$. Define $W^* := (P - T^\top S^{-1}T)_N^{-1}$, and let $\nu^* := x_J^{*\top}(P - T^\top S^{-1}T)_N x_J^*$. By construction, $(z_J^*, W^*)$ is an extreme point of $\mathcal{P}_J$. Moreover, the matrix $\begin{pmatrix} \nu^* & x_J^{*\top} \\ x_J^* & W^* \end{pmatrix}$ is positive semidefinite by the Schur complement. Combining this with the decomposition (4), we conclude that $(x^*, z^*, \eta^*, \nu^*, W^*)$ satisfies all constraints of (8).

Conversely, let $(x^*, z^*, \eta^*, \nu^*, W^*)$ be feasible for formulation (8). Since $z^* \in \{0,1\}^n$, constraint (8c) implies that $(z_J^*, W^*)$ is an extreme point of $\mathcal{P}_J$, and hence $W^* = (P - T^\top \hat{S}^{-1}T)_N^{-1}$ for $N := \{j \in J : z_j^* = 1\}$. Constraint (8b) then yields $\nu^* \ge x_J^{*\top}(P - T^\top S^{-1}T)_N x_J^*$. Substituting this inequality into (8a) and using the indicator constraint, we recover $\eta^* \ge x^{*\top}Qx^*$. Therefore, $(x^*, z^*, \eta^*) \in \mathcal{S}$. $\square$

Formulation (8) provides an exact mixed-integer SDP representation of problem (1). If the integrality constraints on $z$ are relaxed, the SDP constraint (8b) yields the tightest convex relaxation implied by partial convexification. However, such semidefinite constraints are rarely supported by commercial solvers. In subsequent sections, we develop two cut-generation algorithms that recover the strength of (8b) using only quadratic and linear valid inequalities.

## 4. Cut-generation algorithms

In this section, we present two cut-generation algorithms derived from the partial convexification framework developed in Section 3. We first propose a quadratic cut-generation procedure for MIQP (1), a class of cuts that has received relatively limited attention in the existing literature. We then introduce a linear counterpart tailored to the MILO formulation (3), and show that the resulting linear cuts are equivalent to the quadratic cuts when projected onto the original variable space. In addition, we propose an enhanced linear reformulation of MIQP (1), denoted by MILO+, to which the same linear cut-generation procedure can be applied. We prove that, for a given incumbent solution of the continuous relaxation of MIQP (1), MILO (3), or MILO+, the associated separation problems generate the strongest cuts within the proposed partial convexification framework.
We first state two auxiliary lemmas that will be used in the subsequent analysis.

**Lemma 1.** Given a positive definite matrix V and a vector v, the optimal value of the unconstrained quadratic minimization problem satisfies

$$ \min_{u} \{u^{\top} V u + v^{\top} u\} = -\frac{1}{4} v^{\top} V^{-1} v. $$

*Proof.* The first-order optimality condition yields $2Vu^* + v = 0$, which implies $u^* = -\frac{1}{2}V^{-1}v$. Substituting $u^*$ into the objective function gives the stated result. □

**Lemma 2.** Let $U$ and $W$ be convex sets and let $f: U \times W \to \mathbb{R}$ be a continuous function. If $U$ is compact, $w \mapsto f(u, w)$ is concave for any $u \in U$, and $u \mapsto f(u, w)$ is convex for any $w \in W$, then

$$ \min_{u \in U} \sup_{w \in W} f(u, w) = \sup_{w \in W} \min_{u \in U} f(u, w). $$

### 4.1. Quadratic cut-generation algorithm

Given a selected index set $J \subset [n]$, we now derive a separation problem for generating quadratic cuts and show that, in theory, it produces the strongest quadratic cuts induced by partial convexification for strengthening the relaxation of (1).

**Proposition 5.** Let $J \subset [n]$ with $|J| = q$, and let $(\tilde{x}_J, \tilde{z}_J)$ be an indexed incumbent of the fractional solution $(\tilde{x}, \tilde{z}, \tilde{\eta})$ obtained from a relaxation of problem (1). Consider the following quadratic separation problem:

$$ \max_{\pi, \lambda, \lambda_0} \quad \pi^{\top} \tilde{x}_J + \lambda^{\top} \tilde{z}_J + \lambda_0 \qquad (9a) $$

$$ \text{s.t.} \quad \frac{1}{4} \pi^{\top} W_k \pi + \mathbf{e}_k^{\top} \lambda + \lambda_0 \le 0, \quad \forall (\mathbf{e}_k, W_k) \in \mathcal{P}_J. \qquad (9b) $$

Let $(\pi^*, \lambda^*, \lambda_0^*)$ be an optimal solution. Then the inequalities

$$ \eta \ge x^{\top} \begin{pmatrix} T^{\top} S^{-1} T & T^{\top} \\ T & S \end{pmatrix} x + \nu, \qquad (10a) $$

$$ \nu \ge \pi^{*\top} x_J + \lambda^{*\top} z_J + \lambda_0^*, \qquad (10b) $$

are valid for problem (1).
Proof. Given the incumbent $(\tilde{x}, \tilde{z}, \tilde{\eta})$ obtained from a relaxation of MIQP (1), we consider the separation problem (11) for conv($S_J$) proposed in Proposition 2:

$$ \tilde{\nu} := \min_{\theta \in \mathbb{R}_+^K, y_k, k \in [K]} \sum_{k=1}^K \frac{1}{\theta_k} y_k^\top (P - T^\top S^{-1} T)_k y_k \quad (11a) $$

$$ \text{s.t.} \quad \tilde{x}_J = \sum_{k=1}^{K} \hat{y}_k, \quad \tilde{z}_J = \sum_{k=1}^{K} \theta_k \mathbf{e}_k, \quad \sum_{k=1}^{K} \theta_k = 1. \quad (11b) $$

If $\tilde{x}^\top \begin{pmatrix} T^\top S^{-1} T & T^\top \\ T & S \end{pmatrix} \tilde{x} + \tilde{\nu} \ge \tilde{\eta}$, then the incumbent $(\tilde{x}, \tilde{z}, \tilde{\eta})$ can be separated from conv($S_J$) and the corresponding cut can be added.

To derive a $\theta$-free formulation, we first fix $\theta$ in (11) and consider the resulting minimization problem with respect to $y_k$, we note that $\hat{y}_k$ is just the adaptive $y_k$ with respect to the dimension alignment as mentioned in Section 2:

$$ \min_{y_k, k \in [K]} \sum_{k=1}^{K} \frac{1}{\theta_k} y_k^\top (P - T^\top S^{-1} T)_k y_k, \quad \text{s.t.} \quad \tilde{x}_J = \sum_{k=1}^{K} \hat{y}_k. $$

This problem is convex since $P - T^\top S^{-1} T \in \mathbb{S}_+^q$ and satisfies Slater's condition. Hence, strong duality holds. By dualizing the equality constraint using $\pi \in \mathbb{R}^q$ and applying Lemma 1 to each quadratic term, we obtain

$$ \tilde{\nu} = \min_{\theta} \max_{\pi} \pi^\top \tilde{x}_J - \frac{1}{4} \pi^\top \left( \sum_{k=1}^{K} \theta_k W_k \right) \pi \quad \text{s.t.} \quad \tilde{z}_J = \sum_{k=1}^{K} \theta_k \mathbf{e}_k, \quad \sum_{k=1}^{K} \theta_k = 1. $$

We associate Lagrange multipliers $\lambda \in \mathbb{R}^q$ and $\lambda_0 \in \mathbb{R}$ with the constraints $\tilde{z}_J = \sum_{k=1}^K \theta_k \mathbf{e}_k$ and $\sum_{k=1}^K \theta_k = 1$, respectively. The resulting Lagrangian is

$$ L(\pi, \theta, \lambda, \lambda_0) = \pi^\top \tilde{x}_J - \frac{1}{4} \pi^\top \left( \sum_{k=1}^{K} \theta_k W_k \right) \pi + \lambda^\top \left( \tilde{z}_J - \sum_{k=1}^{K} \theta_k \mathbf{e}_k \right) + \lambda_0 \left( 1 - \sum_{k=1}^{K} \theta_k \right). $$

Since the Lagrangian is affine in $\theta$ and the feasible set of $\theta$ is a compact simplex, Lemma 2 allows us to interchange the order of optimization in $\theta$
and $\pi$. Taking the dual with respect to $\theta$ yields

$$ \begin{array}{ll} \tilde{\nu} = \max_{\pi, \lambda, \lambda_0} & \pi^\top \tilde{x}_J + \lambda^\top \tilde{z}_J + \lambda_0 \\ \text{s.t.} & \frac{1}{4} \pi^\top W_k \pi + \mathbf{e}_k^\top \lambda + \lambda_0 \le 0, \quad \forall (\mathbf{e}_k, W_k) \in \mathcal{P}_J. \end{array} $$

□

**Proposition 5** establishes a family of quadratic cuts for problem (1). Within the proposed partial convexification framework, these cuts are strongest in the sense that they correspond to optimal separating cuts of the associated separation problem.

## 4.2. Linear cut-generation algorithm

In this subsection, we focus on the MILO formulation (3). We first introduce an enhanced formulation, denoted by MILO+, and establish its equivalence to MILO (3). Under the same objective function and discrete feasible region, we then develop a linear cut-generation algorithm that applies to both MILO (3) and MILO+ within the variable space defined by $\mathcal{P}$.

**Lemma 3.** (Wei et al., 2024) For any $S \subseteq [n]$, $Q^{-1} \succeq \hat{Q}_S^{-1}$ and $\|\hat{Q}_S^{-1}\|_{\max} := \max_{i,j} |(\hat{Q}_S^{-1})_{ij}| \le \lambda_+(Q^{-1})$.

We formulate MILO+ as follows.

**Proposition 6.** *Formulation MILO+ (12) is equivalent to MILO (3).*

$$ \mu := \min_{z, W} \quad -\frac{1}{2} a^\top W a + b^\top z \\ \text{s.t.} \quad |(Q - QWQ)_{ij}| \le \lambda_+(Q) \cdot \min\{1 - z_i, 1 - z_j\}, \quad \forall i \le j \quad (12a) $$

$$ (\text{MILO}+) \quad |W_{ij}| \le \lambda_+(Q^{-1}) \cdot \min\{z_i, z_j\}, \quad \forall i \le j \quad (12b) $$

$$ W_{ij} = W_{ji}, \quad \forall i \le j \quad (12c) $$

(1d).

*Proof.* It is shown in (Wei et al., 2024) that the feasible region of MILO (3) is the extreme point set of $\mathcal{P}$. We show that MILO+ (12) shares the same feasible region.

Let $(z, W)$ be feasible for MILO+. Since $z \in \{0, 1\}^n$, define the index set $J := \{i \in [n] : z_i = 1\}$. From the constraint (12b) and (12c), it follows
that $W_{ij} = 0$ whenever $i \notin J$ or $j \notin J$. Hence, $W$ has the block structure
$$W = \begin{pmatrix} W_{J,J} & 0 \\ 0 & 0 \end{pmatrix}.$$ Next, consider the constraint (12a) and (12c). For any $i, j \in J$, the right-hand side is zero, implying $(QWQ)_{J,J} = PW_{J,J}P$ and $(Q - QWQ)_{J,J} = 0$. Using the conformal block partition $Q = \begin{pmatrix} P & T^\top \\ T & S \end{pmatrix}$, we obtain $PW_{J,J}P = P$, and therefore $W_{J,J} = P^{-1}$. Consequently, $W = \begin{pmatrix} P^{-1} & 0 \\ 0 & 0 \end{pmatrix} = \hat{Q}_k^{-1}$ for the unique index $k \in [2^n]$ corresponding to $J$. Thus, $(z, W) = (e_k, \hat{Q}_k^{-1})$ is an extreme point of $\mathcal{P}$.

Conversely, let $(e_k, \hat{Q}_k^{-1})$ be an extreme point of $\mathcal{P}$, and let $J \subset [n]$ be the corresponding index set. By construction and Lemma 3, the constraint (12b) and (12c) are satisfied. Moreover, a direct computation yields
$$Q - Q\hat{Q}_k^{-1}Q = \begin{pmatrix} 0 & 0 \\ 0 & S - TP^{-1}T^\top \end{pmatrix}.$$ Let $Q^{-1} = \begin{pmatrix} \bar{P} & \bar{T}^\top \\ \bar{T} & \bar{S} \end{pmatrix}$ be the conformal block inverse. By standard block inversion identities, $\bar{S}^{-1} = S - TP^{-1}T^\top$. Applying Lemma 3, we obtain

$$\max_{i,j \in [n]} |(Q - Q\hat{Q}_k^{-1}Q)_{ij}| \le \lambda_+(Q),$$

which verifies feasibility of $(e_k, \hat{Q}_k^{-1})$ for MILO+.

<figure><img src="image_2.png" /></figure>

As a linear reformulation of MIQP (1), MILO+ (12) exploits both the symmetry and the block structure of the matrix variable $W$ at the expense of a larger model size. However, the number of linear constraints in (12b) grows as $O(n^3)$, compared to $O(n^2)$ in MILO (3). A detailed comparison of the computational performance of MILO and MILO+ is provided in Section 6. Since MILO (3) is equivalent to MIQP (1), and Proposition 6 establishes the same equivalence for MILO+ (12), we next develop a unified linear cut-generation framework applicable to both formulations.

**Proposition 7.** Let $J \subset [n]$ with $|J| = q$, and let $\tilde{z}_J$ be a fractional solution obtained from a relaxation of MILO (3) or MILO+ (12). Define $c := a_J - T^\top S^{-1} a_J \in \mathbb{R}^q$. Consider the following linear separation problem:

$$\max_{\lambda, \lambda_0} \quad \lambda^\top \tilde{z}_J + \lambda_0 \qquad (13a)$$

$$\text{s.t.} \quad \frac{1}{2} c^\top W_k c + e_k^\top \lambda + \lambda_0 \le 0, \quad \forall (e_k, W_k) \in \mathcal{P}_J. \qquad (13b)$$
Let $(\lambda^*, \lambda_0^*)$ denote an optimal solution. Then the inequality

$$ \mu \geq -\frac{1}{2} a_J^\top S^{-1} a_J + \lambda^* \top z_J + \lambda_0^* \quad (14) $$

is valid for both MILO (3) and MILO+ (12).

*Proof.* Let $J$ be a given index set defining the block structure of the matrix $Q$ and the vectors $a$ and $b$. The objective function of (1) can be rewritten as

$$ \min_{x,z} \frac{1}{2} \begin{pmatrix} x_J \\ x_{\bar{J}} \end{pmatrix}^\top \begin{pmatrix} P & T^\top \\ T & S \end{pmatrix} \begin{pmatrix} x_J \\ x_{\bar{J}} \end{pmatrix} + \begin{pmatrix} a_J \\ a_{\bar{J}} \end{pmatrix}^\top \begin{pmatrix} x_J \\ x_{\bar{J}} \end{pmatrix} + \begin{pmatrix} b_J \\ b_{\bar{J}} \end{pmatrix}^\top \begin{pmatrix} z_J \\ z_{\bar{J}} \end{pmatrix}. $$

Since MIQP (1), MILO (3), and MILO+ (12) share the same objective value $\mu$, relaxing the indicator constraint (1c) to (5) for a fixed index set $J$ provides a valid lower bound on $\mu$.

For fixed $(x_J, z_J)$ and continuous $z_J$, we first minimize over the continuous variables $x_{\bar{J}}$. This yields the following relaxed mixed-integer quadratic problem in $(x_J, z_J)$:

$$ \tilde{\mu} := -\frac{1}{2} a_{\bar{J}}^{\top} S^{-1} a_{\bar{J}} + \min_{x_J, z_J} \frac{1}{2} x_J^{\top} (P - T^{\top} S^{-1} T) x_J + c^{\top} x_J + b_J^{\top} z_J \\ \text{s.t.} \quad x_J \circ (\mathbf{1} - z_J) = 0. $$

By fixing $z_J = e_k$ for each feasible indicator vector and applying Lemma 1, we obtain

$$ \tilde{\mu} = -\frac{1}{2} a_{\bar{J}}^{\top} S^{-1} a_{\bar{J}} + \min_{(e_k, W_k) \in \mathcal{P}_J} \left\{ \frac{1}{2} c^{\top} W_k c + b_J^{\top} e_k \right\}. $$

Since optimizing a linear function over a discrete set is equivalent to optimizing it over the convex hull of that set. By the definition of $\mathcal{P}_J$, this yields

$$ \tilde{\mu} = -\frac{1}{2} a_{\bar{J}}^{\top} S^{-1} a_{\bar{J}} + \min_{\theta, W} \frac{1}{2} c^{\top} W_c c + b_J^{\top} z_J \\ \text{s.t.} \quad z_J = \sum_{k=1}^{K} \theta_k e_k, W = \sum_{k=1}^{K} \theta_k W_k, \sum_{k=1}^{K} \theta_k = 1. $$

Substituting $W$ using the above equality constraint and dualizing the resulting linear program with respect to $\theta$, where $\lambda \in \mathbb{R}^q$ and $\lambda_0 \in \mathbb{R}$ are the dual
variables associated with $z_J = \sum_{k=1}^K \theta_k e_k$ and $\sum_{k=1}^K \theta_k = 1$, respectively, yields the valid inequality (14). $\square$

Proposition 7 establishes a family of linear cuts for MILO (3) and MILO+ (12). Analogous to the quadratic cuts derived in Section 4, these linear cuts exploit the combinatorial structure induced by a selected subset of variables and are theoretically tight within the proposed framework.

In practice, the size of the index set $J$ is limited to maintain computational tractability; in particular, we restrict $q \le 6$ so that the number of enumerated cases remains manageable. Overall, the proposed linear cut-generation algorithm provides an efficient mechanism for recovering the tight SDP bound implied by (8b) using only linear inequalities.

## 5. Successive strengthenings

In this section, we present three practical settings to further enhance the linear reformulations MILO (3) and MILO+ (12) of MIQP (1). Under the $l_0$-regularized sparse linear regression setting (2), we propose a valid inequality, referred to as **nneg**, to improve the performance of MILO (3) and MILO+ (12). Moreover, exploiting the prior knowledge that the optimal solution $W$ in MILO (3) and MILO+ (12) admits a positive-definite characterization, we introduce a family of $2 \times 2$ structured inequalities, denoted as **aSDP**, which strengthen MILO (3) and MILO+ (12) via a set of explicit constraints. Finally, leveraging the symmetry of $W$, we discuss a practical implementation setting for MILO (3), referred to as **triW**.

**aSDP** denotes a group of $2 \times 2$ inequalities that are proved to be valid for both MILO (3) and MILO+ (12), as stated below:

**Proposition 8.** The inequalities (15) are valid for any $W \in \mathbb{S}_+^n$.

$$2|w_{ij}| \le w_{ii} + w_{jj}, \quad \forall i, j \in [n], i \le j. \qquad (15)$$

*Proof.* Given $W \in \mathbb{S}_+^n$, we consider all the $2 \times 2$ principal sub-matrices formed by the $i$-th and $j$-th rows and columns: $W_{ij} = \begin{pmatrix} w_{ii} & w_{ij} \\ w_{ij} & w_{jj} \end{pmatrix}$. Since $W_{ij} \in \mathbb{S}_+^2$, $\det(W_{ij}) = w_{ii}w_{jj} - w_{ij}^2 \ge 0$ must hold. Thus, we have $\sqrt{w_{ii}w_{jj}} \ge |w_{ij}|$. Using the AM-GM inequality, we have $\frac{w_{ii}+w_{jj}}{2} \ge \sqrt{w_{ii}w_{jj}} \ge |w_{ij}|$. Therefore, we prove that (15) is valid for any $W \in \mathbb{S}_+^n$. $\square$
Thus, it is valid to include the inequalities in (15), denoted as the aSDP method, in both MILO (3) and MILO+ (12) to further enforce the positive semidefiniteness of W.

nneg denotes the inequality constraint (16), given the context of (2).

**Proposition 9.** Let $W^*$ denote the optimal solution of both MILO (3) and MILO+ (12). Then $W^*$ satisfies the inequality (16).

$$a^{\top} W^* a \le \frac{1}{m} \|y\|_2^2. \qquad (16)$$

*Proof.* Let $(W^*, z^*)$ denote an optimal solution of MILO (3) and MILO+ (12), and let $(x^*, z^*)$ denote an optimal solution of MIQP (1). We have $-\frac{1}{2}a^{\top}W^*a+b^{\top}z^* = \frac{1}{2}x^{*\top}Qx^*+a^{\top}x^*+b^{\top}z^*$. Eliminating the common term $b^{\top}z^*$ on both sides, we get $-\frac{1}{2}a^{\top}W^*a = \frac{1}{2}x^{*\top}Qx^*+a^{\top}x^*$. Moreover, given $\frac{1}{2m}\|X\beta - y\|_2^2 + c\|\beta\|_2^2 \ge 0$ and denoting the optimal solution of the relaxation of (1c) as $\tilde{x}^*$ and $\tilde{x}^*$, from the definition of $Q$ and the notation transformation introduced in Section 2 we have $\frac{1}{2}x^{*\top}Qx^*+a^{\top}x^* \ge \frac{1}{2}\tilde{x}^{*\top}Q\tilde{x}^*+a^{\top}\tilde{x}^* = \min_{\beta} \beta^{\top}(\frac{1}{2m}X^{\top}X+cI)\beta - \frac{1}{m}y^{\top}X\beta \ge -\frac{1}{2m}\|y\|_2^2$. Therefore, we conclude that $a^{\top}W^*a \le \frac{1}{m}\|y\|_2^2$. $\square$

According to Proposition 9, adding constraint (16) does not prevent MILO (3) and MILO+ (12) from attaining the optimal solution. Therefore, it is a valid constraint for both formulations.

triW refers to reducing the symmetric matrix variable $W$ to its upper-triangular form. Since $W$ is inherently symmetric, triW is implemented by replacing its lower-triangular part with the corresponding upper-triangular entries, thereby eliminating redundant variables. Note that triW is considered only for MILO (3), as in MILO+ (12) the matrix $W$ is already explicitly defined to be symmetric, and therefore triW is not required.

## 6. Computational experiments

We conducted a series of computational experiments to evaluate the effectiveness of the proposed cuts within the B&C framework from multiple perspectives. The experiments are organized as follows. In Section 6.1, we first assess the impact of the three strengthening methods, triW, nneg, and aSDP, introduced in Section 5. We examine all possible combinations of these independent techniques to quantify their individual and joint contributions.
Due to the high computational cost of solving mixed-integer programming problems, only a subset of the best-performing base model-strengthening configurations was retained for further experiments. Section 6.2 investigates the effectiveness of the linear and quadratic cuts applied at the root node of MIQP (1), MILO (3), and MILO+ (12). We measure the optimality gap immediately after adding cuts at the root node and again after allowing the solver to execute the B&B procedure for 7,200 seconds. The results are compared against the corresponding unstrengthened B&B baseline models to quantify the improvement in relaxation tightness and solution quality. In Section 6.3, we evaluate the performance of linear cuts integrated into the B&C framework for MILO (3) and MILO+ (12). The cuts were implemented via a user-defined callback in CPLEX (Cplex, 2009), which invokes the cut-generation procedure at each node of the search tree to determine whether additional cuts can strengthen the local relaxation. We report the improvement in optimality gap closure compared to the default B&B algorithm. Finally, Section 6.4 provides a deeper analysis of the bound quality across different formulations. As noted in Wei et al. (2024), the MILO (3) formulation is weak in relaxation bounds. We strengthen both MILO (3) and MILO+ (12) using several linear cuts and compare the resulting bounds with those obtained from MIQP (1) with big-M constraints. Our results indicate that with only a few additional cuts, the strengthened MILO (3) and MILO+ (12) formulations can yield tighter bounds than the MIQP (1) formulation.

*Simulated data.* All experiments were performed on simulated data generated by two distinct data generators. We simulated datasets $(X, y)$ using two generators, denoted as $\mathbb{G}_1$ and $\mathbb{G}_2$. All the datasets were generated by sampling $\beta \sim \mathcal{N}(0_n, I_n/\tau_1)$ with a noise $\varepsilon \sim \mathcal{N}(0_m, I_m/\tau_2)$ and by computing $y = X\beta + \varepsilon$. The matrix $X$ itself is generated from a Gaussian distribution with zero mean and a covariance matrix $R$. For $\mathbb{G}_1$, $R$ is set to $R = \text{diag}(R^1, R^2)$, a 2-block diagonal matrix, where $R^l$ is such that $R_{ii}^l = 1$ and $R_{ij}^l = \rho$ for $i, j \in [n/2]$ and $i \neq j$. For $\mathbb{G}_2$, a matrix $\tilde{R}$ is first built with each element sampled randomly and independently. Then, each element is set to 10 with probability 1/2 and to 0.01 otherwise. $R$ is finally built by symmetrizing $\tilde{R}$ and by setting each diagonal element to $R_{ii} = \sum_{j=1}^n R_{ij} + 1$. For both $\mathbb{G}_1$ and $\mathbb{G}_2$, we set $\tau_1 = \tau_2 = 1$ and $\rho = 0.75$. The data matrix $X \in \mathbb{R}^{m \times n}$ has size either 10 × 50 or 20 × 70, and to simulate solving a convex
problem, an identity matrix with coefficient 1 is added to $\frac{1}{m}X^\top X$ to make sure that $Q \in S_n^{++}$.

*Computational Environment.* All numerical experiments were conducted on an Intel(R) Xeon(R) CPU E5-2670 @ 2.60GHz processor. The computations were performed on the ISIMA computing cluster (https://hpc.isima.fr/doku.php?id(start). For experiments involving user-defined cut callbacks, we allocated one computing thread per task, and for all other experiments, we allocated 12 computing threads per task. Each task was allocated 16 GB of RAM. The optimization solver used was CPLEX 12.10 (Cplex, 2009).

## 6.1. Linear model strengthening and selection

In this section, we evaluated all combinations of the three methods proposed in Section 5 to investigate their individual and joint effects. The resulting improvements in relaxation bounds and changes in running time are reported in Table 1.

<table><caption>Table 1: Compared with MILO with no strengthening method (labeled as “-” in the table), the expected values (in %) of the improvements in relaxation bounds and the changes in running time over 10 repeated runs are reported. The underlined numbers in the *bound_imp* columns indicate the best-performing four strategies in terms of bound improvement, while the underlined numbers in the *time* column indicate the strategies that lead to reduced running time, for each data generator respectively.</caption><thead><tr><th rowspan="2">data</th><th rowspan="2">methods</th><th colspan="2">MILO</th><th colspan="2">MILO+</th></tr><tr><th>bound_imp</th><th>time</th><th>bound_imp</th><th>time</th></tr></thead><tbody><tr><td rowspan="7">G<sub>1</sub></td><td>-</td><td>-</td><td>-</td><td>99.86</td><td>10964.92</td></tr><tr><td>aSDP</td><td>0.62</td><td>14.78</td><td>99.87</td><td>10138.69</td></tr><tr><td>nneg</td><td>100+8.0e-11</td><td>28.39</td><td>100+5.5e-11</td><td>417.97</td></tr><tr><td>aSDP&amp;nneg</td><td>100+8.4e-11</td><td>85.92</td><td>100+5.5e-11</td><td>82.79</td></tr><tr><td>triW</td><td>10.20</td><td>15.01</td><td></td><td></td></tr><tr><td>aSDP&amp;triW</td><td>10.44</td><td>50.61</td><td></td><td></td></tr><tr><td>nneg&amp;triW</td><td>100+9.0e-11</td><td>107.89</td><td></td><td></td></tr><tr><td rowspan="7">G<sub>2</sub></td><td>triW&amp;nneg&amp;aSDP</td><td>100+9.9e-11</td><td>430.37</td><td></td><td></td></tr><tr><td>-</td><td>-</td><td>-</td><td>55.17</td><td>1905.18</td></tr><tr><td>aSDP</td><td>15.03</td><td>8.01</td><td>55.32</td><td>1928.58</td></tr><tr><td>nneg</td><td>100+5.3e-3</td><td>-18.12</td><td>100+3.5e-3</td><td>539.00</td></tr><tr><td>aSDP&amp;nneg</td><td>100+6.0e-3</td><td>-11.46</td><td>100+3.5e-3</td><td>558.40</td></tr><tr><td>triW</td><td>37.05</td><td>16.65</td><td></td><td></td></tr><tr><td>aSDP&amp;triW</td><td>51.28</td><td>51.65</td><td></td><td></td></tr><tr><td>nneg&amp;triW</td><td>100+6.2e-3</td><td>66.93</td><td></td><td></td></tr><tr><td>triW&amp;nneg&amp;aSDP</td><td>100+7.5e-3</td><td>100.66</td><td></td><td></td></tr></tbody></table>

The values presented in Table 1 were computed as the average of 100% × $\frac{(\text{model's bound}) - (\text{MILO bound})}{|\text{MILO bound}|}$ over 10 instances of data sampled under identi-
cal settings by each data generator. The results demonstrate the effective-
ness of the strengthening methods proposed in Section 5, as all the meth-
ods and their combinations can improve the bound of both MILO (3) and
MILO+ (12). It is noteworthy that when the **nneg** method is applied, im-
provements exceeding 100% in the objective value can be achieved. More-
over, in the configurations with **nneg** and **aSDP&nneg**, the running time
is even reduced, which indicates a smaller search tree in the B&C frame-
work. Even without any strengthening methods, MILO+ (12) outperformed
MILO (3) in terms of bound quality. When the strengthening methods were
applied, MILO+ (12) achieved at least the same level of enhancement as
MILO (3), though it generally required longer computational time.

To comprehensively evaluate the models and the proposed strengthening
methods, we considered both bound improvement and computational time as
selection criteria. Based on the results in Table 1, we selected the MILO (3)
and MILO+ (12) models with the following strengthening configurations:
nneg, aSDP&nneg, triW&nneg, and triW&nneg&aSDP.

6.2. Applying cuts at root node

In this section, we conducted experiments applying both linear and quadratic
cuts at the root node of the three distinct models, MILO (3), MILO+ (12),
and MIQP (1). For the linear models, the strengthening methods selected in
Section 6.1 were incorporated. Since the cuts were added at the root node,
they remained active throughout the B&B process. We recorded the rela-
tive optimality gap immediately after strengthening the root node with cuts
and again at the end of a 7,200-second time limit. The relative optimality
gap was computed as $\frac{|LB-UB|}{|10^{-10}|+|UB|}$. All results were compared against those
obtained from the baseline B&B algorithm.

As discussed in Section 3, it is necessary to select a specific subset of
indices *J* in order to generate a corresponding cut. In practice, we adopted
a heuristic hierarchical strategy for selecting the subset *J*. This hierarchical
approach consists of three independent subset selection strategies, described
as follows:

**Strategy 1.** Select the indices with the highest total correlation with other variables, based on the data matrix *Q*.

**Strategy 2.** Select the indices corresponding to the most fractional relaxed indicator variables in the current incumbent solution.
**Strategy 3.** *Select a random subset of indices.*

The hierarchical design aims to both make full use of the information pro-
vided in the data matrix and prevent repeatedly selecting the same subset *J*
during the experiments, as reusing an identical *J* would generate duplicate
cuts. In practice, Strategy 1 can produce only one subset *J* per dataset.
Moreover, we observed that the subset selected by Strategy 2 sometimes
tends to remain unchanged. Therefore, we applied Strategy 2 only once,
and subsequently switched to Strategy 3, which consistently generates non-
duplicate subsets *J*. We also observed that not all subsets *J* yield effective
linear cuts, even when they have not been previously used. By contrast, a
previously unused subset *J* almost always produces a contributing quadratic
cut, although the improvement in bound tightness may be marginal. Another
key factor influencing the quality of the cuts is the size of *J*, denoted by *q*. To
maintain the tractability of the separation problem whose complexity grows
exponentially in 2<sup>q</sup>, the value of *q* must remain small.

Based on these observations and the inherent differences between the
linear and quadratic models, we defined distinct termination criteria for the
cut-generation algorithms. For the linear models, the algorithm terminates
once the number of non-contributing cuts reaches a predefined threshold T.
For the quadratic model, termination occurs when the number of contribut-
ing cuts reaches a threshold T̂.

In the remainder of this section, we present experimental results on four
datasets generated by G₁ and G₂, with dimensions 10 × 50 and 20 × 70,
respectively. We varied *q* from 2 to 6, with *T* set to 10 and T̂ set to 5. For
the MIQP (1) model, the big-M constant was set to *M* := λ⁺(*Q*⁻¹) ||*a*||₂ (Wei
et al., 2024).

From Table 2, we observe that for most models under the current set-
tings, applying cuts at the root node leads to a substantial reduction in the
relative optimality gap immediately after root-node strengthening compared
with the non-strengthened models. This confirms the effectiveness of the
proposed cuts in improving the relaxation bound. Moreover, a higher value
of *q* generally produces stronger cuts, resulting in greater reductions in the
relative gap. Compared with the linear cuts, the effect of the strengthening
methods appears to be mild. For the quadratic model, the improvement
achieved by applying quadratic cuts at the root node is more pronounced
for datasets generated by G₂, as evidenced by a clearer reduction in the
<table><caption>Table 2: Relative gap (%) immediately after the root node was strengthened by the cuts. The first column shows the generator and size (the number of rows and the number of columns) of the corresponding data. The row where *q* is indicated as “-” corresponds to the baseline relative gap obtained from the vanilla B&B algorithm. Cells labeled with an “-” mean that the relative gap values exceed 1000. The underlined numbers indicate the best-performing model and the corresponding value of *q* for each data and base model combination.</caption><thead><tr><th rowspan="2">data</th><th rowspan="2">q</th><th colspan="4">MILO</th><th colspan="2">MILO+</th><th>MIQP</th></tr><tr><th>nneg</th><th>nneg&amp;aSDP</th><th>nneg&amp;triW</th><th>nneg&amp;triW&amp;aSDP</th><th>nneg</th><th>nneg&amp;aSDP</th><th>-</th></tr></thead><tbody><tr><td rowspan="6">G<sub>1</sub>_10_50</td><td>-</td><td>0.25</td><td>0.12</td><td>0.23</td><td>0.21</td><td>-</td><td>-</td><td>0.05</td></tr><tr><td>2</td><td>0.03</td><td>0.46</td><td>0.09</td><td>0.04</td><td>-</td><td>-</td><td>0.05</td></tr><tr><td>3</td><td>0.03</td><td>0.45</td><td>0.08</td><td>0.04</td><td>-</td><td>-</td><td>0.05</td></tr><tr><td>4</td><td>0.03</td><td>0.37</td><td>0.09</td><td>0.04</td><td>-</td><td>-</td><td>0.05</td></tr><tr><td>5</td><td>0.03</td><td>0.41</td><td>0.15</td><td>0.04</td><td>-</td><td>-</td><td>0.05</td></tr><tr><td>6</td><td><u>0.02</u></td><td>0.43</td><td>0.07</td><td>0.03</td><td>-</td><td>-</td><td>0.05</td></tr><tr><td rowspan="6">G<sub>1</sub>_20_70</td><td>-</td><td>127.13</td><td>69.98</td><td>29.03</td><td>4.11</td><td>-</td><td>-</td><td>0.04</td></tr><tr><td>2</td><td>0.03</td><td>-</td><td>-</td><td>300.30</td><td>159.13</td><td>-</td><td>0.04</td></tr><tr><td>3</td><td>0.03</td><td>-</td><td>-</td><td>-</td><td>159.13</td><td>-</td><td>0.04</td></tr><tr><td>4</td><td>0.02</td><td>-</td><td>-</td><td>-</td><td>159.13</td><td>-</td><td>0.04</td></tr><tr><td>5</td><td>0.02</td><td>-</td><td>-</td><td>-</td><td>159.13</td><td>-</td><td>0.04</td></tr><tr><td>6</td><td><u>0.02</u></td><td>-</td><td>-</td><td>-</td><td><u>159.09</u></td><td>-</td><td>0.04</td></tr><tr><td rowspan="6">G<sub>2</sub>_10_50</td><td>-</td><td>407.57</td><td>-</td><td>10.72</td><td>60.02</td><td>-</td><td>-</td><td>5.13</td></tr><tr><td>2</td><td>6.65</td><td>6.52</td><td>6.30</td><td>17.00</td><td>19.61</td><td>17.68</td><td>5.20</td></tr><tr><td>3</td><td>6.37</td><td>4.93</td><td>6.02</td><td>3.96</td><td>15.07</td><td>14.18</td><td>4.37</td></tr><tr><td>4</td><td>6.09</td><td>3.44</td><td>5.75</td><td>6.15</td><td>13.55</td><td>12.43</td><td>4.15</td></tr><tr><td>5</td><td>4.49</td><td>4.95</td><td>5.48</td><td>11.62</td><td>12.33</td><td>9.93</td><td>4.85</td></tr><tr><td>6</td><td>5.63</td><td>5.54</td><td>5.28</td><td>3.09</td><td>11.86</td><td><u>7.52</u></td><td>3.85</td></tr><tr><td rowspan="6">G<sub>2</sub>_20_70</td><td>-</td><td>208.09</td><td>573.99</td><td>335.76</td><td>249.64</td><td>-</td><td>-</td><td>115.15</td></tr><tr><td>2</td><td>111.72</td><td>90.00</td><td>189.29</td><td>90.23</td><td>73.47</td><td>84.05</td><td>51.29</td></tr><tr><td>3</td><td>110.36</td><td>94.22</td><td>110.91</td><td>71.27</td><td>76.17</td><td>216.76</td><td>44.78</td></tr><tr><td>4</td><td>107.15</td><td><u>63.02</u></td><td>116.32</td><td>111.32</td><td>83.52</td><td><u>59.78</u></td><td>40.56</td></tr><tr><td>5</td><td>110.62</td><td>82.38</td><td>108.66</td><td>111.31</td><td>80.36</td><td>154.01</td><td><u>38.74</u></td></tr><tr><td>6</td><td>100.96</td><td>119.77</td><td>94.01</td><td>73.43</td><td>72.67</td><td>128.47</td><td>139.57</td></tr></tbody></table>

optimality gap, whereas this effect is less evident for data generated by $G_1$.

From Table 3, we observe that for all linear models, under the current experimental settings, applying cuts at the root node clearly accelerates the reduction of the relative optimality gap compared with the non-strengthened B&B models. The general trend that larger values of *q* lead to more effective cuts still holds, as evidenced by the smaller remaining relative gaps when the time limit is reached. Among the linear base models, MILO+ (12) tends to close the gap more slowly than MILO (3) and occasionally fails to process strengthened root nodes, which can be attributed to the additional complexity in describing the model. For the quadratic model, the non-strengthened model achieves the best overall performance. This suggests that, as expected, extra quadratic inequalities impose a considerable computational burden, thereby limiting its ability to explore a sufficient number of sub-problems within the allocated time.
<table><caption>Table 3: Relative gap (%) when the time limit (7200 seconds) is reached. The row where *q* is indicated as “-” corresponds to the baseline relative gap obtained from the non-strengthened models. Cells labeled with an “-” mean that the relative gap values exceed 1000. The underlined numbers indicate the best-performing model and the corresponding value of *q* for each data and base model combination.</caption><thead><tr><th rowspan="2">data</th><th rowspan="2">q</th><th colspan="4">MILO</th><th colspan="2">MILO+</th><th>MIQP</th></tr><tr><th>nneg</th><th>nneg&amp;aSDP</th><th>nneg&amp;triW</th><th>nneg&amp;triW&amp;aSDP</th><th>nneg</th><th>nneg&amp;aSDP</th><th>-</th></tr></thead><tbody><tr><td rowspan="6">G<sub>1</sub>_10_50</td><td>-</td><td>0.08</td><td>0.08</td><td>0.08</td><td>0.08</td><td>1.44</td><td>0.52</td><td>0.00</td></tr><tr><td>2</td><td>0.02</td><td>0.01</td><td>0.02</td><td>0.01</td><td>0.13</td><td>0.16</td><td>0.00</td></tr><tr><td>3</td><td>0.01</td><td>0.02</td><td>0.01</td><td>0.01</td><td>0.09</td><td>0.10</td><td>0.00</td></tr><tr><td>4</td><td>0.02</td><td>0.12</td><td>0.02</td><td>0.02</td><td>0.13</td><td>0.16</td><td>0.00</td></tr><tr><td>5</td><td>0.02</td><td>0.01</td><td>0.06</td><td>0.01</td><td>0.15</td><td>0.23</td><td>0.00</td></tr><tr><td>6</td><td>0.01</td><td><u>0.00</u></td><td><u>0.00</u></td><td><u>0.00</u></td><td><u>0.03</u></td><td>0.28</td><td>0.00</td></tr><tr><td rowspan="6">G<sub>1</sub>_20_70</td><td>-</td><td>0.11</td><td>0.10</td><td>0.17</td><td>0.20</td><td>495.20</td><td>237.49</td><td><u>0.00</u></td></tr><tr><td>2</td><td><u>0.02</u></td><td>0.12</td><td>0.47</td><td>0.10</td><td>159.13</td><td>-</td><td>0.01</td></tr><tr><td>3</td><td><u>0.02</u></td><td>0.04</td><td>0.20</td><td>0.06</td><td>159.13</td><td>-</td><td>0.01</td></tr><tr><td>4</td><td><u>0.02</u></td><td>0.06</td><td>0.24</td><td>0.08</td><td>159.13</td><td>-</td><td>0.01</td></tr><tr><td>5</td><td><u>0.02</u></td><td>0.05</td><td>0.22</td><td>0.34</td><td>159.13</td><td>-</td><td>0.01</td></tr><tr><td>6</td><td><u>0.02</u></td><td>0.19</td><td>0.31</td><td>0.09</td><td><u>159.09</u></td><td>-</td><td>0.01</td></tr><tr><td rowspan="6">G<sub>2</sub>_10_50</td><td>-</td><td>7.28</td><td>7.39</td><td>7.32</td><td>7.30</td><td>9.02</td><td>11.73</td><td><u>0.00</u></td></tr><tr><td>2</td><td>2.95</td><td>2.83</td><td>2.95</td><td>2.95</td><td>3.66</td><td>3.73</td><td>0.86</td></tr><tr><td>3</td><td>2.68</td><td>2.28</td><td>2.68</td><td>2.68</td><td>3.23</td><td>3.43</td><td>0.76</td></tr><tr><td>4</td><td>2.42</td><td>2.22</td><td>2.42</td><td>2.42</td><td><u>2.98</u></td><td>3.00</td><td>0.81</td></tr><tr><td>5</td><td>2.16</td><td>2.16</td><td>2.16</td><td>2.16</td><td>3.64</td><td>3.08</td><td>1.02</td></tr><tr><td>6</td><td>1.97</td><td>1.88</td><td>1.97</td><td>1.98</td><td>3.69</td><td>3.03</td><td>1.15</td></tr><tr><td rowspan="6">G<sub>2</sub>_20_70</td><td>-</td><td>119.82</td><td>121.88</td><td>133.44</td><td>120.94</td><td>526.58</td><td>266.83</td><td><u>6.84</u></td></tr><tr><td>2</td><td>29.30</td><td>35.30</td><td>28.34</td><td>30.50</td><td>73.47</td><td>84.05</td><td>25.69</td></tr><tr><td>3</td><td>27.85</td><td>28.56</td><td>27.06</td><td>33.51</td><td>76.17</td><td>216.76</td><td>14.70</td></tr><tr><td>4</td><td>26.30</td><td>24.63</td><td>26.98</td><td>24.24</td><td>83.52</td><td><u>59.78</u></td><td>21.35</td></tr><tr><td>5</td><td>23.51</td><td>27.11</td><td>24.90</td><td>29.57</td><td>80.36</td><td>154.01</td><td>14.60</td></tr><tr><td>6</td><td><u>20.85</u></td><td>24.09</td><td>22.50</td><td>22.09</td><td>72.67</td><td>128.47</td><td>14.66</td></tr></tbody></table>

In summary, from Tables 2 and 3, the effectiveness of both linear and quadratic cuts in tightening the root-node relaxation is evident. For the linear models, these cuts also substantially accelerate the discovery of the exact optimal solution. For the quadratic model, the advantage in gap reduction achieved by applying quadratic cuts at the root node does not persist once the time limit is reached. We emphasize that our analysis focuses on observed performance trends rather than a direct comparison of the remaining optimality gaps between the linear and quadratic models, since the termination criteria and the number of applied cuts differ across these two formulation families.

### 6.3. Applying linear cuts as user-defined callback

In this section, we present experiments in which the linear cut-generation algorithm was implemented as a user-defined cut callback—an advanced feature supported by CPLEX (Cplex, 2009) within the B&C framework for
MILO (3) and MILO+ (12). During the solution process of the mixed-integer programming problem, the solver invoked the callback at each node of the search tree to check whether a valid cut could be generated. Whenever a valid cut was found, it was retained and enforced throughout the remainder of the B&C process.

The selection of *J* followed the same principles as those described in Section 6.2. When the callback function was invoked for the first time globally, it selected the subset *J* according to Strategy 1, which was based on the sum of variable correlations derived from the matrix *Q*. Strategy 1 was executed only once. Subsequently, at each node, the callback selected *J* according to Strategy 2, identifying the indices corresponding to the most fractional indicator variables in the incumbent solution at that node. If Strategy 2 produced a duplicate *J*, the callback switched to Strategy 3, which randomly selected a non-duplicate subset *J*.

All experiments were executed in a single-thread mode due to the nature of the user-defined callback. The subset size *q* still ranged from 2 to 6. Extreme values were used for the solver's integrality and feasibility tolerances to ensure numerical robustness and the correctness of the generated cuts. The relative optimality gap was computed in the same manner as described in Section 6.2, and gap information was recorded every two nodes through an information callback. For each of the 10 repeated runs on identically simulated data, the results were first linearly interpolated and then averaged across all runs.

Figure 1 illustrates that, for all models integrated with the user-defined cut callback, the relative optimality gap closed more rapidly than under the B&B algorithm. This confirms that the cuts generated through the callback were effective in pruning the search tree. Among the base models, MILO (3) with strengthening methods closed the gap more quickly than those based on MILO+ (12). A mild trend with respect to *q* can also be observed: models with larger *q* values (e.g., 5 or 6) tend to reduce the relative gap more rapidly, owing to the stronger cuts derived from larger subsets. The differences among the six combinations of strengthening methods, however, remain too subtle to be clearly distinguished under the effect brought by the cuts.
<figure><img src="image_3.png" /><figcaption>Figure 1: The evolution of the average relative gap (%) over 10 identically generated data by $G_1$ over a time limit of 7200 seconds for the selected models and the vanilla B&B algorithm is shown. B&B refers to the standard branch-and-bound algorithm without user-defined cuts. The other curves, labeled by the value of $q$, correspond to experiments using user-defined cut callbacks in the B&C framework with the indicated $q$.</figcaption></figure>

## 6.4. Bound improvements from cuts in linear models

We next evaluate the bound-tightening potential of MILO (3) and MILO+ (12) when incorporating the proposed cuts. In particular, we compare their improved bounds against the baseline relaxation bound of MIQP (1), which is known to provide stronger relaxations than the corresponding linear models. The big-M value for the MIQP (1) formulation was set to $M := \lambda_+(Q^{-1}) \|a\|_2$. All experiments were conducted on the same datasets as those used in Section 6.1.

As shown in Table 4, before incorporating the cuts, all linear models selected from Section 6.1 were substantially weaker than the MIQP (1) model in terms of relaxation bounds. After incorporating the cuts, however, their bounds surpassed those of the MIQP (1) model, regardless of the data generator. Among all model configurations, MILO+ (12) with the strengthening methods achieved the greatest improvement in bound quality. The trend observed in Section 6.2 persists: as the value of $q$ increases, the improvement in the bound becomes consistently more pronounced, independent of the model type or the termination threshold $T$.
<table><caption>Table 4: Mean(%) of the improvements in relaxation bounds over 10 repeat runs. The values reported are computed as $100 \times \frac{(\text{base model} + \text{CUTS bound}) - (\text{Big-M bound})}{|\text{Big-M bound}|}$. The row where $q$ is indicated as “-” corresponds to the improvement of models that do not incorporate any cuts. The underlined numbers indicate the best improvement for each experimental setting across different values of $q$.</caption><thead><tr><th rowspan="2">data</th><th rowspan="2">T</th><th rowspan="2">q</th><th colspan="4">MILO</th><th colspan="2">MILO+</th></tr><tr><th>nneg</th><th>nneg&amp;aSDP</th><th>nneg&amp;triW</th><th>nneg&amp;triW&amp;aSDP</th><th>nneg</th><th>nneg&amp;aSDP</th></tr></thead><tbody><tr><td rowspan="6">G<sub>1</sub></td><td rowspan="6">10</td><td>-</td><td>-100.00</td><td>-100.00</td><td>-100.00</td><td>-100.00</td><td>-100.00</td><td>-100.00</td></tr><tr><td>2</td><td>26.70</td><td>27.40</td><td>27.48</td><td>24.83</td><td>26.66</td><td>26.22</td></tr><tr><td>3</td><td>29.72</td><td>30.80</td><td>30.28</td><td>30.24</td><td>30.80</td><td>31.06</td></tr><tr><td>4</td><td>33.73</td><td>34.30</td><td>33.89</td><td>34.21</td><td>32.55</td><td>34.41</td></tr><tr><td>5</td><td>39.35</td><td>38.91</td><td>38.80</td><td>39.12</td><td>39.24</td><td>39.24</td></tr><tr><td>6</td><td>39.31</td><td>39.43</td><td>39.28</td><td>39.24</td><td><u>39.59</u></td><td>39.47</td></tr><tr><td rowspan="6">20</td><td rowspan="6"></td><td>2</td><td>29.93</td><td>29.91</td><td>30.19</td><td>29.83</td><td>30.53</td><td>30.29</td></tr><tr><td>3</td><td>31.42</td><td>31.64</td><td>31.33</td><td>31.29</td><td>31.49</td><td>31.75</td></tr><tr><td>4</td><td>34.33</td><td>34.30</td><td>33.89</td><td>34.21</td><td>33.99</td><td>34.45</td></tr><tr><td>5</td><td>39.63</td><td>39.63</td><td>39.55</td><td>40.13</td><td>40.50</td><td><u>40.51</u></td></tr><tr><td>6</td><td>39.95</td><td>40.07</td><td>39.92</td><td>39.88</td><td>40.23</td><td>40.11</td></tr><tr><td rowspan="6">G<sub>2</sub></td><td rowspan="6">10</td><td>-</td><td>-99.12</td><td>-98.96</td><td>-98.94</td><td>-98.62</td><td>-99.52</td><td>-99.52</td></tr><tr><td>2</td><td>141.95</td><td>155.29</td><td>141.95</td><td>142.09</td><td>148.75</td><td>147.32</td></tr><tr><td>3</td><td>157.60</td><td>165.81</td><td>157.60</td><td>154.98</td><td>167.72</td><td>165.20</td></tr><tr><td>4</td><td>175.88</td><td>175.88</td><td>175.88</td><td>179.84</td><td>181.99</td><td>184.58</td></tr><tr><td>5</td><td>170.40</td><td>169.80</td><td>170.40</td><td>173.22</td><td>178.02</td><td>175.26</td></tr><tr><td>6</td><td>225.27</td><td>194.89</td><td>225.27</td><td>232.83</td><td><u>234.29</u></td><td>231.79</td></tr><tr><td rowspan="6">20</td><td rowspan="6"></td><td>2</td><td>162.30</td><td>162.30</td><td>162.30</td><td>162.30</td><td>162.36</td><td>162.36</td></tr><tr><td>3</td><td>176.11</td><td>176.11</td><td>176.11</td><td>176.23</td><td>179.71</td><td>179.71</td></tr><tr><td>4</td><td>183.32</td><td>183.32</td><td>183.32</td><td>182.35</td><td>184.58</td><td>184.58</td></tr><tr><td>5</td><td>197.31</td><td>199.91</td><td>197.31</td><td>202.89</td><td>202.89</td><td>201.70</td></tr><tr><td>6</td><td>230.21</td><td>230.21</td><td>230.21</td><td>232.83</td><td><u>339.12</u></td><td>296.05</td></tr></tbody></table>

## 7. Conclusions

In this paper, we have presented two cut-generation algorithms based on the partial convexification strategy. We first established the theoretical foundation for explicitly constructing convex hulls in both the original and extended variable spaces, from which two classes of cut-generation algorithms were developed. As shown in Section 6, the effectiveness of the linear cuts is evident from multiple perspectives. Their quadratic counterparts also demonstrate strong capability in strengthening the relaxation bounds. We also introduced an alternative linear reformulation, MILO+ (12) for MIQP (1). Within the context of $l_0$-regularized sparse linear regression, we proposed three successive strengthening methods applicable to both MILO (3) and MILO+ (12). Extensive computational experiments demonstrate that the proposed linear cut-generation algorithms effectively accelerate the closure of the optimality gap for moderately sized instances. From
a practical perspective, the heuristic selection of the index set *J* remains an
open direction for further investigation.

References

Aguilera, R.P., Urrutia, G., Delgado, R.A., Dolz, D., Agüero, J.C., 2017. Quadratic model predictive control including input cardinality constraints. IEEE Transactions on Automatic Control 62, 3068–3075.

Aktürk, M.S., Atamtürk, A., Gürel, S., 2009. A strong conic quadratic reformulation for machine-job assignment with controllable processing times. Operations Research Letters 37, 187–191.

Anstreicher, K.M., Burer, S., 2021. Quadratic optimization with switching variables: the convex hull for n= 2. Mathematical Programming 188, 421–441.

Atamtürk, A., Gómez, A., 2018. Strong formulations for quadratic optimization with m-matrices and indicator variables. Mathematical Programming 170, 141–176.

Atamturk, A., Gomez, A., 2019. Rank-one convexification for sparse regression. arXiv preprint arXiv:1901.10334.

Atamtürk, A., Gómez, A., 2023. Supermodularity and valid inequalities for quadratic optimization with indicators. Mathematical Programming 201, 295–338.

Atamturk, A., Gómez, A., Han, S., 2021. Sparse and smooth signal estimation: Convexification of 10-formulations. Journal of Machine Learning Research 22, 1–43.

Balas, E., 1979. Disjunctive programming. Annals of discrete mathematics 5, 3–51.

Balas, E., Ceria, S., Cornuéjols, G., 1993. A lift-and-project cutting plane algorithm for mixed 0-1 programs. Mathematical programming 58, 295-324.

Bertsimas, D., Cory-Wright, R., 2022. A scalable algorithm for sparse portfolio selection. INFORMS Journal on Computing 34, 1489–1511.

Bertsimas, D., King, A., Mazumder, R., 2016. Best subset selection via a modern optimization lens. The Annals of Statistics 44, 813–852.

Bertsimas, D., Van Parys, B., 2020. Sparse high-dimensional regression. The Annals of Statistics 48, 300–323.
Blackburn, L., Young, A., Rogers, P., Hedengren, J., Powell, K., 2019. Dynamic optimization of a district energy system with storage using a novel mixed-integer quadratic programming algorithm. Optimization and Engineering 20, 575-603.

Bourguignon, S., Ninin, J., Carfantan, H., Mongeau, M., 2015. Exact sparse approximation problems via mixed-integer programming: Formulations and computational performance. IEEE Transactions on Signal Processing 64, 1405-1419.

Chen, X., Ge, D., Wang, Z., Ye, Y., 2014. Complexity of unconstrained minimization. Mathematical Programming 143, 371-383.

Chicoisne, R., 2020. Cutting planes for mathematical programming: Separation from convex hulls. HAL preprint hal-02982831v2.

Cozad, A., Sahinidis, N.V., Miller, D.C., 2014. Learning surrogate models for simulation-based optimization. AIChE Journal 60, 2211-2227.

Cplex, I.I., 2009. V12. 1: User's manual for CPLEX. International Business Machines Corporation 46, 157.

Frangioni, A., Gentile, C., 2006. Perspective cuts for a class of convex 0-1 mixed integer programs. Mathematical Programming 106, 225-236.

Frangioni, A., Gentile, C., Hungerford, J., 2020. Decompositions of semidefinite matrices and the perspective reformulation of nonseparable quadratic programs. Mathematics of Operations Research 45, 15-33.

Glover, F., 1975. Improved linear integer programming formulations of non-linear integer problems. Management science 22, 455-460.

Gómez, A., 2021. Strong formulations for conic quadratic optimization with indicator variables. Mathematical Programming 188, 193-226.

Gomory, R.E., 2009. Outline of an algorithm for integer solutions to linear programs and an algorithm for the mixed integer problem, in: 50 Years of Integer Programming 1958-2008: From the Early Years to the State-of-the-Art. Springer, pp. 77-103.

Günlük, O., Linderoth, J., 2008. Perspective relaxation of mixed integer nonlinear programs with indicator variables, in: International Conference on Integer Programming and Combinatorial Optimization, Springer. pp. 1-16.

Günlük, O., Linderoth, J., 2010. Perspective reformulations of mixed integer nonlinear programs with indicator variables. Mathematical programming 124, 183-205.
Günlük, O., Linderoth, J., 2011. Perspective reformulation and applications, in: Mixed integer nonlinear programming. Springer, pp. 61–89.

Han, S., Gómez, A., Atamtürk, A., 2023. 2×2-convexifications for convex quadratic optimization with indicator variables. Mathematical Programming 202, 95–134.

Hastie, T., Tibshirani, R., Friedman, J.H., Friedman, J.H., 2009. The elements of statistical learning: data mining, inference, and prediction. volume 2. Springer.

Jeon, H., Linderoth, J., Miller, A., 2017. Quadratic cone cutting surfaces for quadratic programs with on-off constraints. Discrete Optimization 24, 32–50.

Liu, P., Fattahi, S., Gómez, A., Küçükyavuz, S., 2023. A graph-based decomposition method for convex quadratic optimization with indicators. Mathematical Programming 200, 669–701.

Lodi, A., Tanneau, M., Vielma, J.P., 2023. Disjunctive cuts in mixed-integer conic optimization. Mathematical Programming 199, 671–719.

Parija, G., Gadidov, R., Wilhelm, W., 1999. A facet generation procedure for solving 0/1 integer programs. Operations Research 47, 789–791.

Sherali, H.D., Lee, Y., Kim, Y., 2005. Partial convexification cuts for 0-1 mixed-integer programs. European journal of operational research 165, 625–648.

Stubbs, R.A., Mehrotra, S., 1999. A branch-and-cut method for 0-1 mixed convex programming. Mathematical programming 86, 515–532.

Wei, L., Atamtürk, A., Gómez, A., Küçükyavuz, S., 2024. On the convex hull of convex quadratic optimization problems with indicators. Mathematical Programming 204, 703–737.

Wei, L., Gómez, A., Küçükyavuz, S., 2022. Ideal formulations for constrained convex optimization problems with indicator variables. Mathematical Programming 192, 57–88.

Zhang, F., 2006. The Schur complement and its applications. volume 4. Springer Science & Business Media.

Zheng, X., Sun, X., Li, D., 2014. Improving the performance of miqp solvers for quadratic programs with cardinality and minimum threshold constraints: A semidefinite program approach. INFORMS Journal on Computing 26, 690–703.