Decomposition methods for two-stage stochastic program with integer variables

Question

In a stochastic programming problem, I have binary variables in the second stage. As an example, consider that the optimization problem is given by: \begin{align} &\text{minimize} &\gamma\\ &\text{subject to} &M\cdot Y_{s} &\geq (b-\omega^{s}){'}X -\gamma &&\text{$s = 1,\dots,S$} \tag1\\ &&\sum_{s=1}^{S} Y_{s}P_{s} &\leq \alpha \tag2\\ &&Y_{s} &\in \{0,1\} &&\text{$s = 1,\dots,S$} \\ \end{align} where $\gamma$ is free, $X$ is the vector of optimization variables $0\leq x_{i} \leq 1$ $i = 1,...,n$,
$\alpha$ is the confidence level, $M$ is a big constant, $b$ is a vector of constant values of $X$, $\omega^{s}$ is a vector of uncertain values of $X$, $P_{s}$ is the probability of a scenario, and $S$ is the number of scenarios.

My understanding is that benders decomposition cannot be used due to presence of binary variables in the second stage. The extensive form may be difficult to solve if the number of scenarios are large.

What decomposition methods can be used for this problem? How it can be formulated as a two stage stochastic programming problem using the suggested method?

Answer 1

You can try a master problem of the form \begin{alignat*}{1} \min & \quad \gamma\\ \textrm{s.t.} & \quad \sum_{s=1}^{S}P_{s}Y_{s}\le\alpha\\ & \quad \gamma\ge\gamma_{T}\left[\sum_{s\in T}(1-Y_{s})-|T|+1\right]\quad\forall T\in\mathcal{T}\\ & \quad Y_{s}\in\left\{ 0,1\right\} \quad\forall s\in\left\{ 1,\dots,S\right\} \end{alignat*} where $\mathcal{T}$ is a set of subsets of $\lbrace 1,\dots, S\rbrace$ defined below. Initially $\mathcal{T}=\emptyset$. Each time you find a candidate solution $\hat{Y}$ to the master problem, set $T=\lbrace s : \hat{Y}_s = 0\rbrace$ and solve the LP \begin{alignat*}{1} \min & \quad \gamma\\ \textrm{s.t.} & \quad \gamma\ge(b-\omega^{s})^{\prime}X\quad\forall s\in T. \end{alignat*} Let $\gamma_T$ be the optimal objective value of the LP. If $\gamma_T$ is greater than the value of $\gamma$ in the candidate master solution, add $T$ to $\mathcal{T}$ and add the corresponding constraint to the master. Otherwise, do not add a cut. Either way, continue solving the master problem until the MIP solver declares victory.

Answer 2

To solve stochastic programming models with integer recourse, there are some methods. Most stochastic programming textbooks cover these methods. For example, chapter 7 of Introduction to Stochastic Programming by Birge and Louveux covers these techniques. In particular, I suggest either using the integer L-shaped method or the progressive hedging algorithm (PHA). The basic idea of the integer L-shaped is to employ the combinatorial benders-type cuts to handle the integer recourse problem (see here for the original reference and here for an improved version of the algorithm). The basic idea of PHA is to enforce nonanticipativity constraints (i.e., having the same first-stage variables for all the scenarios) using penalty terms similar to the idea of Lagrangian relaxation (see here for the original reference and here for improved versions of the algorithm).