AI驅動運籌優化「光刻機」！中科大等提出分層序列模型，大幅提升數學規劃解法效率

數學規劃解算器因其重要性和通用性，被譽為運籌最佳化領域的「光刻機」。

其中，混合整數線性規劃(Mixed-Integer Linear Programming, MILP) 是數學規劃求解器的關鍵組件，可建模大量實際應用，如工業排產，物流調度，晶片設計，路徑規劃，金融投資等重大領域。

近期，中科大MIRA Lab 王傑教授團隊和華為諾亞方舟實驗室聯合提出分層序列模型（Hierarchical Sequence Model, HEM），大幅提升混合整數線性規劃求解器求解效率，相關成果發表於ICLR 2023。

目前，演算法已整合入華為 MindSpore ModelZoo 模型庫，相關技術和能力並將於今年內整合入華為天籌（OptVerse）AI求解器。該求解器旨在將運籌學和AI相結合，突破業界運籌優化極限，助力企業量化決策和精細化運營，實現降本增效！

作者表：王治海*，李希君*，王傑**，匡宇飛，袁明軒，曾嘉，張勇東，吳楓

論文連結：https://openreview.net/forum?id=Zob4P9bRNcK

#開源資料集：https://drive.google.com/drive/folders/1LXLZ8vq3L7v00XH-Tx3U6hiTJ79sCzxY?uspsharing

PyTorch 版本開源程式碼：https://github.com/MIRALab-USTC/L2O-HEM-Torch

MindSpore 版本開源程式碼：https://gitee.com/mindspore/models/ tree/master/research/l2o/hem-learning-to-cut

天籌（OptVerse）AI解算器：https://www.huaweicloud.com/product/modelarts/optverse.html

圖1. HEM 與求解器預設策略（Default）求解效率對比，HEM 求解效率最高可提升47.28%

#1 引言

割平面（cutting planes, cuts）對於高效求解混合整數線性規劃問題至關重要。

其中割平面選擇（cut selection）旨在選擇待選割平面的恰當子集以提高求解 MILP 的效率。割平面選擇在很大程度上取決於兩個子問題： （P1）應優先選擇哪些割平面，以及（P2）應選擇多少割平面。

儘管許多現代 MILP 求解器透過手動設計的啟發式方法來處理 (P1) 和 (P2)，但機器學習方法有潛力學習更有效的啟發式方法。

然而，許多現有的學習類方法著重於學習應該優先選擇哪些割平面，而忽略了學習應該選擇多少割平面。此外，我們從大量的實驗結果中觀察到又一子問題，即（P3）應該優先選擇哪種割平面順序，對求解 MILP 的效率也有重大影響。

為了回應這些挑戰，我們提出了一個新穎的分層序列模型（Hierarchical Sequence Model, HEM），並透過強化學習框架來學習割平面選擇策略。

據我們所知，HEM 是第一個可同時處理（P1），（P2）和（P3）的學習類別方法。實驗表明，在人工生成和大規模真實世界 MILP 資料集上，與人工設計和學習類基線相比，HEM 大幅提高了求解 MILP 的效率。

2 背景與問題介紹

2.1 割平面（cutting planes, cuts）介紹

混合整數線性規劃（Mixed-Integer Linear Programming, MILP）是一種可廣泛應用於多種實際應用領域的一般最佳化模型，例如供應鏈管理[1]、排產規劃[2]、規劃排程[3]、工廠選址[4]、裝箱問題[5]等。

標準的MILP具有以下形式：

#（1）

給定問題（ 1），我們丟棄其所有整數約束，可得到線性規劃鬆弛（linear programming relaxation, LPR）問題，它的形式為：

（2）

由於問題（2）擴展了問題（1）的可行集，因此我們可有，即LPR 問題的最優值是原MILP 問題的下界。

給定（2）中的LPR 問題，割平面（cutting planes, cuts）是一類合法線性不等式，這些不等式在添加到線性規劃鬆弛問題中後，可收縮LPR 問題中的可行域空間，且不移除任何原MILP 問題中的整數可行解。

2.2 割平面選擇（cut selection）介紹

MILP 求解器在求解 MILP 問題過程中可產生大量的割平面，且會在連續的回合中不斷向原問題中添加割平面。

具體而言，每一回合中包含五個步驟：

（1）求解目前的LPR 問題；

（2）產生一系列待選割平面;

（3）從待選割平面中選擇一個合適的子集；

（4）將選擇的子集加到(1) 中的LPR 問題，以獲得一個新的LPR 問題；

（5）循環重複，基於新的LPR 問題，進入下一個回合。

將所有產生的割平面添加到 LPR 問題中可最大程度地收縮該問題的可行域空間，以最大程度提高下界。

然而，增加過多的割平面可能會導致問題約束過多，增加問題求解計算開銷並出現數值不穩定問題 [6,7]。

因此，研究者提出了割平面選擇（cut selection），割平面選擇旨在選擇候選割平面的適當子集，以盡可能提升 MILP 問題求解效率。割平面選擇對於提高解決混合整數線性規劃問題的效率至關重要 [8,9,10]。

2.3 啟發實驗－割平面新增順序

我們設計了兩種割平面選擇啟發式演算法，分別為 RandomAll 和 RandomNV（詳見原論文第3章）。

它們都在選擇了一批割平面後，以隨機順序將所選的割平面加入 MILP 問題中。如圖2結果顯示，選定同一批割平面的情況下，以不同的順序加入這些選定割平面對求解器求解效率有極大的影響（詳細結果分析見原論文第3章節）。

圖2. 每一個柱子代表在求解器中，選定相同的一批割平面，以10輪不同的順序加入這些選定割平面，求解器最終的求解效率的平均值，柱子中的標準差線代表不同順序下求解效率的標準差。標準差越大，代表順序對求解器求解效率影響越大。

3 方法介紹

在割平面選擇任務中，應該選擇的最優子集是不可事先取得的。

不過，我們可以使用求解器評估所選任意子集的質量，並以此評估作為學習演算法的回饋。

因此，我們利用強化學習（Reinforcement Learning, RL）範式來試誤學習割平面選擇策略。

在本節中，我們詳細闡述了我們提出的 RL 框架。

首先，我們將割平面選擇任務建模為馬爾科夫決策過程（Markov Decision Process, MDP）；然後，我們詳細介紹我們提出的分層序列模型（hierarchical sequence model, HEM）；最後，我們推導出可高效訓練HEM 的分層策略梯度。我們整體的 RL 框架圖如圖3所示。

圖3. 我們所提出的整體 RL 框架圖。我們將 MILP 求解器建模為環境，將 HEM 模型建模為智慧體。我們透過智能體和環境不斷互動採集訓練數據，並使用分層策略梯度訓練 HEM 模型。

3.1 問題建模

狀態空間：由於目前的 LP 鬆弛和產生的待選 cuts 包含割平面選擇的核心訊息，我們透過定義狀態。這裡  表示目前 LP 鬆弛的數學模型， 表示候選割平面的集合，表示 LP 鬆弛的最適解。為了編碼狀態訊息，我們根據的訊息為每個待選割平面設計13個特徵。也就是說，我們透過一個13維特徵向量來表示狀態 s。具體細節請見原文第4章節。

動作空間：為了同時考慮所選 cut 的比例和順序，我們以候選割平面集合的所有有序子集定義動作空間。

獎勵函數：為了評估添加 cut 對求解 MILP 的影響，我們可透過求解時間，原始對偶間隙積分（primal-dual gap integral），對偶界提升（dual bound improvement）。具體細節請見原文第4章節。

轉移函數：轉移函數給定目前狀態和採取的動作，輸出下一狀態。割平面選擇任務中轉移函數隱式地由求解器提供。

更多建模細節請見原文第4章節。

3.2 策略模型：分層序列模型

如圖3所示，我們將MILP 求解器建模為環境，將HEM 建模為智能體，以下詳細介紹所提出的HEM 模型。為了方便閱讀，我們簡化方法動機，聚焦講清楚方法實現，歡迎有興趣的讀者參考原論文第4章節，了解相關細節。

如圖3 Agent 模組所示，HEM 由上下層策略模型組成。上下層模式分別學習上層策略（policy）  與下層policy 。

首先，上層策略透過預測適當的比例來學習應該選擇的 cuts 的數量。假設狀態長度為，預測比率為，那麼預測應該選擇的 cut 數為

，其中表示向下取整函數。我們定義。

其次，下層策略學習選擇給定大小的有序子集。下層策略可以定義，其中表示給定狀態S和比例K的動作空間上的機率分佈。具體來說，我們將下層策略建模為一個序列到序列模型（sequence to sequence model, sequence model）。

最後，透過全機率定律推導出cut 選擇策略，即

3.3 訓練方法：分層策略梯度

給定最佳化目標函數

圖 4.分層策略梯度。我們以此隨機梯度下降的方式優化 HEM 模型。

4 實驗介紹

我們的實驗有五個主要部分：

實驗1. 在3個人工產生的MILP問題和來自不同應用領域的6個具有在挑戰性的MILP問題基準上評估我們的方法。

實驗2. 進行精心設計的消融實驗，以提供對HEM的深入洞察。

實驗3. 測試 HEM 針對問題規模的泛化效能。

實驗4. 視覺化我們的方法與基準所選擇的割平面特性。

實驗5. 將我們的方法部署到華為實際的排產規劃問題中，驗證 HEM 的優越性。

我們在這篇文章中只介紹實驗1，更多實驗結果，請參考原論文第5章節。請注意，我們論文中報告的所有實驗結果都是基於 PyTorch 版本程式碼訓練所得到的結果。

實驗1結果如表1所示，我們在9個開源資料集上比較了 HEM 和6個基準的比較結果。實驗結果顯示，HEM 可平均提升約 20% 求解效率。

圖5. 圖5.對easy、medium 和 hard 資料集的策略評估。最優性能我們用粗體字標出。以m表示限制條件的平均數量，n表示變數的平均數量。我們展示了求解時間和primal-dual gap 積分的算術平均值（標準差）。

以上是AI驅動運籌優化「光刻機」！中科大等提出分層序列模型，大幅提升數學規劃解法效率的詳細內容。更多資訊請關注PHP中文網其他相關文章！