# 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. Sep 20 '20 at 22:08
• You can employ dual decomposition. A more recent reference (alongside some algorithmic techniques) is this paper. Sep 21 '20 at 2:18
• – ktnr
Sep 21 '20 at 7:51
• Is X integer-valued? Sep 21 '20 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. Sep 22 '20 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$ Sep 24 '20 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 '20 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$). Sep 25 '20 at 15:34
• Thanks. Now it’s clear to me
– Sam
Sep 25 '20 at 16:55

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).

• Thanks @Ehsan. How would you formulate this problem in the format of integer L-shaped form? I mean which variables will be formulated as first stage and which as second stage. If there are any relevant examples in chapter 7 of Introduction to Stochastic Programming for this use case then please let me know.
– Sam
Sep 21 '20 at 22:25
• The difference between the first and second stage variables is that the former must be decided before the realization of uncertainty. Hence, the first-stage variables don't take a scenario index. In your model (if modeled correctly), the vector X must be the first stage variables. This concept is a general concept in stochastic programming and not specific to stochastic integer programming. You might see my answer here for a brief discussion. Section 1.1 of "Introduction to Stochastic Programming gives a good example, known as the farming example. Sep 22 '20 at 5:16