最高3倍無損提速，用數學規劃求解器尋找最優解更快了！

近日，中科大王杰教授團隊（MIRA Lab）和華為諾亞方舟實驗室（Huawei Noah’s Ark Lab）聯合提出了分層序列/集合模型，并開發了基于該分層模型的智能決策訓練方法。

顯著提升混合整數線性規劃（MILP）求解器求解效率，取得最高3倍無損提速。

數學規劃求解器因其重要性和通用性，被譽為運籌優化領域的“光刻機”。

其中，MILP求解器是數學規劃求解器的關鍵組件，可建模大量實際應用。

打個比方，MILP求解器就像一個智能助手，能通過數學方法和算法幫助尋找最優解。

在更復雜的情況下，比如物流調度、生產計劃、金融投資等領域，MILP求解器可以幫助決策者在復雜約束條件下做出最優選擇。

目前論文發表在人工智能頂級期刊IEEE TPAMI 2024。

背景與問題介紹

割平面（cutting planes, cuts）在加速求解混合整數線性規劃（MILP）問題中發揮著至關重要的作用。自上世紀50年代以來，割平面法作為求解MILP問題的強大工具，已成為學術界和工業界廣泛研究的重點。經過多年的實踐驗證，割平面法已被公認為快速求解MILP問題的關鍵技術。

其中割平面選擇（cut selection）目標是：

選擇待選割平面的恰當子集以無損提高求解MILP的效率。

據介紹，割平面選擇在很大程度上取決于兩個子問題：

• (P1) 應優先選哪些割平面
• (P2) 應選擇多少割平面

研究人員認為，盡管許多現代MILP求解器通過手動設計的啟發式方法來處理 (P1) 和 (P2)，但機器學習方法有潛力學習更有效的啟發式方法。

然而，許多現有的學習類方法側重于學習應該優先選擇哪些割平面，而忽略了學習應該選擇多少割平面。

此外，研究人員從大量的實驗結果中發現又一子問題對求解MILP的效率有重大影響。

• (P3) 應該優先選擇哪種割平面順序

針對上述挑戰，研究人員提出了一種新的分層序列/集合模型(Hierarchical Sequence/Set Model,HEM++)，并構建了基于該模型的強化學習框架來學習割平面選擇策略。

下面具體展開。

割平面介紹

混合整數線性規劃（MILP）是一種可廣泛應用于多種實際應用領域的通用優化模型，例如供應鏈管理、排產規劃、規劃調度、工廠選址、裝箱問題等。

標準的MILP具有以下形式：

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

由于松弛問題擴展了原始問題的可行域，因此可有，即LPR問題的最優值是原MILP問題的下界。

給定松弛問題，割平面是一類合法線性不等式，這些不等式在添加到線性規劃松弛問題中后，可收縮LPR問題中的可行域空間，且不去除任何原MILP問題中任何整數可行解。

割平面選擇介紹

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

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

• (1) 求解當前的LPR問題；
• (2) 生成一系列待選割平面；
• (3) 從待選割平面中選擇一個合適的子集；
• (4) 將選擇的子集添加到(1)中的LPR問題，以得到一個新的LPR問題；
• (5) 循環重復，基于新的LPR問題，進入下一個回合。

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

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

因此，研究者們提出了割平面選擇，它的目標是選擇候選割平面的適當子集，以盡可能提升MILP問題求解效率。

啟發實驗：割平面添加順序

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

它們都在選擇了一批割平面后，以隨機順序將選擇的割平面添加到MILP問題中。

結果顯示，選定同一批割平面的情況下，以不同的順序添加這些選定割平面對求解器求解效率有極大的影響（詳細結果分析見原論文第3章節）。

方法介紹

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

不過，研究人員可以使用求解器評估所選任意子集的質量，并以此評估作為學習算法的反饋。

因此，團隊利用強化學習（Reinforcement Learning, RL）范式來試錯學習割平面選擇策略。

研究人員詳細闡述了提出的RL框架。（整體的RL框架圖如圖2所示）

首先，他們將割平面選擇任務建模為馬爾科夫決策過程（Markov Decision Process, MDP）。

然后，詳細介紹了提出的分層序列/集合模型HEM++。

最后，推導可高效訓練HEM++ 的分層近端策略優化（hierarchical proximal policy optimization, HPPO）方法。

下面一一展開。

問題建模：序列決策建模

狀態空間：由于當前的LP松弛和生成的待選cuts包含割平面選擇的核心信息，研究人員通過（??_????，??，）定義狀態s。

這里??_????表示當前LP松弛的數學模型，??表示候選割平面的集合，表示LP松弛的最優解。

為了編碼狀態信息，研究人員根據（??_????，??，）的信息為每個待選割平面設計13個特征。

也就是說，通過一個13維特征向量來表示狀態s。（具體細節請見原文第5和第6章節）

動作空間：為了同時考慮所選cut的比例和順序，研究人員以候選割平面集合的所有有序子集構成的集合??和選擇cut的比例空間[0,1]的直積，即動作空間??^HEM++=?? x [0,1]。

獎勵函數：為了評估添加cut對求解MILP的影響，可通過求解時間，原始對偶間隙積分（primaldual gap integral），對偶界提升（dual bound improvement）。

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

更多建模細節請見原文第5和第6章節。

策略模型：分層序列/集合模型

如圖所示，研究人員將MILP求解器建模為環境，將HEM++建模為智能體，下面詳細介紹所提出的HEM++模型。

可以看出，HEM++由上下層策略模型組成。上下層模型分別學習上層策略（policy）π^?和下層（policy）π^??。

首先，上層策略通過預測恰當的比例來學習應該選擇的cuts的數量。

假設狀態長度為N，預測比率為k，那么預測應該選擇的cut數為，其中表示向下取整函數。

研究人員定義。

其次，下層策略學習選擇給定大小的有序子集。

下層策略可以定義 S x [0，1] → P（??），其中表示給定狀態s和比例k的動作空間上的概率分布。

具體來說，研究人員將下層策略建模為一個序列到序列或者集合到序列模型（sequence/set to sequence model, sequence/set model）。

最后，通過概率乘法定理可得分層cut選擇策略，即：。

訓練方法：分層近端策略優化方法

研究人員用[0，1] x ?? 表示動作空間，用表示分層割平面策略。

最終推導出HPPO，當前策略和舊策略的概率比表示如下：

為了避免過大的策略更新，研究人員對此概率比進行裁剪得到r^clip。

進一步地，給定優勢函數的估計器，優化目標為：

最后，分層策略梯度如下：

具體細節請見原文第6章節。

實驗介紹

實驗共有五個主要部分。

• 實驗1. 在3個人工生成的MILP問題和來自不同應用領域的6個具有挑戰性的MILP問題基準上評估新方法；
• 實驗2. 進行消融實驗，以提供對HEM++的深入洞察；
• 實驗3. 測試HEM++針對問題規模的泛化性能；
• 實驗4. 可視化新方法與基線所選擇的割平面特點；
• 實驗5. 將新方法部署到華為實際的排產規劃問題中，驗證HEM++的優越性；

下面僅簡單介紹下實驗1，更多實驗結果，可參見原論文第8章節。

研究人員提醒道，論文中匯報的所有實驗結果都是基于PyTorch版本代碼訓練得到的結果。

如圖所示，在多個開源數據集和工業數據集上對比了HEM++和最先進開源求解器SCIP基線。

實驗結果顯示，HEM++可在保持求解精度不變的情況下，大幅提升求解效率。

據團隊介紹，相關技術和能力整合入華為天籌（OptVerse）AI求解器，助力提升天籌AI求解器競爭力，成為其首批關鍵AI特性。

天籌AI求解器將運籌學和AI相結合，針對線性和整數模型尋找最優解，以通用形式描述問題，高效計算最優方案，助力企業量化決策和精細化運營。

天籌AI求解器曾獲世界人工智能大會最高獎“卓越人工智能引領者” SAIL獎，并在國際權威數學優化求解器榜單中的5項重量級榜單登上榜首。

相關算法整合入華為MindSpore ModelZoo模型庫，助力國產開源生態。

華為MindSpore是一個全場景深度學習框架，目標是實現易開發、高效執行、全場景覆蓋三大目標。

更多細節歡迎查閱原論文。

本論文作者王治海是中國科學技術大學2020級碩博連讀生，師從王杰教授，主要研究方向為強化學習與學習優化理論及方法，人工智能驅動的芯片設計等。他曾以第一作者在TPAMI、ICML、ICLR、AAAI等頂級期刊與會議上發表論文六篇，一篇入選ICML亮點論文（前3.5%），曾獲華為優秀實習生（5/400+）、國家獎學金等榮譽。

華為MindSpore ModelZoo模型庫：https://gitee.com/mindspore/models/tree/master/research/l2o/hem-learning-to-cut

論文地址：https://ieeexplore.ieee.org/document/10607926
代碼地址：https://github.com/MIRALab-USTC/L2O-HEM-Torch
數據地址：https://drive.google.com/drive/folders/1LXLZ8vq3L7v00XH-Tx3U6hiTJ79sCzxY
會議版本論文（ICLR 2023）：https://arxiv.org/abs/2302.00244