深刻淺出列生成算法
本文儘可能避免數學公式，使用文字解釋列生成算法的原理，爭取讓讀者能造成直觀上的理解。算法
爲何須要了解列生成算法的原理
- 列生成算法沒法簡單地調用第三方庫來使用，必須根據具體問題，構造不一樣的算法模型。
- 只有瞭解了原理，才能在踩到各類坑時，有所針對地去優化各類細節。否則只能抓瞎或者抓腮。
列生成算法原理
列生成算法能夠從兩個視角來理解：對偶角度和單純形算法角度。框架
對偶角度
啥是對偶
這裏簡單過一下對偶的概念。函數
假設有個長得很標準的線性規劃問題：優化
那麼，它的對偶問題爲：3d
下面咱們都以這個問題來討論，即說到原問題時，默認是一個最小化問題；說到對偶問題時，默認是一個最大化問題。rest
怎麼理解這個對偶關係呢？借用經濟學方面的話來講，假設原問題的目標是讓成本最小，那麼對偶就是讓收入最大。更確切地講，是：blog
- 原問題丶：保證收入不低於某個值的條件下，使成本最小化。
- 對偶問題：保證成本不高於某個值的條件下，使收入最大化。
那個丶純粹是爲了對齊，忽略之……繼承
能夠看到，原問題和對偶問題其實就是一個問題：目標淨收益最大。只是一個是約束收入優化成本，一個是約束成本優化收入。角度不一樣而已。體如今公式上，就是原問題的變量對應對偶問題的約束，目標係數對應約束邊界，約束矩陣倒轉過來。接口
另外，關於對偶，一個比較重要的特性是：原問題的最優值與對偶問題的最優值相等。數學
從對偶角度看列生成算法
列生成算法主要用途在於求解變量多，可是大部分變量將會取值爲0的線性規劃問題。整體思路是先忽略大部分變量，構造一個只使用小部分變量的模型（其他變量至關於值爲0），這樣就能很快求出一個解。而後尋找模型外的變量，找到可以讓目標值更優的變量，加入模型再次求解。重複這個過程直至找不到更好的變量。
這個過程的關鍵問題在於，怎麼評估模型外的變量是否能讓目標值更優。
咱們從對偶的角度來研究這個問題。
原問題的變量對應對偶問題的約束。因此原問題新增變量，至關於對偶問題新增約束。
原問題新增變量 -> 對偶問題新增約束
因爲對偶問題是個最大化問題，因此對偶問題新增約束後，顯然最優值不變或變差，也就是不變或變小。從常理上看，約束越多，最優值越差嘛。
而前面提到的，原問題的最優值等於對偶問題的最優值。也就是說，若是對偶問題最優值不變，那麼原問題最優值也不變；若是對偶問題最優值變小，那麼原問題最優值也變小。而咱們須要的正是讓原問題的最優值變小。
因此問題變爲如何儘可能避免新增的約束沒有改變最優值。設想一下，當加入新約束時，若是當前對偶的最優解沒有違反新的約束，那麼這個解仍然會是新增約束後的對偶問題的最優解，最優值將不變。
所以，咱們要找的新增的約束，要和當前最優解衝突。
整條邏輯鏈爲：
新增變量後原問題最優解變小 -> 新增約束後對偶問題最優解變小 -> 新增約束前的最優解不在新增約束後的可行域 -> 新增約束前的最優解不知足新增的約束
一行對偶問題的約束的公式爲：
假設最優解爲w*，那麼違反約束的條件爲：
變換一下，變成：
左側的式子，叫作的reduced cost，也叫作檢驗數。
經過分析，咱們知道，只要加入reduced cost小於0的對偶約束（從而加入了原問題對應的變量）便可。
很天然的想法是，咱們更傾向於找到reduced cost最小的一個或幾個變量加入，也就是最好能找到最小化reduced cost的新約束：
這裏就出現了一個新的最優化問題。這個問題叫作列生成的子問題（sub problem）。其中w*是已知的，未知量是c和a。c和a是和問題的應用場景有關的，須要根據實際場景來構造c和a的約束條件。因此子問題沒法通用地求解，只能根據具體問題選擇不一樣的方法求解。
當全部未加入模型的變量的reduced cost都大於等於0時，目標值沒法再優化，說明咱們已獲得最優解。
另外，熟悉對偶問題經濟學含義的同窗會知道，reduced cost是指產品的差額成本。那麼顯然要新增的是差額成本爲負的產品了。這是另外一種理解列生成的思路。
單純形算法角度
對偶角度給出了一個偏感性的方式來理解列生成算法。換個視角，從單純形算法角度上看，則是單純形算法自己，爲了更高效地求解包含大量變量的問題，天然地擴展爲列生成算法。
相信有很多人被單純形算法虐得有心理陰影——公式複雜，手工計算量也巨大……
其實，若是咱們先不看細節，單純形的核心原理並無那麼難以理解。下面講解時不會很嚴謹，理解算法框架就夠了。嚴謹的過程請參閱運籌學相關書籍。
單純形算法
衆所周知，單純形算法有一個幾何上的解釋：
- 線性規劃是一個凸優化問題，局部最優解就是全局最優解。
- 線性規劃的解空間是一個n維的凸多面體。最優解在這個凸多面體的某個頂點上。
- 單純形算法從一個初始頂點開始，不斷沿着鄰邊找更好的頂點。
- 當一個頂點四周沒有更好的頂點時，這個頂點就是最優解。
整個過程就像水沿着一條蜿蜒的溝渠流下，最終匯聚到最低點同樣。
問題是，這裏面的幾何概念和代數公式怎麼對應？
這裏用不嚴謹（但更容易理解）的語言說明一下：
- 邊界：解空間是由不等式約束（包括變量非負這些約束）圍起來的一塊空間區域。當點p使得若干個不等式取等號時，那麼點p就在約束邊界的超平面上。這個邊界多是一個面、邊、頂點。
- 頂點：頂點會讓儘可能多的約束取等號。也就是說，頂點是由若干個改成等號的約束組成的方程組的解。咱們叫這個方程組爲約束邊界方程組。
- 沿着邊：約束邊界方程組去掉一個方程，其解集就變成與頂點鄰接的一條邊。再取一條原方程組外的約束條件加入，所獲得的解就是相鄰的頂點。簡單說，就是約束邊界方程組中替換掉一個方程，造成的新方程組解出來就是相鄰的頂點。
這裏涉及到經過讓約束取等號來求邊界的操做，而不等式亂糟糟地混在方程型的約束和變量非負約束裏，會使這裏的分析比較困難。因此使用單純形算法以前，都會經過引入鬆弛變量、剩餘變量和人工變量等方法（這一步在這裏不重要，不詳細展開了），將線性規劃轉換成以下標準形式：
標準形式中只有變量非負約束包含不等式，其餘約束都是等式。這樣咱們就能夠很容易地作邊界相關的計算了。假設變量數量爲n，等式約束數量爲m。經過轉換而來的標準形式都會有n > m。那麼，咱們知道，只要讓n-m個變量等於0，剩下的m個變量就能夠經過這m個等式聯立方程組（約束邊界方程組）求出一個解（簡單起見，不考慮無解，無數解這些邊緣條件）。這個解就是一個頂點。
這裏約束邊界方程組中的m個變量叫做基變量，固定值爲0的n-m個變量叫做非基變量。
沿着邊找相鄰頂點，就是取一個被固定爲0的非負約束，也就是一個非基變量（這個操做叫入基），替換掉一個基變量（這個操做叫出基，這個變量出基後就固定值爲0），而後從新求解一個頂點。
入基操做須要選擇入基變量，選擇的依據是這個變量在目標函數中的降低速度，也就是這個變量增長1時，目標值減小多少。通過推導可知，降低速度的計算公式恰好是檢驗數（reduced cost）。這裏就和對偶的視角聯繫起來了。
出基操做這裏就不細說了，大體的思路是在約束條件下，舊的基變量有一部分會隨着入基變量的增加而降低，其中最早降低到0的舊的基變量就會被選爲出基變量。
整個單純形算法的計算步驟是：
- 選取基變量和非基變量，簡單能出初始解就好。
- 計算全部非基變量的reduced cost，找到最小且爲負值的那個做爲入基變量。若是reduced cost都大於等於0，迭代終止。
- 選出基變量
- 解約束邊界方程組，回到步驟2
從單純形算法角度看列生成算法
在單純形的步驟2，須要計算全部非基變量的RC。找到最小的那個。當變量個數不少的時候，這一步就成爲了算法運行時間瓶頸。
在一些狀況下，經過巧妙構造問題，可讓這一步不須要遍歷全部變量。甚至咱們都不須要知道有多少變量，只要能在每次迭代的時候生成一個或者多個變量，提高優化效果就能夠了。
因爲不須要遍歷全部變量，因此一開始就不須要使用全部變量，只須要使用一組能產生初始解的初始變量構成線性優化問題便可。這種只使用部分變量的模型被稱爲原問題的restricted master problem（RMP）。
每次迭代時，生成一個或多個讓reduced cost最小的變量加入RMP。這個生成步驟就是求解子問題。不斷加入新變量直到沒有小於0的reduced cost的變量時就達到最優解。
到這裏就和對偶角度分析的結果一致了。
下面是單純形算法與列生成算法簡要流程圖的對比，能夠看到，二者的結構是同樣的。
通常來講，咱們不會手搓單純形算法，因此正常都是直接調用單純形算法庫解RMP，而後作列生成，再跑RMP，直到達到最優。
一個經典例子：Cutting Stock Problem
這是一個列生成算法的經典例子。
原紙卷每一個長17m，顧客們分別須要25個3m長，20個5m長，18個7m長的紙卷。
問：如何切割使消耗的原紙卷數量最少？
令一個原紙卷的切割方案集合爲：
P = {(a, b, c) | 3a + 5b + 7c <= 17}
其中，a是一個原紙卷切割出的3m紙卷數量，b是5m紙卷數量，c是7m紙卷數量。
咱們用變量x(abc)表示使用切割方案(a, b, c)的原紙卷數量。
顯然，一個變量與一個原紙卷切割方案一一對應。建模以下：
這裏故意不適用傳統的下標序號標記，意在突出咱們不須要對變量編號，只須要知道變量在對應在什麼集合上，如何經過集合中的元素生成變量就好了。
初始解很好找。好比說咱們能夠取25個原紙卷按照方案(1, 0, 0)切割，20個原紙卷按照方案(0, 1, 0)切割，18個原紙卷按照方案(0, 0, 1)切割。這固然會有不少浪費。可是初始解可行就能夠了，浪費的部分會在下面的迭代中優化掉。
接下來要生成變量。變量與切割方案一一對應的。因此是要找出一個切割方案(a, b, c)，使得reduced cost最小。
其中w一、w2和w3分別爲約束R一、R2和R3的對偶值。
約束條件除了a、b、c非負外，還須要知足切割後的紙卷長度綜合小於或者等於原紙卷的長度。
這樣子問題就構造好了。求解子問題獲得新增變量。而後迭代直到最優。具體計算這裏不展開了。
整數規劃求解
前面提到的單純形算法和列生成算法求解的都是線性規劃。在實際應用中，通常還會須要求解整數規劃。也就是變量都約束爲整數的線性規劃。
這裏先提一個概念：整數規劃的線性鬆弛，整數規劃問題，不考慮整數約束，剩下的約束條件和目標組成的線性規劃問題。
其實咱們並無很好的方法直接求解整數規劃，一般都是不斷地調整並求解線性鬆弛，最後找到最優整數解。
分支定界
分支定界是一個用來求整數優化問題的框架。其實思路很簡單，就是採用相似二分法的技巧，在線性解空間中暴力搜索整數解。
首先，求解線性鬆弛獲得線性解。取一個變量x進行分支。好比x線性解值爲1.2，那麼產生 x <= 1 和 x >= 2 兩個分支。將這兩個條件分別加入到線性鬆弛，獲得兩個線性規劃。再求解這兩個線性規劃，兩個又分別分支……直到求得最優解。
有些狀況下判斷一個解是否爲最優解是有方法的，因此不用搜索全部分支。可是，分支定界在最壞狀況下的時間複雜度還是指數級。爲了防止運行時間過長，通常使用分支定界時還會額外加一些終止條件，好比回溯次數限制、運行時間限制、找到第一個整數解就結束等。
分支訂價
分支訂價就是在分支定界框架中，使用列生成算法來求解每一個分支節點的算法。
不過這裏，除了根節點，其餘節點不用從頭開始生成新變量，繼承父節點用到的變量便可，這樣能夠節省不少重複生成變量的過程。
在01整數規劃中，還有更簡化的方法，每次列生成獲得線性鬆弛的最優解後，找出值最接近1的變量，新加這些變量等於1的約束，繼續跑列生成，直到找出因此值爲1的變量。剩下的天然都是0了。這個方法能夠加入回溯，也能夠不回溯，出現無解就直接結束……聽說不回溯也不多出現無解的狀況。
一些相關問題
退化問題/類退化問題
經過RC找的新變量不必定能讓目標值變得更好，仍然存在不變的可能。極小機率的狀況下，單純形算法可能會有入基變量和出基變量循環出現的狀況。因爲咱們確定是調用線性規劃庫來跑單純形的，因此不用考慮這個……
列生成沒有出基操做，不會出現循環。可是有一些改進會剔除冗餘變量，這時就會有極小几率會出現循環了。這種狀況不須要費心去處理，玄學調參下降出現機率，並設置最大迭代次數等強制終止條件，確保能終止就好。
最噁心的狀況是沒有循環，可是長時間沒有提高目標值的狀況。這實際上是算法卡在一個拐點上了，只要過了拐點就能開始提高。特別是在一些約束較強的問題（好比密集的排班問題）中，使用某些啓發式算法或者手工作出來的初始解就很容易出現這種狀況。
而咱們爲了不算法跑過久，一般會設置屢次迭代沒有提高就結束的條件。這可能使算法從拐點出發後，幾回迭代無優化就直接結束了。
這種狀況沒法完美解決。簡單的就是調參加更巧妙地設置結束條件，經過屢次試驗儘可能讓算法能跨過這個拐點。還有另外一個技巧是能夠適當地給約束邊界加一下噪音，好比說小於等於1的約束，能夠放寬到小於等於1.0001。這樣從初始解出發迭代時，因爲邊界寬鬆了一些，變量能夠有些許變化，會讓目標值有一些微小的提高，幫助判斷是否須要結束迭代。
CPLEX計算reduced cost的問題
使用CPLEX時，咱們能夠很方便的設置變量的上下界。好比設置 0 <= x <= 1。這時，x <= 1這部分是會影響reduced cost的值的。而CPLEX接口計算的是沒有考慮這個條件的……因此可能你本身手搓代碼出來reduced cost和CPLEX接口出來的reduced cost不相等。
更嚴重的是，可能你會忘了 x <= 1 這個條件，致使列生成的過程當中算錯reduced cost。
這個問題其實影響不大，主要是會干擾一些計算過程正確性的驗算。
如何驗證子問題有沒有嚴重問題
沒有作分支操做時，線性鬆弛的目標值若是變差，說明子問題可能出現了一些很蠢的問題。
線性規劃求解算法選擇
每次迭代求解線性規劃時，選用不一樣的算法會影響求解時間。根據經驗：
- 增長少許列時（列生成），使用單純形算法（Primal）。
- 增長少許約束時（分支），使用對偶單純形算法（Dual）。
- 其餘狀況，酌情使用對偶單純形算法或者內點法。經過試驗決定。
- 對偶單純形算法快的時候很快，慢的時候很慢。
- 內點法速度比較穩定。
以上也並非全部場景通用的。應當針對具體問題，反覆試驗來肯定使用什麼算法。
迭代中剔除冗餘變量
Reduced cost能夠用來評估變量的「有用」程度。越小表示變量越有用，越大表示變量越可有可無。
列生成迭代次數較多後，變量數量會愈來愈多，從而每次迭代的運行速度愈來愈低。能夠設定一個變量規模上限，當變量數量大於上限時，從模型中去掉reduced cost最大的那些變量。