Efficient Separation of RLT Cuts for Implicit and Explicit Bilinear Products

Abstract

The reformulation-linearization technique (RLT) is a prominent approach to constructing tight linear relaxations of non-convex continuous and mixed-integer optimization problems. The goal of this paper is to extend the applicability and improve the performance of RLT for bilinear product relations. First, a method for detecting bilinear product relations implicitly contained in mixed-integer linear programs is developed based on analyzing linear constraints with binary variables, thus enabling the application of bilinear RLT to a new class of problems. Our second contribution addresses the high computational cost of RLT cut separation, which presents one of the major difficulties in applying RLT efficiently in practice. We propose a new RLT cutting plane separation algorithm which identifies combinations of linear constraints and bound factors that are expected to yield an inequality that is violated by the current relaxation solution. A detailed computational study based on implementations in two solvers evaluates the performance impact of the proposed methods.

1 Introduction

The reformulation-linearization technique (RLT) was first proposed by Adams and Sherali [1,2,3] for bilinear problems with binary variables, and has been applied to mixed-integer [18,19,20], general bilinear [21] and polynomial [24] problems. RLT constructs valid polynomial constraints, then linearizes these constraints by using nonlinear relations given in the problem and applying relaxations when such relations are not available. If relations used in the linearization step are violated by a relaxation solution, this procedure may yield violated cuts. By increasing the degree of derived polynomial constraints, hierarchies of relaxations can be constructed, which were shown to converge to the convex hull representation of MILPs and mixed-integer polynomial problems where continuous variables appear linearly [18,19,20].

RLT has been shown to provide strong relaxations [21, 23], but this comes at the cost of excessive numbers of cuts. To address this, Sherali and Tuncbilek [25] proposed a technique to add a subset of RLT cuts, depending on signs of coefficients of monomial terms in the original constraints and the RLT constraints. Furthermore, the reduced RLT technique [12,13,14, 22] yields equivalent representations with fewer nonlinear terms for polynomial problems containing linear equality constraints.

We focus on RLT for bilinear products, which is of particular interest due to the numerous applications whose models involve nonconvex quadratic nonlinearities [3, 5, 7,8,9, 17]. Even in the bilinear case, large numbers of factors to be multiplied and of RLT cuts that are generated as a result remain an issue that can lead to considerable slowdowns, both due to the cost of cut separation and the large sizes of resulting LP relaxations.

The first contribution of this paper is a new approach to applying RLT to MILPs. Unlike the approaches that only introduce multilinear relations via multiplication [18, 19], this approach detects and enforces bilinear relations that are already implicitly present in the model. A bilinear product relation where one multiplier is a binary variable and the other multiplier is a variable with finite bounds can be equivalently written as two linear constraints. We identify such pairs of linear constraints that implicitly encode a bilinear product relation, then utilize this relation in the generation of RLT cuts.

The second contribution of this paper addresses the major bottleneck for applying RLT successfully in practice, which stems from prohibitive costs of separating RLT cuts, by proposing an efficient separation algorithm. This algorithm considers the signs of bilinear relation violations in a current LP relaxation solution and the signs of coefficients in linear constraints in order to ignore combinations of factors that will not produce a violated inequality. Furthermore, we propose a technique which projects the linear constraints onto a reduced space and constructs RLT cuts based on the resulting much smaller system.

The rest of the paper is organized as follows. In Sect. 2, RLT for bilinear products is explained. In Sect. 3, we describe the technique for deriving bilinear product relations from MILP constraints. Section 4 presents the new cut separation algorithm, and computational results are presented in Sect. 5.

2 RLT for Bilinear Products

We consider mixed-integer (nonlinear) programs (MI(N)LPs) of the extended form where auxiliary variables w are introduced for all bilinear products:

$$\begin{aligned} \min \;&\textbf{c}^{\text {T}}\textbf{x}\end{aligned}$$

(1a)

$$\begin{aligned} \text {s.t.}\;&A\textbf{x} \leqslant \textbf{b},\end{aligned}$$

(1b)

$$\begin{aligned}&g(\textbf{x},\textbf{w}) \leqslant 0,\end{aligned}$$

(1c)

$$\begin{aligned}&x_ix_j \lesseqgtr w_{ij} \text { for all } (i,j) \in \mathcal {I}^w, \end{aligned}$$

(1d)

$$\begin{aligned}&\mathbf {\underline{x}} \leqslant \textbf{x} \leqslant \mathbf {\overline{x}}, ~\mathbf {\underline{w}} \leqslant \textbf{w} \leqslant \mathbf {\overline{w}},\end{aligned}$$

(1e)

$$\begin{aligned}&x_j \in \mathbb {R} \text { for all } j \in \mathcal {I}^c, ~x_j \in \{0,1\} \text { for all } j \in \mathcal {I}^b, \end{aligned}$$

(1f)

with $\mathcal {I} = \mathcal {I}^c \cup \mathcal {I}^b$ being a disjoint partition of variables $\textbf{x}$ and $\textbf{x}$ having dimension $|\mathcal {I}| = n$. In the above formulation, $\mathbf {\underline{x}}$, $\mathbf {\overline{x}} \in \overline{\mathbb {R}}^n$, $\mathbf {\underline{w}}, \mathbf {\overline{w}} \in \overline{\mathbb {R}}^{|\mathcal {I}^w|}$ ($\overline{\mathbb {R}} = \mathbb {R} \cup \{-\infty ,+\infty \}$), $\textbf{c} \in \mathbb {R}^n$ and $\textbf{b} \in \mathbb {R}^{m^{(l)}}$ are constant vectors and $A \in \mathbb {R}^{m^{(l)} \times n}$ is a coefficient matrix, and the function g defines the nonlinear constraints. Constraint (1d) defines the bilinear product relations in the problem and allows for inequalities and equations. Let $\mathcal {I}^p$ denote the set of indices of all variables that participate in bilinear product relations (1d).

Solvers typically employ McCormick inequalities [16] to construct an LP relaxation of constraints (1d). These inequalities describe the convex hull of the set given by the relation $x_ix_j \lesseqgtr w_{ij}$:

$$\begin{aligned}&\underline{x}_ix_j + x_i\underline{x}_j - \underline{x}_i\underline{x}_j \leqslant w_{ij}, ~~~\overline{x}_ix_j + x_i\overline{x}_j - \overline{x}_i\overline{x}_j \leqslant w_{ij}, \end{aligned}$$

(2a)

$$\begin{aligned}&\underline{x}_ix_j + x_i\overline{x}_j - \underline{x}_i\overline{x}_j \geqslant w_{ij}, ~~~\overline{x}_ix_j + x_i\underline{x}_j - \overline{x}_i\underline{x}_j \geqslant w_{ij} , \end{aligned}$$

(2b)

where (2a) is a relaxation of $x_ix_j \leqslant w_{ij}$ and (2b) is a relaxation of $x_ix_j \geqslant w_{ij}$.

In the presence of linear constraints (1b), this relaxation can be strengthened by adding RLT cuts. Consider a linear constraint: $\sum _{k=1}^n a_{1k}x_k \leqslant b_1.$ Multiplying this constraint by nonnegative bound factors $(x_j-\underline{x}_j)$ and $(\overline{x}_j-x_j)$, where $\underline{x}_j$ and $\overline{x}_j$ are finite, yields valid nonlinear inequalities. We will derive the RLT cut using the lower bound factor. The derivation is analogous for the upper bound factor. The multiplication, referred to as the reformulation step, yields:

$$\sum _{k=1}^n a_{1k}x_k(x_j-\underline{x}_j) \leqslant b_1(x_j-\underline{x}_j).$$

This nonlinear inequality is then linearized in order to obtain a valid linear inequality. The following linearizations are applied to each nonlinear term $x_kx_j$:

• $x_kx_j$ is replaced by $w_{kj}$ if the relation $x_kx_j \leqslant w_{kj}$ exists in the problem and $a_{1k} \leqslant 0$, or if the relation $x_kx_j \geqslant w_{kj}$ exists and $a_{1k} \geqslant 0$, or if the relation $x_kx_j = w_{kj}$ exists in the problem,

• if $k=j \in \mathcal {I}^{b}$, then $x_kx_j = x_j^2 = x_j$,

• if $k=j \notin \mathcal {I}^b$, then $x_kx_j = x_j^2$ is outer approximated by a secant from above or by a tangent from below, depending on the sign of the coefficient,

• if $k \ne j$, $k,j \in \mathcal {I}^{b}$ and one of the four clique constraints is implied by the linear constraints (1b), then: $x_k + x_j \leqslant 1 \Rightarrow x_kx_j = 0$; $x_k - x_j \leqslant 0 \Rightarrow x_kx_j = x_k$; $-x_k + x_j \leqslant 0 \Rightarrow x_kx_j = x_j$; $-x_k - x_j \leqslant -1 \Rightarrow x_kx_j = x_j + x_j - 1$,

• otherwise, $x_kx_j$ is replaced by its McCormick relaxation.

The key step is the replacing of products $x_kx_j$ with the variables $w_{kj}$. When a bilinear product relation $x_kx_j \lesseqgtr w_{kj}$ does not hold for the current relaxation solution, this substitution may lead to an increase in the violation of the inequality, thus possibly producing a cut that is violated by the relaxation solution.

In the case that we have a linear equation constraint $\sum _{k=1}^n a_{1k}x_k = b_1$ and all nonlinear terms can be replaced using equality relations, then RLT produces an equation cut. Otherwise, the equation constraint is treated as two inequalities $\sum _{k=1}^n a_{1k}x_k \leqslant b_1$ and $\sum _{k=1}^n a_{1k}x_k \geqslant b_1$ to produce inequality cuts.

3 Detection of Implicit Products

Consider a product relation $w_{ij} = x_ix_j$, where $x_i$ is binary. It can be equivalently rewritten as two implications: $x_i = 0 \Rightarrow w_{ij} = 0$ and $x_i = 1 \Rightarrow w_{ij} = x_j$. With the use of the big-M technique, these implications can be represented as linear constraints, provided that the bounds of $x_j$ are finite:

$$\begin{aligned} w_{ij} - \overline{x}_jx_i \leqslant 0, ~w_{ij} - x_j - \underline{x}_jx_i \leqslant -\underline{x}_j \end{aligned}$$

(3a)

$$\begin{aligned} -w_{ij} + \underline{x}_jx_i \leqslant 0, ~-w_{ij} + x_j + \overline{x}_jx_i \leqslant \overline{x}_j. \end{aligned}$$

(3b)

Linear constraints with binary variables can be analyzed in order to detect constraint pairs of the forms (3). The method can be generalized to allow for bilinear relations of the following form, with $A,B,C,D \in \mathbb {R}$:

$$\begin{aligned} Ax_i + Bw_{ij} + Cx_j + D \lesseqgtr x_ix_j\end{aligned}$$

(4)

Theorem 1

Consider two linear constraints depending on the same three variables $x_i$, $x_j$ and $w_{ij}$, where $x_i$ is binary:

$$\begin{aligned} a_1x_i + b_1w_{ij} + c_1x_j \leqslant d_1,\end{aligned}$$

(5a)

$$\begin{aligned} a_2x_i + b_2w_{ij} + c_2x_j \leqslant d_2. \end{aligned}$$

(5b)

If $b_1b_2 > 0$ and $\gamma = c_2b_1 - b_2c_1 \ne 0$, then these constraints imply the following product relation:

$$(1/\gamma )((b_2(a_1 - d_1) + b_1d_2)x_i + b_1b_2w_{ij} + b_1c_2x_j - b_1d_2) \leqslant x_ix_j ~\text { if } b_1/\gamma \geqslant 0,$$

$$(1/\gamma )((b_2(a_1 - d_1) + b_1d_2)x_i + b_2b_2w_{ij} + b_1c_2x_j - b_1d_2) \geqslant x_ix_j ~\text { if } b_1/\gamma \leqslant 0.$$

Proof

We begin by writing the bilinear relation (4), treating its coefficients and inequality sign as unknown, and reformulating it as two implications:

$$\begin{aligned}&x_i = 1&~\Rightarrow ~&Bw_{ij} + (C-1)x_j \lesseqgtr -D - A,\end{aligned}$$

(6a)

$$\begin{aligned}&x_i = 0&~\Rightarrow ~&Bw_{ij} + Cx_j \lesseqgtr -D, \end{aligned}$$

(6b)

where the inequality sign must be identical in both implied inequalities. Similarly, we rewrite constraints (5) with scaling parameters $\alpha$ and $\beta$:

$$\begin{aligned}&x_i = 1&~\Rightarrow ~&\alpha b_1w_{ij} + \alpha c_1x_j \lesseqgtr \alpha (d_1 - a_1),\end{aligned}$$

(7a)

$$\begin{aligned}&x_i = 0&~\Rightarrow ~&\beta b_2w_{ij} + \beta c_2x_j \lesseqgtr \beta d_2, \end{aligned}$$

(7b)

where the inequality signs depend on the signs of $\alpha$ and $\beta$.

The goal is to find the coefficients A, B, C and D and the inequality sign. We require that coefficients and inequality signs in implications (6) and (7) match. Solving the resulting system yields:

$$\begin{aligned}\begin{gathered} b_1b_2 > 0, ~A = (1/\gamma )(b_2(a_1 - d_1) + b_1d_2)\\ B = b_1b_2/\gamma , ~C = b_1c_2/\gamma , ~D = -b_1d_2/\gamma , ~\gamma \ne 0, \end{gathered}\end{aligned}$$

where $\gamma = c_2b_1 - b_2c_1$ and the inequality sign is ‘$\leqslant$‘ if $b1/\gamma \geqslant 0$, and ‘$\geqslant$‘ if $b1/\gamma \leqslant 0$. Thus, the bilinear relation stated in this theorem is obtained.    $\square$

Although the conditions of the theorem are sufficient for the bilinear product relation to be implied by the linear constraints, in practice more conditions are checked before deriving such a relation. In particular:

• At least one of the coefficients $a_1$ and $a_2$ must be nonzero. Otherwise, the product relation is always implied by the linear constraints, including when $0< x_i < 1$.

• The signs of the coefficients of the binary variable $x_i$ must be different, that is, one linear relation is more restrictive when $x_i = 1$ and the other when $x_i = 0$. While this is not necessary for the non-redundancy of the derived product relation, by requiring this we focus on stronger implications (for instance, for a linear relation $a_1x_i + b_1w_{ij} + c_1x_j \leqslant d_1$ with $a_1 > 0$, we use the more restrictive implication $x_i = 1 ~\Rightarrow b_1w_{ij} + c_1x_j \leqslant d_1 - a_1$ rather than the less restrictive implication $x_i = 0 ~\Rightarrow b_1w_{ij} + c_1x_j \leqslant d_1$).

In separation, the product relation (4) is treated similarly to product relations $w_{ij} \lesseqgtr x_ix_j$, with the linear left-hand side $Ax_i + Bw_{ij} + Cx_j + D$ being used instead of the individual auxiliary variable $w_{ij}$.

The detection algorithm searches for suitable pairs of linear relations and derives product relations from them. Let $x_i$, as before, be a binary variable. The following relation types are considered as candidates for the first relation in such a pair: implied relations of the form $x_i = \xi ~\Rightarrow ~ \tilde{b}_1w_{ij} + \tilde{c}_1x_j \leqslant \tilde{d}_1$, where $\xi = 0$ or $\xi = 1$; and implied bounds of the form $x_i = \xi ~\Rightarrow ~ w_{ij} \leqslant \tilde{d}_1$.

The second relation in a pair can be: an implied relation of the form $x_i = \overline{\xi } ~\Rightarrow ~ \tilde{b}_2w_{ij} + \tilde{c}_2x_j \leqslant \tilde{d}_2$, where $\overline{\xi }$ is the complement of $\xi$; if $w_{ij}$ is non-binary, an implied bound of the form $x_i = \overline{\xi } ~\Rightarrow ~ w_{ij} \leqslant \tilde{d}_2$; if $w_{ij}$ is binary, a clique containing the complement of $x_i$ if $\xi = 1$ or $x_i$ if $\xi = 0$, and $w_{ij}$ or its complement; a constraint on $x_j$ and $w_{ij}$; or a global bound on $w_{ij}$. Cliques are constraints of the form: $\sum _{k \in \mathcal {J}}x_k + \sum _{k \in \overline{\mathcal {J}}}(1-x_k) \leqslant 1$, where $\mathcal {J} \subseteq \mathcal {I}^b$, $\overline{\mathcal {J}} \subseteq \mathcal {I}^b$ and $\mathcal {J} \cap \overline{\mathcal {J}} = \emptyset$.

4 Separation Algorithm

We present a new algorithm for separating RLT cuts within an LP-based branch-and-bound solver. The branch-and-bound algorithm builds LP relaxations of problem (1) by constructing linear underestimators of functions g in the constraint $g(\textbf{x},\textbf{w}) \leqslant 0$ and McCormick inequalities for constraints (1d).

Let $(\textbf{x}^*,\textbf{w}^*)$ be the solution of an LP relaxation at a node of the branch-and-bound tree, and suppose that $(\textbf{x}^*,\textbf{w}^*)$ violates the relation $x_ix_j \lesseqgtr w_{ij}$ for some $i,j \in \mathcal {I}^w$. Separation algorithms generate cuts that separate $(\textbf{x}^*,\textbf{w}^*)$ from the feasible region, and add those cuts to the solver’s cut storage.

The standard separation algorithm, which will serve as a baseline for comparisons, iterates over all linear constraints. For each constraint, it iterates over all variables $x_j$ that participate in bilinear relations and generates RLT cuts using bound factors of $x_j$. Violated cuts are added to the MINLP solver’s cut storage.

4.1 Row Marking

Let the bound factors be denoted as $f_j^{(\ell )}(\textbf{x}) = x_j-\underline{x}_j$ and $f_j^{(u)}(\textbf{x}) = \overline{x}_j - x_j$. Consider a linear constraint multiplied by a bound factor:

$$\begin{aligned} f_j^{(.)}(\textbf{x})\textbf{a}_r\textbf{x} \leqslant f_j^{(.)}(\textbf{x})b_r. \end{aligned}$$

(8)

The ith nonlinear term is $a'_{ri}x_ix_j$, where $a'_{ri} = a_{ri}$ when multiplying by $(x_j - \underline{x}_j)$ and $a'_{ri} = -a_{ri}$ when multiplying by $(\overline{x}_j - x_j)$. Following the procedure described in Sect. 2, RLT may replace the product $x_ix_j$ with $w_{ij}$. The product can also be replaced with a linear expression, but this does not change the reasoning, and we will only use $w_{ij}$ in this section.

If $w^*_{ij} \ne x^*_ix^*_j$, then such a replacement will change the violation of (8). The terms whose replacement will increase the violation are of interest, that is, the terms where:

$$a'_{ri}x^*_ix^*_j \leqslant a'_{ri}w^*_{ij}.$$

This determines the choice of bound factors to multiply with:

$$x^*_ix^*_j< w^*_{ij} ~\Rightarrow ~ \begin{array}{c}\text {multiply by }(x_j - \underline{x}_j) \text { if }a_{ri} > 0,\\ \text {multiply by }(\overline{x}_j - x_j) \text { if }a_{ri} < 0,\end{array}$$

$$x^*_ix^*_j> w^*_{ij} ~\Rightarrow ~ \begin{array}{c}\text {multiply by }(\overline{x}_j - x_j) \text { if }a_{ri} > 0,\\ \text {multiply by }(x_j - \underline{x}_j) \text { if }a_{ri} < 0.\end{array}$$

The separation algorithm is initialized by creating data structures to enable efficient access to 1) all variables appearing in bilinear products together with a given variable and 2) the bilinear product relation involving two given variables.

For each variable $x_i$, linear rows are marked in order to inform the separation algorithms which bound factors of $x_i$ they should be multiplied with, if any. The algorithm can work with inequality rows in both ‘$\leqslant$’ and ‘$\geqslant$’ forms as well as equation rows. For each bilinear product $x_ix_j$, the row marking algorithm iterates over all linear rows that contain $x_j$ with a nonzero coefficient. These rows are stored in a sparse array and have one of the following marks:

• MARK_LT: the row contains a term $a_{rj}x_j$ such that $a_{rj}x^*_ix^*_j < a_{rj}w^*_{ij}$;

• MARK_GT: the row contains a term $a_{rj}x_j$ such that $a_{rj}x^*_ix^*_j > a_{rj}w^*_{ij}$;

• MARK_BOTH: the row contains terms fitting both cases above.

Row marks are represented by integer values 1, 2 and 3, respectively, and are stored in two sparse arrays, row_idcs and row_marks, the first storing sorted row indices and the second storing the corresponding marks. In the algorithm below, we use the notation mark(r) to denote accessing the mark of row r by performing a search in row_idcs and retrieving the corresponding entry in row_marks. We also define a sparse matrix W with entries $w_{ij}$.

The algorithm iterates over the sparse array of marked rows and generates RLT cuts for the following combinations of linear rows and bound factors:

• If $mark =$ MARK_LT, then “$\leqslant$” constraints are multiplied with the lower bound factor and “$\geqslant$” constraints are multiplied with the upper bound factor;

• If $mark =$ MARK_GT, then “$\leqslant$” constraints are multiplied with the upper bound factor and “$\geqslant$” constraints are multiplied with the lower bound factor;

• If $mark =$ MARK_BOTH, then both “$\leqslant$” and “$\geqslant$” constraints are multiplied with both the lower and the upper bound factors;

• Marked equality constraints are always multiplied with $x_i$ itself.

4.2 Projection Filtering

If at least one of the variables $x_i$ and $x_j$ has a value equal to one of its bounds, then the McCormick relaxation (2) is tight for the relation $w_{ij} = x_ix_j$. Therefore, if $x_i$ or $x_j$ is at a bound and the McCormick inequalities are satisfied, then the product relation is also satisfied. We describe the equality case here, and the reasoning is analogous for the inequality case of $x_ix_j \lesseqgtr w_{ij}$.

Consider the linear system $A\textbf{x}\leqslant \textbf{b}$ projected onto the set of variables whose values are not equal to either of their bounds.

$$\sum _{k \in \mathcal {J}^1} a_{rk}x_k \leqslant b_r - \sum _{k \in \mathcal {J}^2} a_{rk}x^*_k, ~\forall r \in 1,\dots ,m^{(l)},$$

where $\mathcal {J}^1 \subseteq \mathcal {I}$ is the set of all problem variables whose values in the solution $\textbf{x}^*$ of the current LP relaxation are not equal to one of their bounds, and $\mathcal {J}^2 = \mathcal {I} \setminus \mathcal {J}^1$.

Violation is then first checked for RLT cuts generated based on the projected linear system. Only if such a cut, which we will refer to as a projected RLT cut, is violated, then the RLT cut for the same bound factor and the corresponding constraint in the original linear system will be constructed. Since $\textbf{x}^*$ is a basic LP solution, in practice either $x^*_k = \underline{x}_k$ or $x^*_k = \overline{x}_k$ holds for many of the variables, and the projected system often has a considerably smaller size than the original system.

In the projected system multiplied with a bound factor $f_j^{(.)}(\textbf{x})$:

$$f_j^{(.)}(\textbf{x})\cdot \sum _{k \in \mathcal {J}^1} a_{rk}x_k \leqslant f_j^{(.)}(\textbf{x})(b_r - \sum _{k \in \mathcal {J}^2} a_{rk}x^*_k), ~\forall r \in 1,\dots ,m^{(l)},$$

the only nonlinear terms are $x_jx_k$ with $k \in \mathcal {J}^1$, and therefore, no substitution $x_ix_k \rightarrow w_{ik}$ is performed for $k \in \mathcal {J}^2$. If the McCormick inequalities for $x_i$, $x_k$ and $w_{ik}$ hold, then $x^*_ix^*_k = w^*_{ik}$ for $k \in \mathcal {J}^2$, and checking the violation of a projected RLT cut is equivalent to checking the violation of a full RLT cut.

Depending on the solver, McCormick inequalities may not be satisfied at $(\textbf{x}^*,\textbf{w}^*)$. Thus, it is possible that $x^*_ix^*_k \ne w^*_{ik}$ for some $k \in \mathcal {J}^2$, but these violations will not contribute to the violation of the projected RLT cut. In this case, projection filtering has an additional effect: for violated bilinear products involving variables whose values in $\textbf{x}^*$ are at bound, the violation of the product will be disregarded when checking the violation of RLT cuts. Thus, adding McCormick cuts will be prioritized over adding RLT cuts.

5 Computational Results

5.1 Setup

We tested the proposed methods on the MINLPLib¹ [6] test set and a test set comprised of instances from MIPLIB3, MIPLIB 2003, 2010 and 2017 [10], and Cor@l [15]. These test sets consist of 1846 MINLP instances and 666 MILP instances, respectively. After structure detection experiments, only those instances were chosen for performance evaluations that either contain bilinear products in the problem formulation, or where our algorithm derived bilinear products. This resulted in test sets of 1357 MINLP instances and 195 MILP instances.

The algorithms were implemented in the MINLP solver SCIP [4]. We used a development branch of SCIP (githash dd6c54a9d7) compiled with SoPlex 5.0.2.4, CppAD 20180000.0, PaPILO 1.0.0.1, bliss 0.73p and Ipopt 3.12.11. The experiments were carried out on a cluster of Dell Poweredge M620 blades with 2.50GHz Intel Xeon CPU E5-2670 v2 CPUs, with 2 CPUs and 64GB memory per node. The time limit was set to one hour, the optimality gap tolerance to $10^{-4}$ for MINLP instances and to $10^{-6}$ for MILP instances, and the following settings were used for all runs, where applicable:

• The maximum number of unknown bilinear terms that a product of a row and a bound factor can have in order to be used was 20. Unknown bilinear terms are those terms $x_ix_j$ for which no $w_{ij}$ variable exists in the problem, or its extended formulation which SCIP constructs for the purposes of creating an LP relaxation of an MINLP.

• RLT cut separation was called every 10 nodes of the branch-and-bound tree.

• In every non-root node where separation was called, 1 round of separation was performed. In the root node, 10 separation rounds were performed.

• Unless specified otherwise, implicit product detection and projection filtering were enabled and the new separation algorithm was used.

5.2 Impact of RLT Cuts

In this subsection we evaluate the performance impact of RLT cuts. The following settings were used: Off - RLT cuts are disabled; ERLT - RLT cuts are added for products that exist explicitly in the problem; IERLT - RLT cuts are added for both implicit and explicit products. The setting ERLT was used for the MINLP test set only, since MILP instances contain no explicitly defined bilinear products.

We report overall numbers of instances, numbers of solved instances, shifted geometric means of the runtime (shift 1 s), and the number of nodes in the branch-and-bound tree (shift 100 nodes), and relative differences between settings. Additionally, we report results on subsets of instances. Affected instances are instances where a change of setting leads to a difference in the solving process, indicated by a difference in the number of LP iterations. [x,timelim] denotes the subset of instances which took the solver at least x seconds to solve with at least one setting, and were solved to optimality with at least one setting. All-optimal is the subset of instances which were solved to optimality with both settings.

Table 1. Impact of RLT cuts: MILP instances

Table 1 shows the impact of RLT cuts on MILP performance. We observe a slight increase in time when RLT cuts are enabled, and a slight decrease in number of nodes. The difference is more pronounced on ‘difficult’ instances: a $9\%$ decrease in number of nodes on subset [100,timelim] and $28\%$ on subset [1000,timelim], and a decrease of $21\%$ in the mean time on subset [1000,timelim].

Table 2 reports the impact of RLT cuts derived from explicitly defined bilinear products. A substantial decrease in running times and tree sizes is observed across all subsets, with a $15\%$ decrease in the mean time and a $19\%$ decrease in the number of nodes on all instances, and a $87\%$ decrease in the mean time and a $88\%$ decrease in the number of nodes on the subset [1000,timelim]. 223 more instances are solved with ERLT than with Off.

Table 3 evaluates the impact of RLT cuts derived from implicit bilinear products. Similarly to MILP instances, the mean time slightly increases and the mean number of nodes slightly decreases when additional RLT cuts are enabled, but on MINLP instances, the increase in the mean time persists across different instance subsets and is most pronounced ($9\%$) on the subset [100,timelim], and the number of nodes increases by $6-7\%$ on subsets [100,timelim] and [1000,timelim].

Table 2. Impact of RLT cuts derived from explicit products: MINLP instances

Table 3. Impact of RLT cuts derived from implicit products: MINLP instances

Table 4 reports numbers of instances for which a change in the root node dual bound was observed, where the relative difference is quantified as $\frac{\gamma _2-\gamma _1}{\gamma _1}$, where $\gamma _1$ and $\gamma _2$ are root node dual bounds obtained with the first and second settings, respectively. The range of the change is specified in the column ‘Difference’, and each column shows numbers of instances for which one or the other setting provided a better dual bound, within given range.

The results of comparisons Off/IERLT for MILP instances and Off/ERLT for MINLP instances are consistent with the effect of RLT cuts on performance observed in Tables 1 and 2. Interestingly, IERLT performs better than ERLT in terms of root node dual bound quality. Thus, RLT cuts derived from implicit products in MINLP instances tend to improve root node relaxations.

Table 4. Root node dual bound differences

5.3 Separation

In Table 5, the setting Marking-off employs the standard separation algorithm, and Marking-on enables the row marking and projection filtering algorithms described in Sect. 4. Row marking reduces the running time by 63% on MILP instances, by 70% on affected MILP instances, by 12% on MINLP instances and by 22% on affected MINLP instances. The number of nodes increases when row marking is enabled because, due to the decreased separation time, the solver can explore more nodes before reaching the time limit: this is confirmed by the fact that on the subset All-optimal, the number of nodes remains nearly unchanged.

Table 5. Separation algorithm comparison

Table 6 analyzes the percentage of time that RLT cut separation takes out of overall running time, showing the arithmetic mean and maximum over all instances, numbers of instances for which the percentage was within a given interval, and numbers of failures. The average percentage is reduced from $54.2\%$ to $2.8\%$ for MILP instances and from $15.1\%$ to $2.4\%$ for MINLP instances, and the maximum percentage is reduced from $99.6\%$ to $71.6\%$ for MILP instances, but remains at $100\%$ for MINLP instances. The numbers of failures are reduced with Marking-on, mainly due to avoiding failures that occur when the solver runs out of memory.

Table 6. Separation times

Projection filtering has a minor impact on performance. When comparing the runs where projection filtering is disabled and enabled, the relative difference in time and nodes does not exceed $1\%$ on both MILP and MINLP instances, except for affected MILP instances where projection filtering decreases the number of nodes by 4%. This is possibly occurring due to the effect of prioritizing McCormick inequalities to RLT cuts when enforcing derived product relations. The number of solved instances remains almost unchanged, with one less instance being solved on both MILP and MINLP test sets when projection filtering is enabled.

5.4 Experiments with Gurobi

In this subsection we present results obtained by running the mixed-integer quadratically-constrained programming solver Gurobi 10.0 beta [11]. The algorithms for implicit product detection and RLT cut separation are the same as in SCIP, although implementation details may differ between the solvers.

The internal Gurobi test set was used, comprised of models sent by Gurobi customers and models from public benchmarks, chosen in a way that avoids overrepresenting any particular problem class. Whenever RLT cuts were enabled, so was implicit product detection, row marking and projection filtering. The time limit was set to 10000 s.

Table 7 shows, for both MILP and MINLP test sets, the numbers of instances in the test sets and their subsets, and the ratios of shifted geometric means of running time and number of nodes of the runs with RLT cuts enabled, to the same means obtained with RLT cuts disabled. The last row shows the numbers of instances solved with one setting and unsolved with the other, that is, for example, “RLT off: +41” means that 41 instances were solved with the setting “off” that were not solved with the setting “on”.

While the results cannot be directly compared to those obtained with SCIP due to the differences in the experimental setup, we observe the same tendencies. In particular, RLT cuts yield small improvements on MILP instances which become more pronounced on subsets [100,timelim] and [1000,timelim], and larger improvements are observed on MINLP instances both in terms of geometric means and numbers of solved instances. Relative differences are comparable to those observed with SCIP, but the impact of RLT cuts is larger in Gurobi, and no slowdown is observed with Gurobi on any subset of MILP instances.

Table 7. Results obtained with Gurobi 10.0 beta

5.5 Summary

RLT cuts yield a considerable performance improvement for MINLP problems and a small performance improvement for MILP problems which becomes more pronounced for challenging instances. The new separation algorithm drastically reduces the computational burden of RLT cut separation and is essential to an efficient implementation of RLT cuts, enabling the speedups we observed when activating RLT.