Chance constrained 0–1 quadratic programs using copulas

Abstract

In this paper, we study 0–1 quadratic programs with joint probabilistic constraints. The row vectors of the constraint matrix are assumed to be normally distributed but are not supposed to be independent. We propose a mixed integer linear reformulation and provide an efficient semidefinite relaxation of the original problem. The dependence of the random vectors is handled by the means of copulas. Finally, numerical experiments are conducted to show the strength of our approach.

1 Introduction

In this paper, we study the following 0–1 quadratic program with joint probabilistic (or chance) constraints, called (QCC) hereafter:

$$\begin{aligned} \min x{}^TQx+c{}^Tx \ \mathrm{subject \ to }\quad \Pr \{ Tx \le d \}\ge p,\quad Ax = b,\ x\in \{ 0,1 \}^n\quad \end{aligned}$$

(1)

where $c\in \mathbb R^n$, $d \in \mathbb R^K$, and $b \in \mathbb R^m$ are deterministic vectors, $Q\in \mathbb R^{n\times n}$ and $A\in \mathbb R^{m\times n}$ are deterministic matrices, $T\in \mathbb R^{K\times n}$ is a random matrix with rows $T{}^T_k,\ k=1,\ldots ,K$, and $p\in (0;1)$ is a prescribed probability level. Chance-constrained problems of such form have been extensively studied in the literature starting with [5]. Excellent surveys on the theory, algorithms and bibliography of probabilistic programming are given by [9, 17, 18].

In this paper, we consider the nonconvex (QCC) with normally distributed dependent rows. This is an extension of previous results where the row independence was assumed [6–8]. Cheng et al. [8] reformulate a linear program with joint chance constraints as a convex completely positive problem, and solve its semidefinite relaxation. A conic approximation is performed using the formulations proposed in [7]. Furthermore, our current approach makes use of copula theory, i.e., we explore some favorable properties of Gumbel-Hougaard copula to describe the dependence between rows of the matrix $T$.

The rest of this paper is organized as follows. In Sect. 2, we present an SOCP and MILP formulations, together with introducing copula theory describing the row dependence. In Sect. 3, we present our semidefinite relaxation. In Sect. 4, we give our computational experiments to illustrate the strength of our SDP relaxation. To simplify the notation, we use indices $k=1,\ldots ,K$, $i,j=1,\ldots ,n$, and $l=1,\ldots , N$ with these ranges throughout the paper without mentioning it explicitly.

2 SOCP and LP formulations

We start our investigation with an equivalent description of (QCC) and its relaxed and restriction (or conservative) approximations by linearizing second order cone programming (SOCP) constraints. For the sequel we assume that $T{}^T_k$ are multivariate normally distributed vectors with known mean vectors $\mu _k$, and covariance matrices $\Sigma _k$ which are assumed to be positive definite. We do not assume independence of the rows; instead, we use the theory of copulas to represent inter-row dependence.

2.1 Row dependence

Copula theory was developed in the fields of probability theory and mathematical statistics to represent general dependence between random variables. To the best of our knowledge, copulas are not commonly used in stochastic optimization. Recently, Henrion et al. [12] used copulas to come up with convexity results for chance constrained problems with dependent random right hand side.

The following notions were taken from the book [15].

Definition 1

A copula is the distribution function $C: [0;1]^K \rightarrow [0;1]$ of some $K$-dimensional random vector whose marginals are uniformly distributed on [0; 1].

The joint distribution function of a random vector and the dependence of its marginals are closely related by Sklar’s Theorem.

Proposition 1

(Sklar’s Theorem) For any $K$-dimensional distribution function $F: \mathbb R^K \rightarrow [0; 1]$ with marginals $F_1, \ldots , F_K$, there exists a copula $C$ such that

$$\begin{aligned} \forall z\in \mathbb R^K \quad F(z) = C(F_1(z_1), \ldots , F_K(z_K)). \end{aligned}$$

(2)

If, moreover, $F_k$ are continuous, then $C$ is uniquely given by

$$\begin{aligned} C(u) = F(F_1^{-1}(u_1), \ldots , F_K^{-1}(u_K)). \end{aligned}$$

(3)

Otherwise, $C$ is uniquely determined on ${{\mathrm{range}}}F_1 \times \cdots \times {{\mathrm{range}}}F_K$.

Sklar’s theorem ensures the existence and uniqueness of a copula for any distribution function and all its marginals. In our paper, we restrict the consideration to the following two classes of copulas:

• 1. independent (product) copula, defined by

  $$\begin{aligned} C_\Pi (u) = \prod _{k=1}^K u_k. \end{aligned}$$

  Indeed, the independent copula represents the joint distribution of independent random variables.

• 2. Gumbel-Hougaard family of copulas, given for a $\theta \ge 1$ by

  $$\begin{aligned} C_\theta (u) = \exp \left\{ -\left[ \sum _{k=1}^K (-\ln u_k)^\theta \right] ^{1/\theta }\right\} \end{aligned}$$

  It is easy to see that the independent copula is a special case of the Gumbel-Hougaard copula with $\theta =1$. The Gumbel-Hougaard copula is a member of strict Archimedean copulas and shares of course the general properties of this class of copulas. Nelsen [15] showed that Gumbel-Hougaard copula can be considered as the representation of the bivariate extreme value distribution. This copula was used for several applications amongst all multivariate hydrologic frequency analysis for extreme hydrological events [19]. It was also used for trivariate rainfall frequency analysis in the subhumid climate of Southern Louisiana [22].

For $x\ne 0$ and for each $k$ we introduce the transformation

$$\begin{aligned} \xi _k (x) := \frac{T{}^T_k x - \mu {}^T_k x}{\Vert \Sigma _k^{1/2} x \Vert }, \quad&g_k (x) := \frac{d_k - \mu {}^T_k x}{\Vert \Sigma _k^{1/2} x \Vert }. \end{aligned}$$

The random variable $\xi _k(x)$ has one-dimensional standard normal distribution which is independent of $x$. Therefore, the probabilistic constraint $\Pr \{ Tx\le d \} \ge p$ can be equivalently rewritten as

$$\begin{aligned} \Pr \bigl \{ \xi _k(x) \le g_k(x)\ \forall k \bigr \} \ge p. \end{aligned}$$

(4)

Lemma 1

If the random vector $(\xi _1(x), \ldots , \xi _K(x)){}^T$, where $\xi _k(x)$ has one-dimensional standard normal distribution, has a joint distribution driven by the Gumbel-Hougaard copula $C_\theta$ with some $\theta \ge 1$ then the constraint $\Pr \{ Tx\le d \} \ge p$ is equivalent to the set of constraints

$$\begin{aligned} \mu {}^T_k x&+ \Phi ^{-1}\left( p^{z_k^{1/\theta }}\right) \left\| \Sigma _k^{1/2} x \right\| \le d_k \quad \forall k, \nonumber \\&\sum \nolimits _k z_k = 1,\ z_k \ge 0 \quad \forall k \end{aligned}$$

(5)

where $\Phi (\cdot )$ is the inverse of the standard normal cumulative distribution function.

Proof

Assume that there exists $z_k$ such that (5) holds and $x\ne 0$. Then, the inequality of (5) is equivalent to

$$\begin{aligned} \Phi ^{-1}\left( p^{z_k^{1/\theta }}\right) \le \frac{d_k - \mu {}^T_k x}{\Vert \Sigma _k^{1/2} x \Vert }, \quad \text { i.e., }\quad \Phi (g_k(x)) \ge p^{z_k^{1/\theta }}. \end{aligned}$$

Let us first show that a vector $x$ feasible in (5) satisfies (4). Indeed, from the definition of the Gumbel-Hougaard copula and Sklar’s theorem,

$$\begin{aligned} \Pr \bigl \{ \xi _k(x)&\le g_k(x)\ \forall k \bigr \} = C_\theta (\Phi (g_1(x)),\ldots ,\Phi (g_K(x))) \\&\ge C_\theta \left( p^{z_1^{1/\theta }},\ldots ,p^{z_K^{1/\theta }}\right) = \exp \left\{ -\left[ \sum _k \left( - \ln p^{z_k^{1/\theta }}\right) ^\theta \right] ^{1/\theta }\right\} \\&= \exp \left\{ -\left[ \sum _k \left( - z_k^{1/\theta } \ln p\right) ^\theta \right] ^{1/\theta }\right\} = \exp \left\{ \ln p \left[ \sum _k z_k \right] ^{1/\theta } \right\} = p. \end{aligned}$$

For the opposite direction, we have to prove the existence of such $z_k$. Let $x$ be a feasible solution for  (4). Hence, assume $p<1$ and define

$$\begin{aligned} \tilde{z}_k&:= \left( \frac{\ln \Phi (g_k(x))}{\ln p}\right) ^\theta \quad {\text { for }}\; k=1,\ldots ,K,&z_k&:= \frac{\tilde{z}_k}{\sum _{k=1}^{K} \tilde{z}_k}\quad {\text { for }}\; k=1,\ldots ,K.\end{aligned}$$

It is easy to verify that such definition of $z_k$ satisfies $\sum _{k=1}^{K} z_k = 1,\ z_k \ge 0$. Since $\tilde{z}_k = \left( \frac{\ln \Phi (g_k(x))}{\ln p}\right) ^\theta$, then we have $\mu {}^T_k x + \Phi ^{-1}\left( p^{\tilde{z}_k^{1/\theta }}\right) \left\| \Sigma _k^{1/2} x \right\| = d_k \ \forall k$. Moreover, as

$$\begin{aligned} p&\le \Pr \bigl \{ \xi _k(x) \le g_k(x)\ \forall k \bigr \} = C_\theta (\Phi (g_1(x)),\ldots ,\Phi (g_K(x))) \\&= C_\theta \left( p^{\tilde{z}_1^{1/\theta }},\ldots ,p^{\tilde{z}_K^{1/\theta }}\right) = \exp \left\{ -\biggl [\sum _k \left( - \ln p^{\tilde{z}_k^{1/\theta }}\right) ^\theta \biggr ]^{1/\theta }\right\} = p^{\left[ \sum _{k=1}^{K} \tilde{z}_k\right] ^{1/\theta }} \end{aligned}$$

and $p<1$, one has $\left[ \sum _{k=1}^{K} \tilde{z}_k\right] ^{1/\theta } \le 1$ and further $\sum _{k=1}^{K} \tilde{z}_k \le 1$. Then we have $z_k\ge \tilde{z}_k \forall k$. Therefore, it is attained $\mu {}^T_k x + \Phi ^{-1}\left( p^{z_k^{1/\theta }}\right) \left\| \Sigma _k^{1/2} x \right\| \le d_k \ \forall k$, which means $z_k$ satisfies (5).

The remaining case, $x=0$, where (4) does not make sense but $\Pr \{Tx\le d \}\ge p$ is equivalent to the constraint $d\ge 0$.

Above all, the conclusion follows. $\square$

For the sequel, we will also need the following convexity lemma:

Lemma 2

If $p\ge \frac{1}{2}$ and $\theta \ge 1$ then $H(z) := \Phi ^{-1}\left( p^{z^{1/\theta }}\right)$ is convex on $[0;1]$.

Proof

$H$ is convex if $\Phi ^{-1}(\cdot )$ is convex, nondecreasing, and $z\mapsto p^{z^{1/\theta }}$ is convex. The first assertion is true if $p^{z^{1/\theta }} \ge \frac{1}{2}$, that is if

$$\begin{aligned} z \le \left( - \frac{\ln 2}{\ln p}\right) ^\theta \end{aligned}$$

(6)

(excluding the case $p=1$ which is trivial). If $p\ge \frac{1}{2}$ then $-\frac{\ln 2}{\ln p} \ge 1$ hence (6) is valid for $z\in [0;1]$. The function $z\mapsto p^{z^{1/\theta }}$ is convex if $z\mapsto z^{1/\theta } \ln p$ is convex, i. e., $z\mapsto z^{1/\theta }$ concave. But $\frac{1}{\theta } \in (0;1]$ hence the last assertion is true for all $z\in [0;1]$. $\square$

Lemma 2 provides a condition which is crucial for the deduction of our subsequent approximations. Hence, for the rest of the paper, we will assume that $1> p\ge \frac{1}{2}$.

2.2 Mixed integer formulation

According to our assumptions and Lemma 1, we can derive a deterministic reformulation of (QCC) as

$$\begin{aligned} \min x{}^TQx+c{}^Tx \quad \text {subject } \text { to}\quad&\mu {}^T_k x + \Phi ^{-1}\Bigl (p^{z_k^{1/\theta }}\Bigr ) \Vert \Sigma _k^{1/2}x \Vert \le d_k \ \forall k, \nonumber \\&\sum _{k=1}^K z_k = 1, \ z_k \ge 0 \ \forall k, \ Ax = b, \ x \in \{0, 1\}^n.\nonumber \\ \end{aligned}$$

(7)

The problem (7) is equivalent to

(8)

Using the Taylor approximation of $H(z)^2$ at $z_k$ and linearizing the quadratic terms, we provide its piecewise-tangent approximation, and obtain a mixed integer linear program

$$\begin{aligned}&\min \langle X, Q \rangle +c{}^Tx \end{aligned}$$

(9)

$$\begin{aligned}&\quad \text {subject } \text { to}\quad \langle \Sigma _k, Z^k \rangle \le d_k^2 - 2 d_k \mu {}^T_k x + \langle \mu _k \mu {}^T_k, X \rangle \quad \forall k \end{aligned}$$

(10)

$$\begin{aligned}&\mu {}^T_k x \le d_k \quad \forall k \end{aligned}$$

(11)

$$\begin{aligned}&\hat{F}^k - (1 - X_{ij}) U^+ \le Z^k_{ij} \le \hat{F}^k \quad \forall i,j,k \end{aligned}$$

(12)

$$\begin{aligned}&0 \le Z^k_{ij} \le X_{ij} U^+ \quad \forall i,j,k\end{aligned}$$

(13)

$$\begin{aligned}&a_l + b_l z_k \le \hat{F}^k \quad \forall k, l \end{aligned}$$

(14)

$$\begin{aligned}&x_i+x_j-1 \le X_{ij} \le \min \{x_i, x_j \} \quad \forall i,j, \end{aligned}$$

(15)

$$\begin{aligned}&X_{ii} = x_i \quad \forall i, \ X_{ij}\ge 0 \quad \forall i,j, \end{aligned}$$

(16)

$$\begin{aligned}&\sum _{k=1}^K z_k = 1, \ z_k \ge 0 \quad \forall k,\ Ax=b, \ x \in \{0, 1\}^n \end{aligned}$$

(17)

where $U^+$ is an upper bound of $\hat{F}_k := \max _l \{ a_l + b_l z_k \}$, $a_l$ and $b_l$ are coefficients of the piecewise-tangent approximation of $H(z_k)^2$ at $N$ selected tangent points $z_{(l)}$, $l=1,\ldots ,N$. Constraints (10) are obtained by replacing the function $H(z)^2xx^T$ by $Z^k$. Constraints (12) and (13) are linearization constraints for the quadratic terms $Z^k_{ij}=\hat{F}^kX_{ij}$ whilst constraints (15) are linearization constraints for the quadratic terms $X_{ij}=x_ix_j$ [10]. The model (9–17) is a relaxation of problem (7) as shown by the following lemma:

Lemma 3

The optimal value $\phi ^*_N$ of (9–17) is a lower bound of (7). Moreover if the trivial solution $x=0$ is not feasible to (7) and tangents points are uniformly selected on the interval $(0,1]$, then $\lim \limits _{N\rightarrow +\infty } \phi ^*_N = \phi ^*$ where $\phi ^*$ is the optimal value of (7).

Proof

According to Lemma 2, $H(z)$ is convex and so is $H(z)^2$ as the square function is non-decreasing and convex on the interval $[0, \infty )$. We approximate this function at tangent points $z_{(l)}$, $l=1,\ldots ,N$ by the first-order Taylor polynomial. We obtain $N$ lines $z_k \mapsto a_l + b_l z_k$. By applying the linearization technique and due to the convexity, we obtain an outer approximation of the feasible set of (8). Hence, the optimal value $\phi ^*_N$ is a lower bound of $\phi ^*$. Further, as $x=0$ is an infeasible solution, $x\in \{0,1\}^n$ and $\Sigma _k$ is positive definite, then ${x{}^T\Sigma _k x}$ is lower bounded by a constant $L> 0$. Thus, $\frac{\left( d_k-\mu {}^T_k x\right) ^2}{x{}^T\Sigma _k x}$ is bounded above by $\frac{d_k^2}{L}$ and further $H(z)^2$ is bounded above by $\frac{d_k^2}{L}$. Therefore, $z_k$ is bounded below by $\left( \frac{\ln \Phi (\frac{d_k^2}{L})}{\ln p}\right) ^\theta$, which implies that the derivative of $H(z)^2$ is bounded. Moreover the tangents points are uniformly selected on the interval $(0,1]$, the convergence can be proved directly by applying the results of [21]. $\square$

Note that if $x=0$ is a feasible solution to (7), we can add the constraint $\sum x_i\ge 1$ to the problem and solve it. We can then compare the optimal objective value of the new problem with $0$ to find the optimal solution of (7).

When we approximate $H(z)^2$ by using the piecewise-linear technique, then we have another mixed integer linear program which is a restriction of the problem (7) as shown by the following lemma:

Lemma 4

The optimal value $\phi ^*_N$ of the restriction problem is an upper bound of (7). Moreover if the trivial solution $x=0$ is not feasible to (7) and the interpolation points are uniformly selected on the interval $(0,1]$, then $\lim \limits _{N\rightarrow +\infty } \phi ^*_N = \phi ^*$ where $\phi ^*$ is the optimal value of (7).

Proof

Similar to the proof of Lemma 3.

3 SDP relaxation

Semidefinite programming is a subfield of convex optimization which provides strong modeling capabilities using polynomial solving methods. More precisely, a semidefinite program is a linear program over the cone of positive semidefinite matrices. We refer the reader to [2] for a various applications of semidefinite programming. Since the seminal works of Lovász [14] and Goemans and Williamson [11], several authors proposed approximation algorithms for NP-hard combinatorial problems based on the semidefinite relaxation. They show that SDP relaxation provides generally tightened bounds than LP relaxations. In this paper, we use the inner approximations proposed by [16], namely the first cone $(\mathbb {S}_+ \cap \mathbb N)$ where $\mathbb {S}_+$ is the cone of positive semidefinite matrices and $\mathbb {N}$ is the cone of nonnegative matrices. Here, we give a semidefinite programming approximation by using the piecewise tangent method [7] whose objective value is a lower bound of (QCC).

By using a piecewise tangent approximation of $H(z_k)$, we have an approximation of (7) as follows:

$$\begin{aligned}&\min x{}^TQ x + c{}^Tx \end{aligned}$$

(18)

$$\begin{aligned}&\quad \text {subject } \text { to}\quad \mu {}^T_k x + \Vert \Sigma _k^{1/2}\tilde{z}_k \Vert \le d_k \quad \forall k \end{aligned}$$

(19)

$$\begin{aligned}&\tilde{z}_{ki} \ge a_l x_i + b_l z_{ki} \quad \forall i, l \end{aligned}$$

(20)

$$\begin{aligned}&\sum _{k=1}^K z_{ki} = x_i, \ z_{ki}\ge 0 \quad \forall i, k \end{aligned}$$

(21)

$$\begin{aligned}&\tilde{F}_k - (1 - x_i) M^+ \le \tilde{z}_{ki} \le M^+ x_i \quad \forall i,k \end{aligned}$$

(22)

$$\begin{aligned}&0 \le \tilde{z}_{ki} \le \tilde{F}_k \quad \forall k\end{aligned}$$

(23)

$$\begin{aligned}&a_l + b_l z_k \le \tilde{F}_k \quad \forall k,l \end{aligned}$$

(24)

$$\begin{aligned}&\sum _{k=1}^K z_k = 1,\ z_k \ge 0 \quad \forall k,\ Ax=b, \ x \in \{0,1\}^n \end{aligned}$$

(25)

where $\tilde{z}_k = (\tilde{z}_{k1},\ldots ,\tilde{z}_{kn})$ and $M^+$ is an upper bound of $\tilde{F}_k=\max _l \{a_l + b_l z_k\}$, the piecewise tangent approximation of $H(z_k)$.

Constraints (19) are obtained by approximating the term $H(z_k)x_i$ by $\tilde{z}_{ki}=\tilde{F}_k x_i$. The variables $z_{ki}$ are defined by $z_{ki}=z_kx_i$. Constraints (22) and (23) are linearization constraints for the quadratic terms $\tilde{z}_{ki}=\tilde{F}_k x_i$. Constraints (20) and (21) strengthen our SDP relaxation though they are redundant when $x$ is a binary variable. These constraints are deduced from constraints (24) and (25). Further, as constraint $z_{ki}=z_kx_i$ are difficult to consider explicitly, they are not taken into account in our relaxed model.

Theorem 1

The optimal value of (18–25) is a lower bound of (QCC). Moreover, if the trivial solution $x = 0$ is not feasible to (7), and the interpolation points are uniformly selected on the interval $(0;1]$, then it converges to the optimal value of (QCC), as the number of segments N goes to infinity.

Proof

The proof is similar to Lemma $3$ proof. $\square$

A semidefinite relaxation of (18–25) can be written as

$$\begin{aligned} \min&\langle X, Q \rangle + c{}^Tx \end{aligned}$$

(26)

$$\begin{aligned} \quad \text {subject } \text { to}\quad&\begin{pmatrix} (d_k-\mu {}^T_k x)I &{}\quad \Sigma _k^{1/2}\tilde{z}_k\\ \tilde{z}_k{}^T(\Sigma _k^{1/2}){}^T&{}\quad d_k-\mu {}^T_k x \end{pmatrix} \succeq 0 \quad \forall k \end{aligned}$$

(27)

$$\begin{aligned}&\tilde{z}_{ki} \ge a_l x_i + b_l z_{ki} \quad \forall i, l \end{aligned}$$

(28)

$$\begin{aligned}&\sum _{k=1}^K z_{ki} = x_i, \ z_{ki}\ge 0 \quad \forall i, k \end{aligned}$$

(29)

$$\begin{aligned}&\tilde{F}_k - (1-x_i) M^+ \le \tilde{z}_{ki} \le M^+ x_i \quad \forall i,k \end{aligned}$$

(30)

$$\begin{aligned}&0 \le \tilde{z}_{ki} \le \tilde{F}_k \end{aligned}$$

(31)

$$\begin{aligned}&a_l + b_l z_k \le \tilde{F}_k \quad \forall l \end{aligned}$$

(32)

$$\begin{aligned}&A{}^T_t x = b_t, \ A{}^T_t X A_t = b_t^2, \quad \forall t=1,\ldots ,m \end{aligned}$$

(33)

$$\begin{aligned}&\sum _{k=1}^K z_k = 1, \ z_k \ge 0 \quad \forall k \end{aligned}$$

(34)

$$\begin{aligned}&\begin{pmatrix} 1 &{}\quad x{}^T\\ x &{}\quad X \end{pmatrix} \succeq 0, \ X \ge 0 \end{aligned}$$

(35)

where $I$ is the identity matrix of appropriate dimension. Linear matrix inequality Constraints (27) are derived from constraints (19) using Schur complement [3]. Constraints (33) are used to strength our SDP relaxation; they were used by [4] for copositive programs. Constraints (35) are a relaxation of constraints $X=x^Tx$ obtained using the Schur complement.

4 Computational study

We study two MILP approximations and one SDP relaxation on stochastic multidimensional quadratic knapsack problems (SMQKP for short) from the OR-library [1]. Three different instances are considered, their sizes are defined by $(n,m,K)={(14,5,5),(28,10,5),(50,5,10)}$ where $n$ is number of variables, $m$ number of deterministic constraints and $K$ denotes the number of rows of the joint chance constraints. The parameters of the instances are generated as follows: the elements of $Q$ are randomly generated on the interval $[10, 20]$, the means $\mu _k$ are drawn from the uniform distribution on the interval $[0, 5]$, the covariance matrices $\Sigma _k$ are generated by MATLAB function gallery(’randcorr’,n)*2 and the capacity $d$ is independently chosen from the interval $[10,20]$. The confidence parameter is set to $p=0.9$.

We solve and compare four approximations. The first one is SDP relaxation (26–35) whose solution objective value is designed hereafter by $V^{ SDP }$. The second and third ones solve (9–17) and the restriction problem abovementioned which are mixed integer linear problems designed by $V^{MILP}(R)$ and $V^{MILP}(C)$ respectively.

We also implement a continuous linear relaxation of (9–17) called hereafter $V^{ LP }$. For all the approximations, we choose $N=3$ tangent points $z_{(1)}=0.01$, $z_{(2)}=0.15$ and $z_{(3)}=0.45$ in Table 1, and vary the number of tangent points from $3$ up to $20$ in Table 2 . The dependence parameter $\theta$ is set to 1 (independence), 2 (moderate dependence), and 5 (high dependence), respectively. All the considered models are generated using MATLAB environment and solved either by IBM CPLEX $v12$ [13] on an Intel(R)D @ $2.00$ GHz with $4.0$ GB RAM, or by Sedumi [20] with default parameters. The BigM number $M^+$ used in the SDP relaxation is chosen as the maximum of the parameters $a_l, \forall l$.

Table 1 Computational results when $p=0.9$

Table 2 Computational results for $(28,10,5)$ with different $N$ and $p$

The numerical results for the three instances and for different values of $\theta$ are given by Table 1 where column one gives the name of the instance, columns two and three show the MILP optimal values and the corresponding CPU time respectively. Columns four, five and six give the relaxed MILP objective values. Columns seven, eight and nine show the LP relaxation objective value, the CPU time and the corresponding gap respectively. The last three columns present the SDP relaxation objective value, the CPU time and the corresponding gap respectively. The gap is defined by $Gap = \frac{ UB - Opt }{ Opt }\cdot$ 100 % where $UB$ is the upper bound and $Opt$ is the optimal solution of the restriction problem, i.e., $V^{MILP}(C)$, which provides a feasible solution.

We observe that for all instances, the SDP relaxation of our formulation outperforms the LP relaxation in terms of the quality of the solution. The SDP gaps range from 5 to 20 % while the LP gaps range from 27 to 40  %. The CPU time for our approach is within $100$ s. However, both MILP formulations, i.e., the relaxation and the restriction of the original problem (7), give better solutions than SDP but within a larger CPU time.

Table 2 gives the same results as Table 1 for one instance $(28,10,5)$ but for three different values of $p$, namely $p=0.85;0.9;0.95$, and for different number of tangent points, i.e., $N=3,10,20$. Table 2 shows the same performances as before for different values of $p$ and $N$. Our SDP approach outperforms LP approach for different values of $p$. Moreover, the gaps decrease when the number of tangent points increase. In addition, both tables show that our two MILP approximations provide good candidate solutions for small size instances for two reasons: first, their CPU time is within 320 s; and their solutions are optimal when $N=20$.