# A Review on the Performance of Linear and Mixed Integer Two-Stage Stochastic Programming Software
## 2 Problem Statement  
We consider a two-stage stochastic mixed-integer linear problem (\(P\)) in the following form:  
\[(P)\quad\min_{x,y}\quad TC=c^{T}x+\sum_{\omega\in\Omega}\tau_{\omega}d_{ \omega}^{T}y_{\omega} \tag{1a}\] \[\text{s.t.}\quad Ax\leq b\] (1b) \[x\in X,\quad X=\left\{x:x_{i}\in\left\{0,1\right\}\ \forall i\in I_{1},\ \ x_{i}\geq 0\ \ \forall i\in I \backslash I_{1}\right\}\] (1c) \[W_{\omega}y_{\omega}\leq h_{\omega}-T_{\omega}x\quad\forall \omega\in\Omega\] (1d) \[y_{\omega}\in Y\quad\forall\omega\in\Omega \tag{1e}\]  
where \(x\) denotes the 'here and now' decisions, taken at the beginning of the planning horizon before the uncertainties unfold, and \(\Omega\) is the set of scenarios. Vector \(y_{\omega}\) represents the recourse or corrective actions (wait and see), applied after the realization of the uncertainty. Matrix \(A\in\mathbb{R}^{m_{1}\times n_{1}}\) and vector \(b\in\mathbb{R}^{m_{1}}\) represent the first-stage constraints. Matrices \(T_{\omega}\) and \(W_{\omega}\), and vector \(h_{\omega}\in\mathbb{R}^{m_{2}}\) represent the second-stage problem. Matrices \(T_{\omega}\in\mathbb{R}^{m_{2}\times n_{1}}\) and \(W_{\omega}\in\mathbb{R}^{m_{2}\times n_{2}}\) are called technological and recourse matrices, respectively. Let \(I=\left\{1,2,\ldots,n_{1}\right\}\) be the index set of all first-stage variables. Set \(I_{1}\subseteq I\) as the subset of indices for binary first-stage variables. Let \(J=\left\{1,2,\ldots,n_{2}\right\}\) be the index set of all second-stage variables. If the second-stage variables are mixed integer, \(Y=\left\{y:y_{i}\in\left\{0,1\right\},\forall j\in I_{1},\ \ y_{j}\geq 0\ \ \forall j\in I \backslash I_{1}\right\}\), where set \(J_{1}\subseteq J\) is the subset of indices for binary second-stage variables. If all the second-stage variables are continuous, set \(J_{1}=\mathcal{O}\) and \(Y=\left\{y:y_{j}\geq 0\ \forall j\in I\right\}\). The objective function (\(TC\)) minimizes the total expected cost with the scenario probability \(\tau_{\omega}\), and the cost vectors \(c\) and \(d_{\omega}\). It should be noted that the approaches discussed in this paper can be applied to mixed-integer variables. Here, we restrict the variables to be mixed binary for simplicity. Equation (1) is often referred to as the deterministic equivalent, or extensive form of the SP. Formulation (\(P\)) can be rewritten in an equivalent form (\(PNAC\)) with nonanticipativity constraints (\(NACs\)), where the first-stage variables are no longer shared, and each scenario represents an instance of a deterministic problem with a specific realization outcome [16; 17]. \[(PNAC)\quad\min_{x_{\omega},y_{\omega}}\quad TC=\sum_{\omega\in\Omega}\tau_{ \omega}(c^{T}x_{\omega}+d_{\omega}^{T}y_{\omega}) \tag{2a}\]s.t. \[\sum_{\omega\in\Omega}H_{\omega}x_{\omega}=0\] (2b) \[(x_{\omega},y_{\omega})\in G_{\omega}\quad\forall\omega\in\Omega\] (2c)  
In Equation (2c), \(G_{\omega}\) represents the feasible region for scenario \(\omega\), which is defined by constraints (1b)-(1e). Nonanticipativity constraints (2b) are added to ensure that the first-stage decisions are the same across all scenarios. Nonanticipativity constraints are represented by a suitable sequence of matrices \(H_{\omega}\in\mathbb{R}^{n_{1}\cdot(|\Omega|-1)\times n_{1}}\). One example of such constraints is the following:  
\[x_{\omega}=x_{\omega-1}\quad\forall\omega=2,3,\ldots,|\Omega| \tag{3}\]  
Given the mathematical structure of the deterministic equivalent formulations (\(P\)) and (\(PNAC\)), (mixed-integer) linear stochastic problems can be solved using decomposition methods derived from duality theory [18]. Such methods split the deterministic equivalent into a master problem and a series of smaller subproblems to decentralize the overall computational burden.