1. 行生成算法
行生成就是指的不断添加约束的算法。
因为在求解矩阵中，一个约束条件对应一行，因此添加约束条件的方法自然叫做行生成算法。相对应的，添加变量的方法就叫做列生成算法。
这一节先看行生成算法，用在求解变量不多，但是约束条件特别多的情况下。
2. Benders分解
Benders分解（Benders Decomposition，BD）的基本思路是：使用子问题（primal problem）来寻找合适的约束不断添加到松弛主问题（relaxed master problem）中。子问题可以给上界（UB），松弛主问题可以给下界（LB），不断迭代就可以逐步找到最优解。具体可以参考论文：http://www.ie.boun.edu.tr/~taskin/pdf/taskin_benders.pdf，这里做一下简单的概述：
问题模型是：
min cx+fy
s.t. Ax+By = b
y∈Y
Benders分解将上述模型拆分为只包含x变量的子问题和只包含y变量的主问题。
2.1. 子问题
子问题（SP）为：
min cx
s.t. Ax = b - By
使用对偶法求解子问题（DSP）：
max α(b-By’)
s.t. Aα ≤ c
α无限制
这是个线性规划问题，枚举可行域{α : Aα≤c}的极点（I）和极方向（J）便可以求解了，上面DSP等价于：
min q
s.t. αi (b-By) ≤ q
αj(b-By) ≤ 0
q无限制
2.2. 主问题
定义q(y)为SP问题的最优解，则原问题可以重新写为如下主问题的形式：
min q(y)+fy
s.t. y∈Y
等价于下面的主问题（MP）：
min q+fy
s.t. αi (b-By) ≤ q
αj(b-By) ≤ 0
y∈Y，q无限制
2.3. benders分解求解步骤
由于约束条件较多，因此α也是非常多的，直接上所有约束条件求解MP比较困难。因此从少量约束条件的松弛主问题开始，逐步把约束条件加上。
- 求解松弛主问题RMP，得到y*∈Y，得到的q*用来更新下界LB。
- 将y*代入对偶子问题（DSP）求解。
2.1. 若DSP存在最优解，假设是在极点α'处取得，则用α'(b-By’)+fy'更新上界UB，并且给主问题MP添加约束条件α' (b-By) ≤ q
2.2. 若DSP存在无界最优解，假设是在极线α'处取得，则给主问题MP添加约束条件α'(b-By) ≤ 0 - 求解新的松弛主问题RMP'，回到1进行迭代直至LB ≥ UB。
3. Benders分解例子
在下面的问题中，y∈{0,1}属于复杂约束，因此将原问题按如图的颜色拆分开。
一轮迭代后，UB = 23，LB = 8，还需要继续迭代。后面的求解过程省略。
4. 广义Benders分解
Benders分解法要求子问题必须为线性，而广义Benders分解法（Generalized Benders Decomposition，GBD）针对这个问题作了改进。广义Benders分解的问题模型是：
min f(x,y)
s.t. g(x,y) ≤ 0
y∈Y
由于涉及到了非线性规划，因此要用到拉格朗日法。求解的步骤是：
选取y'∈Y，求解子问题：
min f(x,y')
s.t. g(x,y') ≤ 0
使用拉格朗日法，令L(x,u,y) = f(x,y) + Σu*g(x,y)，使用KKT条件求解。如果子问题可行，则用最优解更新UB；并且给主问题添加约束条件（可行割）：
q ≥ L(x',u',y') + L'|y(x',u',y')*(y-y')
其中x'，y'是子问题的变量取值。如果子问题不可行，则引入剩余变量s后求解新的子问题：
min s
s.t. g(x,y') ≤ s
同样使用拉格朗日法，求得x'和u'，然后给主问题添加约束条件（不可行割）：
s.t. 0 ≥ u'*(g(x',y')+g'|y(x',y')*(y-y'))
其中x'，y'是新的子问题的变量取值。求解主问题：
min q
s.t. 所有的可行割和不可行割满足条件。
求得的结果更新LB。不断迭代，直到 LB ≥ UB。
