最高3倍無損提速，用數(shù)學(xué)規(guī)劃求解器尋找最優(yōu)解更快了！

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

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

數(shù)學(xué)規(guī)劃求解器因其重要性和通用性，被譽(yù)為運籌優(yōu)化領(lǐng)域的“光刻機(jī)”。

其中，MILP求解器是數(shù)學(xué)規(guī)劃求解器的關(guān)鍵組件，可建模大量實際應(yīng)用。

打個比方，MILP求解器就像一個智能助手，能通過數(shù)學(xué)方法和算法幫助尋找最優(yōu)解。

在更復(fù)雜的情況下，比如物流調(diào)度、生產(chǎn)計劃、金融投資等領(lǐng)域，MILP求解器可以幫助決策者在復(fù)雜約束條件下做出最優(yōu)選擇。

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

背景與問題介紹

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

其中割平面選擇（cut selection）目標(biāo)是：

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

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

• (P1) 應(yīng)優(yōu)先選哪些割平面
• (P2) 應(yīng)選擇多少割平面

研究人員認(rèn)為，盡管許多現(xiàn)代MILP求解器通過手動設(shè)計的啟發(fā)式方法來處理 (P1) 和 (P2)，但機(jī)器學(xué)習(xí)方法有潛力學(xué)習(xí)更有效的啟發(fā)式方法。

然而，許多現(xiàn)有的學(xué)習(xí)類方法側(cè)重于學(xué)習(xí)應(yīng)該優(yōu)先選擇哪些割平面，而忽略了學(xué)習(xí)應(yīng)該選擇多少割平面。

此外，研究人員從大量的實驗結(jié)果中發(fā)現(xiàn)又一子問題對求解MILP的效率有重大影響。

• (P3) 應(yīng)該優(yōu)先選擇哪種割平面順序

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

下面具體展開。

割平面介紹

混合整數(shù)線性規(guī)劃（MILP）是一種可廣泛應(yīng)用于多種實際應(yīng)用領(lǐng)域的通用優(yōu)化模型，例如供應(yīng)鏈管理、排產(chǎn)規(guī)劃、規(guī)劃調(diào)度、工廠選址、裝箱問題等。

標(biāo)準(zhǔn)的MILP具有以下形式：

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

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

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

割平面選擇介紹

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

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

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

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

然而，添加過多的割平面可能會導(dǎo)致問題約束過多，增加問題求解計算開銷并出現(xiàn)數(shù)值不穩(wěn)定問題。

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

啟發(fā)實驗：割平面添加順序

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

它們都在選擇了一批割平面后，以隨機(jī)順序?qū)⑦x擇的割平面添加到MILP問題中。

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

方法介紹

據(jù)介紹，在割平面選擇任務(wù)中，應(yīng)該選擇的最優(yōu)子集是不可事先獲取的。

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

因此，團(tuán)隊利用強(qiáng)化學(xué)習(xí)（Reinforcement Learning, RL）范式來試錯學(xué)習(xí)割平面選擇策略。

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

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

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

最后，推導(dǎo)可高效訓(xùn)練HEM++ 的分層近端策略優(yōu)化（hierarchical proximal policy optimization, HPPO）方法。

下面一一展開。

問題建模：序列決策建模

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

這里??_????表示當(dāng)前LP松弛的數(shù)學(xué)模型，??表示候選割平面的集合，表示LP松弛的最優(yōu)解。

為了編碼狀態(tài)信息，研究人員根據(jù)（??_????，??，）的信息為每個待選割平面設(shè)計13個特征。

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

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

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

轉(zhuǎn)移函數(shù)：轉(zhuǎn)移函數(shù)給定當(dāng)前狀態(tài)s和采取的動作??，輸出下一狀態(tài)s^’。割平面選擇任務(wù)中轉(zhuǎn)移函數(shù)隱式地由求解器提供。

更多建模細(xì)節(jié)請見原文第5和第6章節(jié)。

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

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

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

首先，上層策略通過預(yù)測恰當(dāng)?shù)谋壤齺韺W(xué)習(xí)應(yīng)該選擇的cuts的數(shù)量。

假設(shè)狀態(tài)長度為N，預(yù)測比率為k，那么預(yù)測應(yīng)該選擇的cut數(shù)為，其中表示向下取整函數(shù)。

研究人員定義。

其次，下層策略學(xué)習(xí)選擇給定大小的有序子集。

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

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

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

訓(xùn)練方法：分層近端策略優(yōu)化方法

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

最終推導(dǎo)出HPPO，當(dāng)前策略和舊策略的概率比表示如下：

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

進(jìn)一步地，給定優(yōu)勢函數(shù)的估計器，優(yōu)化目標(biāo)為：

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

具體細(xì)節(jié)請見原文第6章節(jié)。

實驗介紹

實驗共有五個主要部分。

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

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

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

如圖所示，在多個開源數(shù)據(jù)集和工業(yè)數(shù)據(jù)集上對比了HEM++和最先進(jìn)開源求解器SCIP基線。

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

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

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

天籌AI求解器曾獲世界人工智能大會最高獎“卓越人工智能引領(lǐng)者” SAIL獎，并在國際權(quán)威數(shù)學(xué)優(yōu)化求解器榜單中的5項重量級榜單登上榜首。

相關(guān)算法整合入華為MindSpore ModelZoo模型庫，助力國產(chǎn)開源生態(tài)。

華為MindSpore是一個全場景深度學(xué)習(xí)框架，目標(biāo)是實現(xiàn)易開發(fā)、高效執(zhí)行、全場景覆蓋三大目標(biāo)。

更多細(xì)節(jié)歡迎查閱原論文。

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

華為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
數(shù)據(jù)地址：https://drive.google.com/drive/folders/1LXLZ8vq3L7v00XH-Tx3U6hiTJ79sCzxY
會議版本論文（ICLR 2023）：https://arxiv.org/abs/2302.00244