# A Review on the Performance of Linear and Mixed Integer Two-Stage Stochastic Programming Software
## 6 Software Packages for Scenario Decomposition
### PySP: Pyomo Stochastic Programming
#### 6.1.1 Algorithmic Innovations in PySP  
The innovations in PySP for multi-stage mixed-integer stochastic programs were described by [PERSON] and [PERSON] [52]. Here, we briefly paraphrase those innovations. First, instead of keeping a fixed \(\rho\) value for all first-stage decisions in Algorithm 4, the authors proposed several variable-dependent \(\rho\) strategies. The cost-proportional (CP) strategy sets \(\rho(i)\) to be proportional to the cost parameter \(c(i)\), i.e., \(\rho(i)=\alpha c(i)\), where \(\alpha\) is a constant multiplier for all first-stage variables \(i\). The other variable-dependent \(\rho\) strategy was denoted by SEP in [52], where the \(\rho(i)\) for integer variables is calculated by  
\[\rho(i):=\frac{c(i)}{(x^{\max}-x^{\min}+1)}\]  
After PH iteration 0, for each variable \(x\), \(x^{\max}=\max_{\omega\in\Omega}x_{\omega}^{0}\) and \(x^{\min}=\min_{\omega\in\Omega}x_{\omega}^{0}\). For continuous variables, the \(\rho(i)\) is calculated with  
\[\rho(i):=\frac{c(i)}{\max\left(\left(\sum_{\omega\in\Omega}\tau_{\omega}|x_{ \omega}^{0}-\bar{x}^{0}|\right),1\right)}\]  
where \(\bar{x}^{0}\) is the weighted average of \(x_{\omega}^{0}\), i.e., \(\bar{x}^{0}=\sum_{\omega\in\Omega}\tau_{\omega}x_{\omega}^{0}\).  
The authors also proposed some heuristics for accelerating convergence. One heuristic is called \"variable fixing\". The values of some of the first-stage decisions \(x_{\omega,i}\) are fixed after they stay at a given value \(z_{i}\) for a few iterations for all scenarios. In order to apply this heuristic, the authors introduced a lag parameter \(\mu\). At a given PH iteration \(k\), the value of \(x_{\omega,i}^{k}\) is fixed to \(z_{i}\) for all subsequent iterations \(l>k\), if \(x_{\omega,i}^{(k)}=z_{i}\) for all \(\omega\in\Omega\) and \(m\in\{k-\mu|\Omega|,\ldots,k\}\), such that \(m\geq\mu|\Omega|\). Additionally, the authors proposed another more aggressive variable fixing heuristic called \"variable slamming\", where the \(x_{\omega}^{k}\) is fixed if they are \"sufficiently converged\", i.e., there can be some discrepancies for \(x_{\omega}^{k}\) across all scenarios. In order to decide when variable slamming should be applied, the authors proposed several termination criteria based on the deviations of the first-stage variab  
\begin{table}
\begin{tabular}{c c c c c c c c} \hline \hline \multirow{2}{*}{**Name**} & \multirow{2}{*}{**Scenarios**} & \multicolumn{4}{c}{**First Stage**} & \multicolumn{4}{c}{**Second Stage**} \\ \cline{3-8}  & & **Rows** & **Cols** & **Ints** & **Rows** & **Cols** & **Ints** \\ \hline sslp\_5\_25 & 50, 100 & 1 & 5 & 5 & 30 & 130 & 125 \\ sslp\_10\_50 & 50, 100, 500, 1000 & 1 & 10 & 10 & 60 & 510 & 500 \\ sslp\_15\_45 & 5,10,15 & 1 & 15 & 15 & 60 & 690 & 675 \\ sslprf\_5\_25 & 100 & 1 & 5 & 5 & 30 & 130 & 125 \\ sslprf\_5\_50 & 100 & 1 & 10 & 10 & 60 & 510 & 500 \\ dcap 233 & 200, 300, 500 & 6 & 12 & 6 & 15 & 27 & 27 \\ dcap 243 & 200, 300, 500 & 6 & 12 & 6 & 18 & 36 & 36 \\ dcap 332 & 200, 300, 500 & 6 & 12 & 6 & 12 & 24 & 24 \\ dcap 342 & 200, 300, 500 & 6 & 12 & 6 & 14 & 32 & 32 \\ \hline \hline \end{tabular}
\end{table}
Table 1: The sizes of the problems tested.  
In solving stochastic mixed-integer programs with PH, the cyclic behavior can be found in some instances. In order to detect the cyclic behavior, the authors proposed a strategy based on the values of the \(u_{\omega}\) vectors, i.e., the weights associated with the first-stage decision variable \(x_{\omega}\). The authors proposed a simple hashing scheme. Let hash value \(h(i)=\sum_{\omega\in\Omega}z_{\omega}u_{\omega,i}\), where \(z_{\omega}\) is an integer hash weight for each scenario \(\omega\in\Omega\) when the PH is initialized. If equal hash weights are detected, they are interpreted as evidence for a potential cycle. Variable \(x_{i}\) can be fixed if cyclic behaviors are found.  
The heuristics, including variable fixing and slamming and cyclic behavior detection, are denoted as WW (Watson-Woodruff) heuristics in the software distribution of PySP.