最近在写一个新的工作，回顾了一下Integer L-shaped method。之前的认知里对Benders Decomposition和L-shaped Method之间的区别并不是特别清晰，通过这次回顾，有了一些新的认知，故将其写成这篇notes。
1 Two Stage Stochastic Programming
Benders Decomposition是经典的用于求解MILP问题的算法，他利用可分解结构，将复杂决策变量留在master problem中，将简单决策变量留在sub problem中。与Benders Decomposition的思想一致，L-shaped用于求解两阶段随机规划模型（通过采样平均近似后的模型）
$$ \begin{equation*} (\text{TSSP}) \ \min_{\pmb{x} \in \mathcal{X}} \quad \pmb{c}^\top \pmb{x} + \mathbb{E}_{\tilde{\pmb{\xi}} \sim \mathbb{P}} \left[Q(\pmb{x}, \tilde{\pmb{\xi}})\right] \end{equation*} $$基于$N$组scenario，TSSP被近似为
$$ \begin{equation*} (\text{TSSP-SAA}) \ \min_{\pmb{x} \in \mathcal{X}} \quad \pmb{c}^\top \pmb{x} + \sum_{n=1}^{N} w_n Q(\pmb{x}, \hat{\pmb{\xi}}_n) \end{equation*} $$注意到，其具备一阶段问题和$N$个scenario下的recourse问题，天然有可分解结构。
2 L-shaped Method
考虑如下问题，
$$ \begin{equation*} \begin{aligned} \min_{\pmb{x}, \pmb{y}_n} \quad & \pmb{c}^\top \pmb{x} + \sum_{n=1}^{N} w_n \pmb{q}^\top \pmb{y}_n \\ s.t. \quad & \pmb{A}\pmb{x} \geq \pmb{b} \\ & \pmb{T}\pmb{x} + \pmb{W}\pmb{y}_n \geq \pmb{h}_n, && \forall n \in [N] \\ & \pmb{x} \in \left\{0, 1\right\}^d \\ & \pmb{y}_n \in \mathbb{R}_+^m, && \forall n \in [N] \end{aligned} \end{equation*} $$在L-shaped method下，我们可以构建如下master problem，
$$ \begin{equation*} \begin{aligned} \min_{\pmb{x}, \pmb{y}_n} \quad & \pmb{c}^\top \pmb{x} + \theta \\ s.t. \quad & \pmb{A}\pmb{x} \geq \pmb{b} \\ & \pmb{x} \in \left\{0, 1\right\}^d \\ & \theta \geq \sum_{n=1}^{N} w_n \left[\overline{\pmb{\pi}}_n^\top(\pmb{h} - \pmb{T}\pmb{x}) \right] && (\text{Optimality cuts}) \\ & 0 \geq \overline{\pmb{r}}_n^\top(\pmb{h} - \pmb{T}\pmb{x}) && (\text{Feasibility cuts}) \end{aligned} \end{equation*} $$对于任意给定的一阶段决策$\overline{\pmb{x}}$，scenario $n$的primal subproblem是
$$ \begin{equation*} \begin{aligned} Q(\overline{\pmb{x}}, \hat{\pmb{\xi}}_n) = \min_{\pmb{y}_n} \quad & \pmb{q}^\top \pmb{y}_n \\ s.t. \quad & \pmb{W} \pmb{y}_n \geq \pmb{h} - \pmb{T}\overline{\pmb{x}} \\ & \pmb{y}_n \in \mathbb{R}_+^m \end{aligned} \end{equation*} $$其dual问题可以写成
$$ \begin{equation*} \begin{aligned} \max_{\pmb{\pi}_n} \quad & \pmb{\pi}_n^\top (\pmb{h} - \pmb{T}\overline{\pmb{x}}) \\ s.t. \quad & \pmb{W}^\top\pmb{\pi}_n \leq \pmb{q} \\ & \pmb{\pi}_n \in \mathbb{R}_+^a \end{aligned} \end{equation*} $$整体上，L-shaped Method可以表述为，
Algorithm 1 L-shaped Method
Step 1: Initialization
Initialize lower bound $LB=-\infty$ and upper bound $UB=+\infty$;
Set iteration counter $k=1$;
Step 2: Solve the master problem
Solve the current master problem to get a solution $(\overline{\pmb{x}}_k, \overline{\theta}_k)$;
Update the lower bound $LB=\max(LB, \pmb{c}^\top\overline{\pmb{x}}_k + \overline{\theta}_k)$;
Step 3: Check for convergence
If $UB - LB \leq \epsilon$, STOP. The optimal solution is found;
Step 4: Solve the subproblems
For each scenario $n \in [N]$, solve the dual subproblem with the fixed value $\overline{\pmb{x}}_k$;
Step 5: Generate and add cut
If a subproblem is infeasible, add a feasibility cut to the master problem;
If all subproblems are feasible, add a optimality cut to the master problem;
Step 6: Loop
Increment $k = k + 1$ and go back to Step 2;
3 Integer L-shaped Method
特别地，对于Recourse问题中包含整数变量时，上述L-shaped Method无法应用。但是，类似地我们可以将问题分解为如下master problem，
$$ \begin{equation*} \begin{aligned} \min_{\pmb{x}, \pmb{y}_n} \quad & \pmb{c}^\top \pmb{x} + \theta \\ s.t. \quad & \pmb{A}\pmb{x} \geq \pmb{b} \\ & \pmb{x} \in \left\{0, 1\right\}^d \\ & ... && (\text{No-good Cuts}) \\ & ... && (\text{Integer Optimality Cuts}) \end{aligned} \end{equation*} $$对于任意给定的一阶段决策$\overline{\pmb{x}}$，每一个场景$n \in [N]$对应的Subproblem为如下MILP问题，
$$ \begin{equation*} \begin{aligned} Q(\overline{\pmb{x}}, \hat{\pmb{\xi}}_n) = \min_{\pmb{y}_n} \quad & \pmb{q}^\top \pmb{y}_n \\ s.t. \quad & \pmb{W} \pmb{y}_n \geq \pmb{h} - \pmb{T}\overline{\pmb{x}} \\ & \pmb{y}_n \in \mathbb{Z}_+^m \end{aligned} \end{equation*} $$求解这一问题，可根据其是否可行，向master problem添加No-good Cut或Integer Optimality Cut。
当出现一个$n \in [N]$对应的Subproblem不可行时，说明此时传入的一阶段决策$\overline{\pmb{x}}$应该被排除掉。于是，我们可以添加如下No-good Cut，
$$ \begin{equation*} \sum_{i \in I_1} (1 - x_i) + \sum_{i \in I_0} x_i \geq 1 \end{equation*} $$其中，$I_1$表示值为1的变量集合，$I_0$表示值为0的变量集合。
当所有$n \in [N]$对应的Subproblem都可行时，对应的目标函数值为$Q_n^*$，说明此时传入的一阶段决策对于原问题是一个可行解。于是，我们添加如下Integer Optimality Cut，
$$ \begin{equation*} \theta \geq Q^* - M \left(\sum_{i \in I_1} (1- x_i) + \sum_{i \in I_0} x_i\right) \end{equation*} $$其中，$Q^* = \sum_{n \in [N]} w_n Q_n^*$.
整体的算法流程可以表述为，
Algorithm 2 Integer L-shaped Method
Step 1: Initialization
Initialize lower bound $LB=-\infty$ and upper bound $UB=+\infty$;
Set iteration counter $k=1$;
Step 2: Solve the master problem
Solve the current master problem to get a solution $(\overline{\pmb{x}}_k, \overline{\theta}_k)$;
Update the lower bound $LB=\max(LB, \pmb{c}^\top\overline{\pmb{x}}_k + \overline{\theta}_k)$;
Step 3: Check for convergence
If $UB - LB \leq \epsilon$, STOP. The optimal solution is found;
Step 4: Solve the subproblems
For each scenario $n \in [N]$, solve the dual subproblem with the fixed value $\overline{\pmb{x}}_k$;
Step 5: Generate and add cut
If a subproblem is infeasible, add the No-good Cut to the master problem;
If all subproblems are feasible, add the Integer Optimality Cut to the master problem;
Step 6: Loop
Increment $k = k + 1$ and go back to Step 2;
Reference
[1] Birge, J. R., & Louveaux, F. (1997). Introduction to stochastic programming. New York, NY: Springer New York.
[2] Laporte, G., & Louveaux, F. V. (1993). The integer L-shaped method for stochastic integer programs with complete recourse. Operations research letters, 13(3), 133-142.