本文由傳統集合劃分優化問題入手，結合工業背景，引入列生成技術在路徑優化選擇中的運用，并使用經典例子解釋特殊結構在列生成算法中的重要使用。
一、集合劃分問題
集合劃分問題是組合優化中的一類經典問題，其大架構可被定義為将一組集合中的元素劃分多個互斥非空集合。其數學表達可以為：對于集合
和集合
，找到一個劃分
滿足
限制條件即意味着劃分集合的并集等于原集合，且用于劃分的任意兩個不同集合不相交。
當集合
被賦予成本
時，該問題就轉化為一個優化問題，即找到成本最小的分割。
二、集合劃分到路徑優化選擇
于上述理論，當我們把
集合I看做一系列分布在不同地理位置的
訂單，
集合S看做是一系列途經其中某些地理位置的
路線，成本
c定義為經營每條路徑的
成本（包括使用成本，營運成本），該問題則成為了一個傳統的路徑優化問題之一，即
找到覆寫所有訂單的成本最小路徑集合。
首先，我們将該問題用數學模型表示
其中變量為
，代表着路徑r是否被選擇使用，如果選擇那麼
，否則等于0。
參數
為每條路徑的成本，則目标函數代表成本最小化路徑選擇。而
即代表該路徑特征，如果路徑r經過訂單i所在位置，則
，否則等于0。
我們将使用一個小例子來幫助了解，
每條路徑的成本：
每條路徑的特征：
每條路徑的決策變量：
同時，我們可以對此整數規劃進行松弛，即去掉整數限制使得其成為線性優化，以更友善了解和闡釋列生成算法。
通常而言，如果規劃問題為IP（integer programming, 整數規劃）或者MIP(mixed integer programming, 混合整數規劃)則算法過程将更為複雜，基于不同問題運用到的算法有Branch and Bound(分枝定界), Cutting plane（割平面）, Danzig-Wolf, Column Generation（列生成）等或其他組合算法例如branch and cut（分枝裁剪法）, branch and pricing（分枝定價）等。
松弛後在處理實際問題時，我們會面臨兩個問題：
1) 訂單數目增長導緻可行路徑的數目N通常十分巨大，我們如何找到所有的可行路徑？
2) 如果已找到N條可行路徑，如何快速求解這一龐大的整數規劃？
通常我們有針對該問題的解決辦法為：
1）使用啟發式算法，比如Local Search: Hill Climbing, 2-opt, 3-opt, k-opt或者Metaheuristics: Genetic Algorithm (GA), Simulated Annealing (SA), Tabu Search (TS)去找尋“可行最優”路徑。
2）使用列生成算法，計算成本降低數值後僅加入有效的路徑進行求解。或同時在列生成算法過程中，找尋具有特殊結構的Pricing Model(之後将會展現例子)求解出最優被加入的列（路徑）。
本篇文章将主要簡單介紹如何使用列生成技術，基于已有所有可行路徑的情況下，加速算法過程，得到最優解。同時會介紹針對另一經典問題(cutting stock problem) ，闡述如何使用pricing model的特殊結構更加快速有效的求解。
三、單純形法回顧
首先在介紹列生成前，我們需要回顧一下基于線性規劃的單純形法與我們将會使用到的一些變量定義：
定義1：基礎可行解(b.f.s.) x：即為滿足
1）有n個線性無關的限制在x為等式
2）所有等式限制在x處成立
3）滿足所有限制條件
定義2：極點（extreme point）：即為b.f.s.的幾何表示，也有人形象的描述它為corner point。
我們可以用一個簡單的例子來闡述，在二維平面用
所圍成的區域内(2,0) 即為唯一的極點。
單純形法步驟說明與利用上述路徑配置設定例子進行定義的可視化：
步驟1：對于線性規劃問題，我們首先需要進行PhaseΙ單純形法以得到一個b.f.s., 否則該問題無解。
例子1：
即上述例子中最直覺的
基于b.f.s.與其對應的基矩陣，對于非基礎解變量，計算reduced cost以判斷是否已得最優解，如果reduced cost均非負則停止，否則判斷哪一個列j需要加入到基礎矩陣
例子2：b.f.s.對應的基矩陣:
基礎解變量:
非基礎解變量:
reduced cost:
其中r∈{6,7,8,9,10}
步驟3：計算解的更新方向與步長
例子3：更新方向：
其中
為被選中加入的非基礎解列
步長：
判斷哪個列将移出基礎矩陣
例子4：若
達到最小步長，則
移出基矩陣
步驟5：更新基矩陣
四、列生成算法流程
列生成顧名思義即對于原問題（Master Problem, MP）一開始僅适用部分列（基矩陣）進行計算(Restricted Master Problem, RMP)，基于基矩陣建立pricing model，基于計算結果，選擇下一循環需要加入的列或者判斷已達到最優解。
在該例子中MP即為：
RMP：
其中R'為R的子集
Pricing Model 即為尋找具有最小reduced cost 的非基礎列加入求解矩陣中，即求解
如果w≥0, 則目前可行解為最優解，否則加入使得reduced cost最小的列進入求解矩陣進行求解。
即其算法流程圖為：
五、小規模基于路徑優化問題執行列生成
現在将繼續适用上述例子模拟該算法：
- 選擇路徑1,2,3,4,5，即基矩陣
建立RMP
2.計算reduced cost
将
加入基矩陣進行求解
3. 重複上述過程，移入
後w≥0
4.是以，我們得到了最優解
。
是以對于Pricing Model:
我們可以通過其對偶問題（Constraint generation）以及強對偶定理，将此步驟替換為計算
y為其對偶變量，對于多數求解器例如CPLEX而言是非常容易獲得的，這将使得計算變得容易。
由于此處提及了對偶問題，是以在此列舉對偶問題的對應模型但不過多介紹，如果感興趣可以更深入的研究：
（MP: Master Problem; DMP: Dual Master Problem; RMP: Restricted Master Problem; DRMP: Dual Restricted Master Problem）
六、特殊結構在列生成算法中的作用
同時，我們還可以對某些具有特殊結構的Pricing Model進行再構造，
直接計算出需要加入的列，而無需一開始通過其他算法得到所有可行列。
比如經典問題cutting stock problem，以下用以數值化小例子幫助了解：
某公司生産長度為100的紙張，而其訂單來自于三個擁有不同長度需求的客戶，他們需要長度為25,35,45的紙張各150,200,300張。那麼為了滿足需求，應該如何剪裁使得使用的紙張數最少呢？
對此，我們有以下的模型：
因為，該篇文章主要介紹列生成，是以首先對該問題進行
松弛，使其成為線性規劃。
當我們開始進行列生成時，我們選擇{9,10,11}作為解矩陣，那麼可以得到
緊接着，針對該問題進行Pricing Model的建立：
即該問題轉化為找到可行的列
使得
最大，
即為對偶變量。
因為該問題的特殊結構，它變為了經典的
knapsack problem，可迅速求解問題。
首先該輪目标函數為：
其限制條件為：其剪裁不可以超過總長度100，且每一種長度類型的剪裁數目必須為整數且大于等于0：
那麼第一輪求解可得：
是以，我們需要循環重複上述過程直到reduced cost非負。
最終經過4次求解，我們得到了最優解。
如果大家對Cutting Stock Problem + Column Generation感興趣的話，下述連結為開源的Julia執行個體與更為具體的求解過程。
https://www.juliaopt.org/notebooks/Chiwei%20Yan%20-%20Cutting%20Stock.html
七、最後的一點碎碎念
發現Pricing Model的特殊結構對于更充分的利用列生成算法是非常有利的，像上述例子，當剪裁長度達到一定長度或需求長度變化過多時，我們很難将可行的所有列都先找出，是以，利用該特殊結構的Pricing Model，我們很好的解決了這一問題。
但對于路徑問題而言，很多時候基于現實因素，其Pricing Model是十分複雜且困難的，是以除了建立Pricing Model 直接找尋加入的列以外，我們可以通過一些巧妙的方法找到所有或大部分可行的線路，以直接計算每一循環的reduced cost。
參考文獻：
Lecture Notes from Dr. Sun - Derterministic Optimization 2017 in Georgia Tech