# An Algorithm for Two-Stage Stochastic Quadratic Problems

Eugenio Mijangos

► To cite this version:

Eugenio Mijangos. An Algorithm for Two-Stage Stochastic Quadratic Problems. 25th System Mod-
eling and Optimization (CSMO), Sep 2011, Berlin, Germany. pp.177-187, 10.1007/978-3-642-36062-
6_18 . hal-01347535

HAL Id: hal-01347535

https://inria.hal.science/hal-01347535

Submitted on 21 Jul 2016

**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 Attribution 4.0 International License
# An Algorithm for Two-Stage Stochastic
Quadratic Problems

Eugenio Mijangos*

Department of Applied Mathematics
and Statistics and Operations Research
University of the Basque Country UPV/EHU, Spain
eugenio.mijangos@ehu.es

**Abstract.** An algorithm for solving quadratic, two-stage stochastic problems is developed. The algorithm is based on the framework of the Branch and Fix Coordination (BFC) method. These problems have continuous and binary variables in the first stage and only continuous variables in the second one. The objective function is quadratic and the constraints are linear. The nonanticipativity constraints are fulfilled by means of the twin node family strategy. On the basis of the BFC method for two-stage stochastic linear problems with binary variables in the first stage, an algorithm to solve these stochastic quadratic problems is designed. In order to gain computational efficiency, we use scenario clusters and propose to use either outer linear approximations or (if possible) perspective cuts. This algorithm is implemented in C++ with the help of the Cplex library to solve the quadratic subproblems. Numerical results are reported.

**Keywords:** Stochastic Programming, Mixed-Integer Quadratic Problems, Branch-and-Fix Coordination, Perspective Cuts

## 1 Introduction

Two-stage stochastic mixed integer programs are among the most interesting problems since the complexity generated by the integrality of variables and the high dimensionality. Stochastic parameters can exist anywhere in the problem. In order to model the uncertainty a finite set of scenarios, $\Omega$, is used, where each $\omega \in \Omega$ has an associated probability of occurrence $p^\omega$. In a two-stage program decisions on the first and second stage variables must be taken. First-stage variables are chosen before knowing the realization of the uncertain parameters. After having decided on first stage and having known each realization of the uncertain parameters, the second stage decision must be taken. The first-stage variables take the same value in each scenario, which yields *nonanticipativity constraints*. If we consider a finite number of scenarios, a general two-stage program can be expressed regarding the first-stage variables being equivalent to a

<footnote>* This work was partially supported by the Ministry of Science and Technology of Spain through MICINN Project DPI2008-02153.</footnote>
large programming problem suggested in citeWets66 and known as deterministic equivalent model (DEM). A general two-stage problem can include binary first-stage variables. The simplest form of two-stage stochastic integer problems have first-stage binary and second-stage continuous variables. In [7] a branch-and-cut method is used for those problems, which is based on the Benders decomposition method. An efficient branch-and-fix coordination (BFC) method for solving two-stage programs is provided in [1], where the first-stage has only binary variables, and where the uncertainty only appears in the coefficients of the objective function and in the right-hand-side of the constraints. If the first stage involves pure binary variables, finite termination is justified by using branching over the 0-1 first-stage variables, see among others [8] and [9]. Escudero et al. [3] study general two-stage stochastic mixed 0-1 problems, where the first stage only involves binary variables and continuous variables and the second stage continuous variables. They use a specialization of the BFC scheme and the twin-node-family (TNF) concept, which was introduced in [1]. Their scheme is specifically designed for coordinating the node branching selection and pruning and the 0-1 variable branching selection and fixing at each branch-and-fix (BF) tree. Also, they suggest to decompose the set of scenarios in clusters.

On the other hand, real problems with this structure exist and have a high dimensionality. They often need to be solved and it is important to find the procedure that will solve them with the highest efficiency. An example of this type is the Iberian Electricity Market (MIBEL), which comprises Spanish and Portuguese electricity systems, see [6].

In this paper we consider the two-stage mixed 0-1 quadratic problem

$$ 
\begin{array}{ll}
\text{minimize} & c^t \delta + q(x, y) \\
\text{subject to:} & l_a \le A \begin{bmatrix} \delta \\ x \end{bmatrix} \le u_a, \\
& l_t \le T \begin{bmatrix} \delta \\ x \\ y \end{bmatrix} \le u_t, \\
& x \ge 0, \quad y \le u \le \bar{y}, \quad \delta \in \{0, 1\}^{n_\delta},
\end{array}
$$

where $\delta$ are first-stage-binary variables, $x \in \mathbf{R}^{n_x}$ are first-stage continuous variables, $y \in \mathbf{R}^{n_y}$ are second-stage continuous variables, $c$ is the coefficient vector for $\delta$, and $q$ is the quadratic function defined as follows

$$ q(x, y) = b^t \begin{bmatrix} x \\ y \end{bmatrix} + [x^t \quad y^t]^T Q \begin{bmatrix} x \\ y \end{bmatrix}, $$

where $Q$ is a positive-definite matrix and $b$ and $Q$ are partitioned as $\begin{bmatrix} x \\ y \end{bmatrix}$; i.e.,

$$ b = \begin{bmatrix} b_x \\ b_y \end{bmatrix} \quad \text{and} \quad Q = \begin{bmatrix} Q_{xx} & Q_{xy} \\ Q_{yx} & Q_{yy} \end{bmatrix}. $$

In addition, $l_a$ and $u_a$ are the bounds for the first-stage constraints and $l_t$ and $u_t$ are the bounds for the second-stage constraints.
Let us suppose that some of the coefficient in $b_y$, $Q_{xy}$, $Q_{yx}$, $Q_{yy}$, $l_t$, $u_t$ and $T$ are uncertain. The uncertainty is given by the scenarios $\omega$ in the finite set $\Omega$ and $p^\omega$ is the probability of that occurs $\omega \in \Omega$. Therefore, the initial problem given in a stochastic way can be written as the so-called Deterministic Equivalent Model (DEM)

$$ \text{minimize} \quad c^t \delta + \sum_{\omega \in \Omega} p^\omega q^\omega(x, y^\omega) \qquad (1) $$

$$ \text{subject to:} \quad l_a \le A \begin{bmatrix} \delta \\ x \end{bmatrix} \le u_a, \qquad (2) $$

$$ l_t^\omega \le T^\omega \begin{bmatrix} \delta \\ x \\ y^\omega \end{bmatrix} \le u_t^\omega, \quad \omega \in \Omega, \qquad (3) $$

$$ x \ge 0, \quad y \le y^\omega \le \bar{y}, \quad \omega \in \Omega, \qquad (4) $$

$$ \delta \in \{0, 1\}^{n_\delta}, \qquad (5) $$

As is shown by [3] the compact representation DEM can be written as a splitting variable representation; i.e., $\delta$ and $x$ are respectively replaced by $\delta^\omega$ and $x^\omega$, for $\omega \in \Omega$. So, we have

$$ \begin{array}{ll} \textbf{(MIQP)} \quad & \displaystyle \text{minimize} \quad \sum_{\omega \in \Omega} p^\omega (c^t \delta^\omega + q^\omega(x^\omega, y^\omega)) \\[1.5em] & \text{subject to:} \quad l_a \le A \begin{bmatrix} \delta^\omega \\ x^\omega \end{bmatrix} \le u_a, \quad \omega \in \Omega, \\[1em] & \qquad l_t^\omega \le T^\omega \begin{bmatrix} \delta^\omega \\ x^\omega \\ y^\omega \end{bmatrix} \le u_t^\omega, \quad \omega \in \Omega, \\[1em] & \qquad x^\omega \ge 0, \quad y \le y^\omega \le \bar{y}, \quad \delta^\omega \in \{0, 1\}^{n_\delta}, \quad \omega \in \Omega, \\[1.5em] & \text{(NAC}_\delta) \quad \delta^\omega - \delta^{\omega'} = 0, \quad \forall \omega, \omega' \in \Omega : \omega \ne \omega', \\[1em] & \text{(NAC}_x) \quad x^\omega - x^{\omega'} = 0, \quad \forall \omega, \omega' \in \Omega : \omega \ne \omega', \end{array} $$

where NAC$_\delta$ and NAC$_x$ are the nonanticipativity constraints.

Note that the relaxation of the NACs in the model **MIQP** gives rise to $|\Omega|$ independent **MIQP**$^\omega$ submodels

$$ \text{minimize} \quad p^\omega (c^t \delta^\omega + q^\omega(x^\omega, y^\omega)), \qquad (6) $$

$$ \text{subject to:} \quad l_a \le A \begin{bmatrix} \delta^\omega \\ x^\omega \end{bmatrix} \le u_a, \qquad (7) $$

$$ l_t^\omega \le T^\omega \begin{bmatrix} \delta^\omega \\ x^\omega \\ y^\omega \end{bmatrix} \le u_t^\omega, \qquad (8) $$

$$ x^\omega \ge 0, \quad y \le y^\omega \le \bar{y}, \qquad (9) $$

$$ \delta^\omega \in \{0, 1\}^{n_\delta}, \qquad (10) $$
and these models are linked by the NACs, which force the equality of the first-stage variables.

In this work to solve the original quadratic problem **DEM** a Branch-and-Fix-Coordination scheme (BFC) is used for each scenario $\omega \in \Omega$ to fulfill the integrality condition (IC) given by (10), so that the NAC$_\delta$ are also satisfied when selecting branching nodes and branching variables by the Twin-Node-Families concept (TNF), which was introduced by [1]. A similar approach to that suggested in [3] is used in this work to coordinate the selection of the branching node and branching variable for each scenario-related BF tree, such that the NAC$_\delta$ are satisfied when fixing $\delta^\omega$, $\forall \omega \in \Omega$, either to 1 or to 0. A TNF integer set is a set of integer BF nodes (i.e. they verify IC), one per BF tree, in which the NAC$_\delta$ are verified.

For each TNF integer set we use two quadratic submodels. The quadratic model $QP^{TNF}$ obtained after fixing in **DEM** $\delta = \bar{\delta} \in \{0,1\}^{n_\delta}$ for a TNF integer set

$$ (QP^{TNF}) \quad Z^{TNF} = c^t \bar{\delta} + \min \sum_{\omega \in \Omega} p^\omega q^\omega(x, y^\omega) $$

$$ \text{subject to : } l_a \le A \begin{bmatrix} \bar{\delta} \\ x \end{bmatrix} \le u_a, $$

$$ l_t^\omega \le T^\omega \begin{bmatrix} \bar{\delta} \\ x \\ y^\omega \end{bmatrix} \le u_t^\omega, \omega \in \Omega, $$

$$ x \ge 0, \quad y \le y^\omega \le \bar{y}, \omega \in \Omega, $$

It gives a feasible solution and a possible incumbent solution.

The second quadratic submodel to solve at a TNF integer set corresponds to the case where not all the $\delta$ variables have been branched on in the current TNF, but all of them hold the integrality condition. Then, the other quadratic submodel ($QP^f$) is obtained from problem **DEM** with $\delta = \begin{pmatrix} \bar{\delta} \\ \delta^f \end{pmatrix}$, where $\bar{\delta}_j$, for $j \in \{1, \dots, k\}$, are fixed to 0-1 values and the componentes of $\delta_j^f$ are in the interval $[0, 1]$.

$$ (QP^f) \quad Z^f = \min c^t \delta + \sum_{\omega \in \Omega} p^\omega q^\omega(x, y^\omega) $$

$$ \text{subject to : } l_a \le A \begin{bmatrix} \delta \\ x \end{bmatrix} \le u_a, $$

$$ l_t^\omega \le T^\omega \begin{bmatrix} \delta \\ x \\ y^\omega \end{bmatrix} \le u_t^\omega, \omega \in \Omega, $$

$$ x \ge 0, \quad y \le y^\omega \le \bar{y}, \omega \in \Omega, $$

$$ \delta_j = \bar{\delta}_j \text{ fixed to } 0-1, \text{ for } j \in \{1, \dots, k\} $$

$$ \delta_j = \delta_j^f \in [0, 1], \text{ for } j \in \{k+1, \dots, n^\delta\} $$
This model contributes strong lower bounds of the solution value of the descen-
dent nodes from a given node, by satisfying the NAC<sub>x</sub>.

1.1 Outline of BFC

This method branches on the δ-variables, obtaining the solution of the quadratic submodels **MIQP**<sup>ω</sup> and coordinating the selection of the branching node and branching variable for the BF trees, such that the NAC<sub>δ</sub> constraints are fulfilled once fixed the suitable variables δ to 1 or to 0. .

A sequence of lower bounds $\underline{Z}_i$ is computed, where $\underline{Z}_i = \sum_{\omega \in \Omega} z_i^\omega$ and $z_i^\omega$ is the solution to the quadratic relaxation ($\mathbf{QP}^\omega$) of $\mathbf{MIQP}^\omega$ once the previous variables $\delta$ have been fixed to 0 or to 1.

If the optimal solution obtained in each node of the TNF satisfies the IC (integrality constraints) and the NAC<sub>δ</sub>, two cases can happen with respect to the NAC<sub>x</sub>. If NAC<sub>x</sub> are satisfied, the incumbent solution is updated and the TNF's branch is pruned; if the set of active nodes is empty, that solution is the optimum. Otherwise, to satisfy NAC<sub>x</sub> we solve the TNF quadratic problem obtained by fixing the δ-variables that verified IC and NAC<sub>δ</sub>; if this problem is feasible, the incumbent solution is updated, and if the TNF cannot be pruned, we continue with the tree examination. For more details about the BFC method for two-stage stochastic problems see [3].

1.2 Scenario clusters

When the number of scenarios is very large, in order to gain computational
efficiency we can take scenario clusters; see in [4] an information structuring for
scenario cluster partitioning of nonsymmetric scenario trees.

Let $\hat{p}$ be the number of clusters and $\Omega^1, \dots, \Omega^{\hat{p}}$, where $\Omega^p \cap \Omega^{p'} = \emptyset$ for $p, p' = 1, \dots, \hat{p}$, such that $p \neq p'$, and $\cup_{p=1}^{\hat{p}} \Omega^p = \Omega$. So, instead of the submodel $\mathbf{MIQP}^\omega$ for $\omega \in \Omega$ we can consider the following submodel for the scenario cluster $p = 1, \dots, \hat{p}$

$$
\begin{array}{ll}
(\mathbf{MIQP}^p) & \text{minimize} \quad \sum_{\omega \in \Omega^p} p^\omega (c^t \delta^p + q^\omega (x^p, y^\omega)) \\
\text{subject to :} & l_a \le A \begin{bmatrix} \delta^p \\ x^p \end{bmatrix} \le u_a, \\
& l_t^\omega \le T^\omega \begin{bmatrix} \delta^p \\ x^p \\ y^\omega \end{bmatrix} \le u_t^\omega, \omega \in \Omega^p \\
& x^p \ge 0, \quad \bar{y} \le y^\omega \le \bar{y}, \omega \in \Omega^p, \quad \delta^p \in \{0,1\}^{n_\delta}
\end{array}
$$

These models are linked by the NACs $\delta^p - \delta^{p'} = 0$ and $x^p - x^{p'} = 0$, for all $p, p' \in \{1, \dots, \hat{p}\}$ such that $p \neq p'$.
However, since the number of branches to test can be huge, the BFC method has some troubles: the number of feasible solutions can be too high, a high number of quadratic problems $QP^p$, $QP^{TNF}$, and $QP^f$ can exist to solve, and $QP^{TNF}$ and $QP^f$ can have very high dimensions. Hence, in order to gain computational efficiency, we propose to use either outer linear approximations or (if possible) perspective cuts to solve $QP^p$ in each TNF (i.e., $\mathbf{MIQP}^p$ where the previous branching variables have been fixed and the rest is relaxed in $[0, 1])$

## 2 Outer linear approximations (OLA)

Let the problem $\min_{y \in Y} g(y)$, where $g$ is convex and $Y$ is a polyhedral set. The optimal value of that problem is not smaller than that of

$$ \begin{array}{ll} \text{minimize} & \eta \\ \text{subject to:} & \eta \ge g(y_i) + \nabla g(y_i)^t (y - y_i), \\ & y \in Y. \end{array} $$

Therefore, the value of $\eta^*$ gives us an underestimate of $g(y^*)$ and, so, we can use it instead of $g(y^*)$ in the comparison with the current upper bound, in order to prune (or not) the current branch.

In our problem, we use as $y_i$ the solution in the previous node.

## 3 Perspective cuts

When $Q_{xy}$ and $Q_{yx}$ are zero matrices, the quadratic function $q$ is defined as follows

$$ q(x, y) = b_x^t x + b_y^t y + x^t Q_{xx} x + y^t Q_{yy} y. $$

This kind of model can be found in liberalized electricity markets [6] and [2].

For each scenario $\omega \in \Omega$ we can write the objective function of the submodel $\mathbf{MIQP}^\omega$ as follows

$$ \begin{aligned} p^\omega(c^t \delta^\omega + b_x^t x + (b_y^t)^t y^\omega + x^t Q_{xx} x + (y^\omega)^t Q_{yy} y^\omega) = \\ p^\omega \left\{ \left( b_x^t x + x^t Q_{xx} x \right) + \left( (y^\omega)^t Q_{yy} y^\omega + (b_y^t)^t y^\omega + c^t \delta^\omega \right) \right\} \end{aligned} $$

and, if $n := n^\delta = n^y$ and $Q_{yy}$ is diagonal (as in [6]), we can write the last bracket as $\sum_{i=1}^n q_{ii}^\omega (y_i^\omega)^2 + b_i^\omega y_i^\omega + c_i \delta_i^\omega$.

For notational simplicity in this paragraph we drop the indices. The issue is then how to best represent the quadratic function $f(y, \delta) = qy^2 + by + c\delta$ by means of a piecewise-linear one. There is an effective way based on ideas developed by Frangioni and Gentile [5]. The function $f(y, \delta)$ is only relevant at points $(y, \delta)$ of its (disconnected) domain $\mathcal{D} = [0, 0] \cup [\bar{y}, \bar{y}] \times \{1\}$. Standard branch-and-cut approaches typically solve the continuous relaxation of the mixed problem, where $\delta \in [0, 1]$ instead of $\{0, 1\}$, in order to obtain lower bounds on
the optimal value. This makes sense to use the convex envelope of $f(y, \delta)$ over $\mathcal{D}$, that is, the convex function with the smallest (in set-inclusion sense) epigraph containing that of $f(y, \delta)$. As is showed in [5] the convex envelope is

$$h(y, \delta) = \begin{cases} 0, & \text{if } (y, \delta) = (0, 0) \\ \frac{qy^2}{\delta} + by + c\delta, & \begin{cases} \text{if } \delta\underline{y} \le y \le \delta\bar{y}, \\ \text{for } \delta \in (0, 1] \end{cases} \\ +\infty, & \text{otherwise.} \end{cases}$$

This function is strongly related with the perspective-function $\check{f}(y, \delta) = \delta f(y/\delta)$ of $f(y) = qy^2 + by + c$, which is convex if $f(y)$ is convex.

$h(y, \delta) \ge f(y, \delta)$ for $0 < \delta \le 1$, i.e. $h$ is a tighter objective function than $f$ for the continuous relaxation. As is well-known, every convex function is the point-wise supremum of affine functions. In fact, the epigraph of $h$ is composed of all and only triples $(v, y, \delta)$ satisfying $\delta\underline{y} \le y \le \delta\bar{y}$, $0 \le \delta \le 1$ and the infinite system of linear inequalities

$$v \ge (2q\hat{y} + b)y + (c - q\hat{y}^2)\delta$$

taking $\hat{y} \in [y, \bar{y}]$. For each $\hat{y}$ we have an inequality so-called a perspective cut (PC), which is the unique supporting hyperplane to the function passing by $(0, 0)$ and $(\hat{y}, 1)$.

## 3.1 PC formulation (PCF)

PC formulation (PCF) lies in choosing these supporting hyperplanes and using as an objective function the polyhedral function that is the point-wise maximum of the corresponding linear functions. A small set of initial PCs is chosen to solve the problem with the continuous relaxation. When $\delta^* > 0$, check whether the solution $(v^*, y^*, \delta^*)$ satisfies the PC for $\hat{y} = y^*/\delta^*$; if not, the obtained cut can be added to PCF.

PCF starts with only two pieces, the ones corresponding with $\underline{y}$ and $\bar{y}$; additional cuts are then dynamically generated when needed as described in the previous paragraph.

Therefore, the objective function of $\mathbf{MIQP}^\omega$ for PCF becomes

$$p^\omega \left\{ \left( b_x^t x + x^t Q_{xx} x \right) + \left( \sum_{i=1}^n v_i^\omega \right) \right\},$$

and the initial PCs added to the constraints of $\mathbf{MIQP}^\omega$ for each $i \in \{1, \dots, n\}$

$$v_i^\omega \ge (2q_{ii}^\omega \underline{y}_i + b_i^\omega) y_i^\omega + (c_i - q_{ii}^\omega \bar{y}_i^2) \delta_i^\omega$$

$$v_i^\omega \ge (2q_{ii}^\omega \bar{y}_i + b_i^\omega) y_i^\omega + (c_i - q_{ii}^\omega \underline{y}_i^2) \delta_i^\omega$$
We can extend this formulation to scenario clusters obtaining the $MIQP^p$ submodels for $p = 1, \dots, \hat{p}$ in this way

$$ \min \sum_{\omega \in \Omega^p} p^{\omega} \left\{ \left(b_x^t x + x^t Q_{xx} x\right) + \left(\sum_{i=1}^n v_i^{\omega}\right) \right\} $$

$$ \text{s.t.:} \quad v_i^{\omega} \ge (2q_{ii}^{\omega}y_i + b_i^{\omega})y_i^{\omega} + (c_i - q_{ii}^{\omega}y_i^2)\delta_i^{\omega}, \quad i \in \{1, \dots, n\}, \omega \in \Omega^p $$

$$ v_i^{\omega} \ge (2q_{ii}^{\omega}\bar{y}_i + b_i^{\omega})y_i^{\omega} + (c_i - q_{ii}^{\omega}\bar{y}_i^2)\delta_i^{\omega}, \quad i \in \{1, \dots, n\}, \omega \in \Omega^p $$

$$ l_a \le A \left[ \frac{\delta^p}{x^p} \right] \le u_a, $$

$$ l_t^{\omega} \le T^{\omega} \begin{bmatrix} \delta^p \\ x^p \\ y^{\omega} \end{bmatrix} \le u_t^{\omega}, \quad \omega \in \Omega^p $$

$$ x^p \ge 0, \quad y^p \in [y, \bar{y}], \quad \omega \in \Omega^p, \text{ and } \delta^p \in \{0, 1\}^{n_\delta} $$

# 4 Implementation

These methods have been implemented in C++ with the help of Cplex 12.1 to solve only the quadratic subproblems $QP^p$ in each node of the BF tree, for each $p \in \{1, \dots, \hat{p}\}$, and the $QP^{TNF}$ and $QP^f$ subproblems. These algorithmic alternatives have been considered:

* QBFC: coordination of $\delta$ in the TNF of the BF trees for clusters $p \in \{1, \dots, \hat{p}\}$ without using neither OLAs nor PCs, i.e. solving the quadratic subproblems $QP^p$.

* QBFC-PC: coordination of $\delta$ in the TNF of the BF trees for clusters $p \in \{1, \dots, \hat{p}\}$ using PCs.

* QBFC-OLA: coordination of $\delta$ in the TNF of the BF trees for clusters $p \in \{1, \dots, \hat{p}\}$ using OLAs.

For our instances the number of scenarios in each cluster is the same, $|\Omega^p| = |\Omega|/\hat{p}$. Each cluster contains $|\Omega^p|$ consecutive scenarios, starting from the first one and following in natural order.

# 5 Numerical tests

In order to obtain a computational comparison of the performance of the algorithmic alternatives QBFC, QBFC-PC, and QBFC-OLA some computational tests are carried out, which consist in solving two-stage stochastic problems, where the objective function is convex quadratic with linear constraints using QBFC code with those algorithmic choices. Therefore, these problems have a unique primal solution and the duality gap is zero. The tests have been performed on HP Compact with Intel Core 2 Quad Q9550 2.83GHz 4 CPU under Linux 2.6.38-8-generic-pae (x86_64).
The test problems have been randomly generated by using a C++ code developed by this author. This generator provides the scenarios set together with the associated probability of occurrence for two-stage stochastic mixed quadratic problems where $Q_{xy} = 1$, $Q_{xy} = 0$, and $Q_{yx} = 0$. Moreover, as can be seen in Table 1, in some problems $Q_{xx} = 0$ and in the rest of problems $Q_{xx} = 1$. Also, “# var” means the number of continuous variables, “# bin” the number of binary variables, “# constr” the number of constraints for DEM, see (1)-(5), and “dens” constraint matrix density %.

<table><caption>**Table 1.** Test problems</caption><thead><tr><th>Prob.</th><th>Ω</th><th># var</th><th># bin</th><th># constr</th><th>Q<sub>xx</sub></th><th>dens.</th></tr></thead><tbody><tr><td>P1</td><td>20</td><td>420</td><td>20</td><td>840</td><td>0</td><td>38</td></tr><tr><td>P2</td><td>30</td><td>620</td><td>20</td><td>1240</td><td>0</td><td>37</td></tr><tr><td>P3</td><td>40</td><td>820</td><td>20</td><td>1640</td><td>0</td><td>42</td></tr><tr><td>P4</td><td>50</td><td>1020</td><td>20</td><td>2040</td><td>0</td><td>43</td></tr><tr><td>P5</td><td>60</td><td>1220</td><td>20</td><td>2440</td><td>0</td><td>39</td></tr><tr><td>P6</td><td>70</td><td>1420</td><td>20</td><td>2840</td><td>0</td><td>37</td></tr><tr><td>P7</td><td>30</td><td>930</td><td>30</td><td>1860</td><td>0</td><td>2</td></tr><tr><td>P8</td><td>40</td><td>1230</td><td>30</td><td>2460</td><td>0</td><td>2</td></tr><tr><td>P9</td><td>50</td><td>1530</td><td>30</td><td>3060</td><td>0</td><td>1</td></tr><tr><td>P10</td><td>60</td><td>1830</td><td>30</td><td>3660</td><td>0</td><td>1</td></tr><tr><td>P11</td><td>70</td><td>2130</td><td>30</td><td>4260</td><td>0</td><td>1</td></tr><tr><td>P12</td><td>100</td><td>3030</td><td>30</td><td>6060</td><td>0</td><td>1</td></tr><tr><td>P13</td><td>30</td><td>930</td><td>30</td><td>1550</td><td>1</td><td>13</td></tr><tr><td>P14</td><td>40</td><td>1230</td><td>30</td><td>2050</td><td>1</td><td>10</td></tr><tr><td>P15</td><td>50</td><td>1530</td><td>30</td><td>2550</td><td>1</td><td>10</td></tr><tr><td>P16</td><td>60</td><td>1830</td><td>30</td><td>3050</td><td>1</td><td>9</td></tr><tr><td>P17</td><td>70</td><td>2130</td><td>30</td><td>3550</td><td>1</td><td>9</td></tr></tbody></table>

Table 2 presents the main results of the computational experimentation for given values of the number of scenario clusters. Below the heading QBFC-1 are the times in CPU-seconds used for solving problems with 1 only scenario cluster (i.e. $\hat{p} = 1$) and by solving the quadratic subproblem $QP^p$ for each node using Cplex; the heading QBFC-5OLA indicates the CPU-times for 5 scenario cluster (i.e. $\hat{p} = 5$) and by solving the quadratic subproblem $QP^p$ for each node using outer linear approximations (OLA). Finally, PC means perspective cuts are used.

As can be observed in Table 2, the best efficiency is mainly obtained when the problems are solved with 5 clusters, except in the case of QBFC-5 because of the computational cost of solving a quadratic problem in each node of the BF tree for the different clusters. In addition, the outer linear approximations give us a higher efficiency than the perspective cuts.
<table><caption>**Table 2.** Computational results: CPU-times</caption><thead><tr><th>Prob.</th><th>QBFC-1</th><th>QBFC-1PC</th><th>QBFC-1OLA</th><th>QBFC-5</th><th>QBFC-5PC</th><th>QBFC-5OLA</th></tr></thead><tbody><tr><td>P1</td><td>4.4</td><td>11.8</td><td>4.9</td><td>17.8</td><td>3.8</td><td>2.0</td></tr><tr><td>P2</td><td>9.7</td><td>14.2</td><td>6.7</td><td>6.6</td><td>8.0</td><td>3.0</td></tr><tr><td>P3</td><td>17.0</td><td>26.3</td><td>7.8</td><td>24.5</td><td>22.8</td><td>4.4</td></tr><tr><td>P4</td><td>21.4</td><td>43.3</td><td>16.3</td><td>14.5</td><td>18.6</td><td>6.3</td></tr><tr><td>P5</td><td>56.4</td><td>22.3</td><td>18.8</td><td>28.9</td><td>45.0</td><td>19.6</td></tr><tr><td>P6</td><td>33.9</td><td>96.0</td><td>28.7</td><td>10.6</td><td>20.0</td><td>9.7</td></tr><tr><td>P7</td><td>51.1</td><td>10.6</td><td>5.1</td><td>-</td><td>5.2</td><td>3.8</td></tr><tr><td>P8</td><td>5.2</td><td>9.3</td><td>3.9</td><td>-</td><td>5.0</td><td>2.3</td></tr><tr><td>P9</td><td>-</td><td>2.18</td><td>10.2</td><td>-</td><td>5.2</td><td>3.3</td></tr><tr><td>P10</td><td>135.4</td><td>28.5</td><td>14.2</td><td>-</td><td>18.8</td><td>10.5</td></tr><tr><td>P11</td><td>1052.7</td><td>39.1</td><td>14.5</td><td>-</td><td>17.2</td><td>3.7</td></tr><tr><td>P12</td><td>915.1</td><td>30.2</td><td>11.0</td><td>-</td><td>16.3</td><td>20.1</td></tr><tr><td>P13</td><td>10.5</td><td>7.1</td><td>7.8</td><td>-</td><td>5.3</td><td>6.8</td></tr><tr><td>P14</td><td>5.8</td><td>149.1</td><td>37.5</td><td>-</td><td>15.2</td><td>20.4</td></tr><tr><td>P15</td><td>94.4</td><td>69.5</td><td>58.4</td><td>-</td><td>33.2</td><td>16.1</td></tr><tr><td>P16</td><td>46.3</td><td>143.5</td><td>109.1</td><td>-</td><td>16.7</td><td>44.6</td></tr><tr><td>P17</td><td>1260.4</td><td>250.8</td><td>87.3</td><td>-</td><td>13.3</td><td>7.6</td></tr></tbody></table>

# 6 Conclusions

An algorithm to solve two-stage stochastic quadratic problems based on the Twin Node Family concept involved in the Branch-and-Fix Coordination has been implemented in C++ with the help of Cplex library to solve only the quadratic subproblems. When the problem's structure makes it possible, the algorithm uses perspective cuts or OLA to linearize the MIQ subproblems in each BF tree. The preliminary numerical results show a bit better efficiency with OLA than with PCF.

The path started from this work has the aim of solving nonlinear (non-quadratic) stochastic problems with nonlinear constraints and for two stage or more.

# References

1. Alonso-Ayuso A., Escudero L.F., Ortuño M.T. (2003). BFC, a branch-and-fix coordination algorithm framework for solving some types of stochastic pure and mixed 0-1 programs. European Journal of Operational Research 2003;151:503-519.

2. Corchero C., Mijangos E., Heredia F.J. (2012). A new optimal electricity market bid model solved through perspective cuts. Top, published online 2011, DOI 10.1007/s11750-011-0240-6.

3. Escudero L.F., Garín M., Merino M., Pérez G. (2009). A general algorithm for solving two-stage stochastic mixed 0-1 first-stage problems. Computers & Operations Research 36:2590-2600.

4. Escudero L.F., Garín M., Merino M., Pérez G. (2012). An algorithmic framework for solving large-scale multistage stochastic mixed 0-1 problems with nonsymmetric scenario trees. Computers & Operations Research 39(5):1133-1144.
5. Frangioni A., Gentile C. (2006) Perspective cuts for a class of convex 0-1 mixed integer programs. Mathematical Programming 106:225-236

6. Heredia F.J., Corchero C., Mijangos E. (2011). Solving electricity market quadratic problems by Branch and Fix Coordination methods. 25th IFIP TC7 Conference, Berlin.

7. Laporte G., Louveaux F. (2002). An integer L-shaped algorithm for the capacited vehicle routing problem with stochastic demands. Operations Research 50:415-423.

8. Sen S., Sherali H. (2006). Decomposition with branch-and-cut approaches for two-stage stochastic mixed-integer programming. Mathematical Programming Series A 105:203-223.

9. Sherali H.D., Fraticelli B.M.P. (2002). A modification of Bender's decomposition algorithm for discrete subproblems: an approach for stochastic programs with integer recourse. Journal of Global Optimization 22:319-342.

10. Wets R.J.-B. (1966). Programming under uncertainty: the equivalent convex program. SIAM Journal on Applied Mathematics 14:89-105.