天天看點

分支定價算法入門分支定價法(branch and price)

分支定價法(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變量松弛為連續變量得到松弛模型)。

  1. 為什麼使用列生成而不是單純形法`

    在面對大規模問題時,變量數量極多,單純形法尋找進基出基變量的速度非常慢,僅僅在尋找進基變量時,就需要對每一個非基變量進行reduced cost的計算,挑選最小的RC。(所謂reduced cost個人了解為某個變量使得目标函數下降的速度,對于優化方向為最小的問題來說,當然這個下降速度越快越好,是以需要尋找reduced cost的最小值)

  2. 列生成法與單純形法的關系

    個人認為列生成法就是單純形法的改進版,它的優勢主要展現在充分的削減變量,降低模型複雜度。相較于單純形法在所有的變量裡尋找最優政策,列生成算法首先尋找一組可行解,并将其餘變量強制置零來生成一個小規模模型(RMP,restricted master problem),然後通過subproblem尋找要生成的列,加入到RMP中,直到不能尋找到使RC<0的列,此時,求解生成的RMP即可得到最優解。列生成算法流程圖以及subproblem生成新列的方式均在下文中有所展示。

列生成算法流程

下面是列生成算法的簡單流程圖

分支定價算法入門分支定價法(branch and price)

列生成算法要點

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​−CB​B−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} CB​B−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中的變量為系數,數量為限制的個數,是以變量數相較于主問題要少很多。話說回來,如果不快也不用這麼麻煩了。

繼續閱讀