分支定價算法入門

分支定價法（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生成新列的方式均在下文中有所展示。

列生成算法流程

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

列生成算法要點

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