列生成算法的改進策略研究

羅鳳娥，張 鑫，趙 強，楊思瀚

（中國民用航空飛行學院空中交通管理學院，廣漢 618307）

0 引言

列生成算法是一種用于解決大規模線性規劃問題的迭代算法。該算法的核心思想是通過逐步添加列來構建松弛問題的最優解，從而逼近原問題的最優解。在算法的初期階段，只考慮少量的變量和約束條件，隨著計算的進行，逐漸添加新的變量和約束條件，直到得到原問題的最優解。在每次迭代中，它解決了一個受限的主問題（restricted master problem，RMP）和一個定價問題（pricing issues，PP）。受限的主問題是原始線性規劃（linear programming，LP），被限制在其變量的子集中，并由原始線性規劃求解器求解，例如原始單純形算法。與傳統的線性規劃算法相比，列生成算法在處理大規模問題時具有更高的效率和精度，尤其適用于包含大量稀疏約束條件的問題。此外，該算法還具有較好的可擴展性和靈活性，可以通過調整算法參數和優化策略來滿足不同的求解需求。

1 列生成算法的基本原理

列生成算法通過求解子問題（sub problem，SP）來找到可以進基的非基變量，該非基變量在模型中并沒有顯性地寫出來［1］（可以看成是生成了一個變量，每個變量其實等價于一列，所以該方法被稱為列生成算法）。如果找不到一個可以進基的非基變量，那么就意味著所有的非基變量的檢驗數（reduced cost，RC）都滿足最優解的條件，也就是說，該線性規劃的最優解已被找到。其思路如下：

（1）先把原問題（master problem，MP）轉換到一個規模更小（即變量數比原問題少）的問題上，這個只使用部分變量的模型被稱為原問題的RMP 問題。在RMP 上用單純形法求最優解，注意此時求得的最優解只是RMP 上的，并不是MP的最優解。

（2）然后需要通過一個子問題去檢測在那些未被考慮的變量中是否有使得RC 小于零的情況，如果有，那么就把這個變量的相關系數列加入到RMP 的系數矩陣中，返回第一步。經過反復迭代，直到子問題中的RC 都大于等于零，此時就找到了MP的最優解。流程如圖1所示。

圖1 列生成算法流程

2 列生成算法的改進思路

列生成算法的改進思路主要有以下四個方面。

2.1 加速松弛問題的求解

松弛問題的求解是列生成算法中的瓶頸，因此加速松弛問題的求解可以提高整個算法的效率。可以通過優化線性規劃求解器、改進算法的分支策略和剪枝技術、引入啟發式算法等方法來加速松弛問題的求解。

優點：通過優化線性規劃求解器、改進算法的分支策略和剪枝技術、引入啟發式算法等方法來加速松弛問題的求解，可以大幅提高算法的效率和精度。

缺點：一些優化方法可能會增加算法的復雜度，導致運算時間和空間開銷增加。

2.2 改進列選擇策略

列選擇策略是列生成算法中的關鍵因素，決定了列的質量和數量，因此改進列選擇策略可以提高算法的精度和效率。可以通過引入先進的列選擇策略、基于貪心策略的啟發式算法等方法來改進列選擇策略［2］。

優點：通過引入先進的列選擇策略、基于貪心策略的啟發式算法等方法來改進列選擇策略，可以提高算法的精度和效率。

缺點：列選擇策略的改進需要對問題本身有深入的理解和分析，可能需要大量的實驗和測試，才能找到合適的列選擇策略。

2.3 優化列集合的管理

列集合是列生成算法中的關鍵數據結構，對算法的效率和精度有著重要的影響。可以通過優化列集合的更新策略、管理策略、排序策略等方法來提高算法的效率和精度。

優點：通過優化列集合的更新策略、管理策略、排序策略等方法來提高算法的效率和精度，可以改善列生成算法的求解速度和質量。

缺點：列集合管理的優化可能會增加算法的復雜度，導致運算時間和空間開銷增加。并且需要仔細選擇優化策略，以避免出現不穩定的情況。

2.4 結合其他方法

列生成算法可以結合其他方法來進一步提高算法的效率和精度，如將列生成算法與分支定界算法、混合整數規劃算法、模擬退火算法等方法相結合，可以得到更加高效和精確的求解方法。

優點：通過結合其他方法，如將列生成算法與分支定界算法、混合整數規劃算法、模擬退火算法等方法相結合，可以得到更加高效和精確的求解方法。

缺點：不同方法的組合需要進行合適的調整和實驗，才能找到最優的求解策略。而且，不同方法的結合可能會導致算法的復雜度增加，導致運算時間和空間開銷增加。

總體來說，不同的思路和方法在不同的問題和情況下具有不同的優缺點。為了提高算法的效率和精度，需要根據具體問題的特點和求解需求來選擇合適的改進方法，并對改進方法進行適當的組合和調整，同時進行大量的實驗和測試，以驗證改進方法的有效性和性能。

3 基于機器學習的列生成算法改進策略

在用列生成求解時，一些大規模模型容易出現高度簡并，導致收斂速度較慢。對于這些問題，可以在每次迭代中生成許多列并添加到受限的主問題中。然而，這樣做只會增加處理簡并的難度，從而產生反效果。在過去的幾年里，研究人員對使用機器學習算法來解決組合優化問題或加速現有的優化方法越來越感興趣。Bengio等［3］對組合優化的機器學習技術進行了很好的概述。

3.1 列生成算法的基本模型

在每次列生成迭代中，優化受限的主問題并求解定價問題后，得到一組列β。目標是選擇要添加到受限的主問題的列βs?β的子集。這種列的選擇可以被認為是一個二元分類問題，其中我們嘗試將每個生成的列分為兩個類y∈{ 0,1} ，即如果要選擇列，則為1；否則為0。設l為列生成迭代號，αl為迭代開始時受限的主問題中出現的列集l，βl為此迭代中生成的列。對于每一列p∈βl，我們定義了一個決策變量yp，如果選擇列p則取值1；否則取0。由此得到用于列分類任務的混合整數線性規劃模型如下：

其中：p是變量θp的指數集；cp∈R,ap∈Rm分別為θp的代價系數向量和約束系數向量；b∈Rm是約束條件（2）的右邊向量。注：這些約束條件中的一些或全部也可以是不等式。如果沒有yp變量和約束（4）和（5），模型（1）～（5）將恰好是迭代l+ 1 時的受限的主問題。假設足夠小，這些變量和約束只考慮最小化所選列的集合。這些列對應于yp= 1的列，即yp列與正值θp變量相關（約束（8））。因此，迭代l時受限的主問題中要添加的列子集為

3.2 圖神經網絡概述

圖神經網絡（GNNs）為圖結構化數據的學習提供了一個有效的框架。它們可以用于節點分類、鏈接預測、圖預測、文檔分類甚至組合優化等任務。它們最初由Gori 等［4］提出，并由Scarselli 等［5］進一步發展。GNN 的目標是以迭代的方式聚合來自鄰居節點的信息來學習節點表示。然后，使用節點表示形式為節點分類任務生成輸出標簽。

GNN 概述：給定一個圖G=(V,E)，其中V是節點的集合，E是邊的集合，每個節點v∈V由其特征向量xv來表示。目標是通過聚合來自鄰居節點的信息，迭代地更新節點的表示。設h(k)v是節點v∈V在迭代k處的表示向量k=0,1,…,K。設N(v)為v∈V作為相鄰節點集合，如圖2 所示，通過聚合鄰居節點的表示來迭代更新表示向量。在迭代k＞0 時，該聚合函數（aggr）首先用于計算每個節點v∈V的聚合信息向量a(k)v:

圖2 圖神經網絡

h(v0)=xv,?(k)是一個學習函數。函數aggr對于節點順序的排列應該是不變的。然后，使用一個表示comb的函數，我們將聚合的信息與給定節點的當前狀態結合起來，以獲得更新的節點表示向量:

其中φ(k)是另一個學習函數。

隨著迭代的進行，節點從較遠的節點收集信息。在最后的迭代K中，節點v∈V的表示h(K)v可以用來預測它的標簽，記為fv，通過應用最終習得的變換，記為out，即:

學習的函數?(k)，φ(k)，out通過使用多層感知器前饋神經網絡實現。

3.3 算法模型

上述內容中存在明顯的架構是用一個節點表示每一列，如果兩個節點對應的列至少有一個共同的約束，就用一條邊連接它們。但是，在這種情況下，邊的數量會非常大，模型中很難包含對偶值信息。另一種架構使用具有兩種節點類型的二部圖：列節點V和約束節點C。如果列v對約束c有貢獻，則在節點v∈V和節點c∈C之間存在邊(v,c)。這種表示的優點是可以將特征向量附加到約束節點上，這將允許我們輕松地包含雙重信息。

因為有兩種節點類型，所以每次迭代都分兩個階段進行，且在一次迭代之后，每個列節點都包含一些關于對相同約束有貢獻的其他列的信息。然而，通過執行額外的迭代可以傳遞更好的信息。

列表示h(vK),v∈V，然后用于預測標簽yv∈{ 0,1} 。以下為算法示例：

4 結語

本文通過對列生成算法進行探索，針對列生成算法求解子問題的速度，進行相應的分析研究并提出對應的改進策略，同時通過相應的實驗驗證了本文提出內容的可行性。本文提出的改進策略對于提高列生成算法的計算速度具有很大的增益，也為各個應用領域運用列生成算法提供了一些改進思路。