分支定價法(branch and price)
分支定價
- 分支定價法(branch and price)
-
- 組成
- 分支定界法
- 列生成算法
- 列生成算法流程
-
- 列生成算法要點
組成
~~~~~~ 分支定價由分支定界(branch and bound,B&B)和列生成算法(column generation)組成,它适用于求解大規模線性規劃問題,其中B&B作為主體。branch and price的算法流程與B&B非常相似,不同的是在求解線性規劃問題的過程中子節點采用column generation進行定界,通過削減變量減少複雜度,提高求解效率。
分支定界法
~~~~~~ 作為五大算法之一,B&B可以解決整數線性規劃和混合整數線性規劃問題。通常單純形法可以解線性規劃的松弛模型,但是由于部分變量的整數限制條件,像 x ⊆ N x\subseteq\mathbb{N} x⊆N或 x = 0 o r 1 x=0 or1 x=0or1,隻求解松弛模型并未達到最終目标。
~~~~~~ 這時候使用branch and bound在可行解空間中搜尋,找出最優整數解,反應到資料結構中就是對二叉樹進行搜尋。
算法邏輯
1求解線性松弛的原問題
1.1 判斷是否可行
a. 如果不可行,則原問題不可行
b. 如果可行,原問題得到整數解,線性松弛後的原問題的解是該問題的最優解,終止算法
c. 如果可行,線性松弛後的原問題沒有得到整數解,則線性松弛後的原問題的目标函數值作為目前根節點的上界,選擇原問題的可行解對應的目标函數值作為目前根節點的下界。根據分支政策進行分支得到子問題,并添加至未被探索的問題集中
2當未被探索的問題集不為空,且上下界的gap大于門檻值,則根據搜尋政策選擇子問題進行探索
2.1 子問題不可行,剪枝
2.2 子問題可行
2.3 子問題得到整數解,子問題的線性松弛的解是該子問題的最優解,剪枝;線性松弛的子問題得到整數解,且線性松弛的子問題所求的目标函數值大于所有葉子結點的上界,算法終止
2.4 子問題沒有得到整數解
當子問題的上界不超過原問題目前所求得的下界,剪枝。否則将線性松弛後的子問題的目标函數值作為目前根節點的上界,選擇子問題的可行解對應的目标函數值作為目前節點的下界。根據分支政策進行分支得到子問題,并添加至未被探索的問題集中。
3算法的終止條件
當未被探索的問題集不為空;如果上界等于下界,或者上界-下界的gap很小,則算法終止。
列生成算法
列生成算法與單純形法一樣,是針對連續模型求解的(先将整數變量或者0-1變量松弛為連續變量得到松弛模型)。
-
為什麼使用列生成而不是單純形法`
在面對大規模問題時,變量數量極多,單純形法尋找進基出基變量的速度非常慢,僅僅在尋找進基變量時,就需要對每一個非基變量進行reduced cost的計算,挑選最小的RC。(所謂reduced cost個人了解為某個變量使得目标函數下降的速度,對于優化方向為最小的問題來說,當然這個下降速度越快越好,是以需要尋找reduced cost的最小值)
-
列生成法與單純形法的關系
個人認為列生成法就是單純形法的改進版,它的優勢主要展現在充分的削減變量,降低模型複雜度。相較于單純形法在所有的變量裡尋找最優政策,列生成算法首先尋找一組可行解,并将其餘變量強制置零來生成一個小規模模型(RMP,restricted master problem),然後通過subproblem尋找要生成的列,加入到RMP中,直到不能尋找到使RC<0的列,此時,求解生成的RMP即可得到最優解。列生成算法流程圖以及subproblem生成新列的方式均在下文中有所展示。
列生成算法流程
下面是列生成算法的簡單流程圖
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsIyZuBnLkVjYyMTYiJTZ5YmN3kTO5YjN4QDZxMmZ1E2NxMDNzIzLc52YucWbp5GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.png)
列生成算法要點
1.如何生成RMP
通常使用啟發式算法尋找一個初始解,以經過啟發式算法尋找的次優解構造RMP,在一定程度上也會加快求解速度。
2.subproblem建立
列生成算法中子問題的功能是尋找使reduced cost<0的列,将此列添加到RMP中,以進一步優化問題。是以它的目标函數即為檢驗數,檢驗數計算方法為 c j − C B B − 1 a j c_j-C_BB^{-1}a_j cj−CBB−1aj ,也就是變量 x j x_j xj在主問題目标函數中對應的系數減去對偶變量與系數矩陣相乘。這裡的 a j a_j aj為主問題系數矩陣中對應變量 x j x_j xj的系數, c j c_j cj為目标函數中 x j x_j xj對應的系數, C B B − 1 C_BB^{-1} CBB−1為對偶變量組成的向量。另外,subproblem中還有限制,主要是對生成規則的限制,當然由于subproblem中的變量為待生成的主問題系數,是以這些限制自然也是針對這些系數的規則。比如在經典的紙卷生成問題中(cutting stock problem),各個切割方案長度的加和不能超過單個紙卷的總長度。
不了解cutting stock problem的小夥伴可以參考部落格這位大佬的https://www.cnblogs.com/codejiaoer/archive/2021/11/24/Column_Geration.html,并且這篇博文還給出了具體的計算步驟,非常有助于了解。
3.subproblem的求解
subproblem求解也是一個優化問題,當然這比直接求解主問題要快多了,因為subproblem中的變量為系數,數量為限制的個數,是以變量數相較于主問題要少很多。話說回來,如果不快也不用這麼麻煩了。