# Decomposition methods for two-stage stochastic program with integer variables

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?

• Search for combinatorial Benders decomposition or logic-based Benders decomposition. – RobPratt Sep 20 at 22:08
• You can employ dual decomposition. A more recent reference (alongside some algorithmic techniques) is this paper. – mtanneau Sep 21 at 2:18
• – ktnr Sep 21 at 7:51
• Is X integer-valued? – prubin Sep 21 at 21:37
• It should not be too hard to implement a working version of the dual decomposition (DD) part. Going from "working" to "fast" will likely be some work though. That being said, note that the DD only gives a dual bound, i.e., it must be complemented by primal techniques to find feasible solutions. Not sure how simple to implement that part is. – mtanneau Sep 22 at 17:02

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.
• The quantity in brackets simplifies a little: $1-\sum_{s\in T} Y_s$ – RobPratt Sep 24 at 18:29
• Thank you @prubin, I would like to clarify few points: 1. $\gamma_{T}$ appears in the Master problem and is defined as the optimal objective value of the LP. What value of $\gamma_{T}$ should be assumed in the master problem initially (in the first iteration) or the LP needs to be solved first? 2. I am a bit confused with definitions of $\mathcal{T}$ and $T$. Does $\mathcal{T}$ represent a set of optimality cuts? Is $|T|$ = $\phi$ set initially? – Sam Sep 24 at 21:51
• $\mathcal{T}$ is a set of sets $T$, with each $T$ generating an optimality cut. Initially, $\mathcal{T}=\emptyset$, so the master starts with just constraint (2) and the first candidate solution generated in the master problem will have $\gamma=0$. Each candidate solution generates a set $T$ (indices for which $Y_. = 0$). – prubin Sep 25 at 15:34