1. 行生成算法
行生成就是指的不斷添加約束的算法。
因?yàn)樵谇蠼饩仃囍刑汛粋€(gè)約束條件對應(yīng)一行蹭睡，因此添加約束條件的方法自然叫做行生成算法蓖救。相對應(yīng)的从橘，添加變量的方法就叫做列生成算法踩萎。
這一節(jié)先看行生成算法码倦，用在求解變量不多蝗柔，但是約束條件特別多的情況下。
2. Benders分解
Benders分解（Benders Decomposition，BD）的基本思路是：使用子問題（primal problem）來尋找合適的約束不斷添加到松弛主問題（relaxed master problem）中喻圃。子問題可以給上界（UB）予权，松弛主問題可以給下界（LB），不斷迭代就可以逐步找到最優(yōu)解习绢。具體可以參考論文：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
α無限制
這是個(gè)線性規(guī)劃問題，枚舉可行域{α : Aα≤c}的極點(diǎn)（I）和極方向（J）便可以求解了鸭栖，上面DSP等價(jià)于：
min q
s.t. αi (b-By) ≤ q
αj(b-By) ≤ 0
q無限制
2.2. 主問題
定義q(y)為SP問題的最優(yōu)解，則原問題可以重新寫為如下主問題的形式：
min q(y)+fy
s.t. y∈Y
等價(jià)于下面的主問題（MP）：
min q+fy
s.t. αi (b-By) ≤ q
αj(b-By) ≤ 0
y∈Y躁锁，q無限制
2.3. benders分解求解步驟
由于約束條件較多刁标，因此α也是非常多的撵儿，直接上所有約束條件求解MP比較困難淀歇。因此從少量約束條件的松弛主問題開始浪默，逐步把約束條件加上。
- 求解松弛主問題RMP胜榔，得到y(tǒng)*∈Y尊惰，得到的q*用來更新下界LB。
- 將y*代入對偶子問題（DSP）求解。
2.1. 若DSP存在最優(yōu)解，假設(shè)是在極點(diǎn)α'處取得，則用α'(b-By’)+fy'更新上界UB址貌，并且給主問題MP添加約束條件α' (b-By) ≤ q
2.2. 若DSP存在無界最優(yōu)解铐拐，假設(shè)是在極線α'處取得，則給主問題MP添加約束條件α'(b-By) ≤ 0 - 求解新的松弛主問題RMP'练对，回到1進(jìn)行迭代直至LB ≥ UB遍蟋。
3. Benders分解例子
在下面的問題中，y∈{0,1}屬于復(fù)雜約束螟凭，因此將原問題按如圖的顏色拆分開虚青。
一輪迭代后，UB = 23螺男，LB = 8棒厘，還需要繼續(xù)迭代。后面的求解過程省略烟号。
4. 廣義Benders分解
Benders分解法要求子問題必須為線性绊谭，而廣義Benders分解法（Generalized Benders Decomposition，GBD）針對這個(gè)問題作了改進(jìn)汪拥。廣義Benders分解的問題模型是：
min f(x,y)
s.t. g(x,y) ≤ 0
y∈Y
由于涉及到了非線性規(guī)劃达传，因此要用到拉格朗日法。求解的步驟是：
選取y'∈Y迫筑，求解子問題：
min f(x,y')
s.t. g(x,y') ≤ 0
使用拉格朗日法宪赶，令L(x,u,y) = f(x,y) + Σu*g(x,y)，使用KKT條件求解脯燃。如果子問題可行搂妻，則用最優(yōu)解更新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. 所有的可行割和不可行割滿足條件引几。
求得的結(jié)果更新LB。不斷迭代挽铁，直到 LB ≥ UB伟桅。
