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

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

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

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

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

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

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

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

背景與問(wèn)題介紹

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

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

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

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

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

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

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

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

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

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

下面具體展開(kāi)。

割平面介紹

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

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

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

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

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

割平面選擇介紹

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

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

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

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

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

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

啟發(fā)實(shí)驗(yàn)：割平面添加順序

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

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

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

方法介紹

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

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

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

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

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

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

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

下面一一展開(kāi)。

問(wèn)題建模：序列決策建模

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

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

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

也就是說(shuō)，通過(guò)一個(gè)13維特征向量來(lái)表示狀態(tài)s。（具體細(xì)節(jié)請(qǐng)見(jiàn)原文第5和第6章節(jié)）

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

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

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

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

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

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

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

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

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

研究人員定義。

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

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

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

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

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

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

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

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

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

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

具體細(xì)節(jié)請(qǐng)見(jiàn)原文第6章節(jié)。

實(shí)驗(yàn)介紹

實(shí)驗(yàn)共有五個(gè)主要部分。

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

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

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

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

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

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

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

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

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

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

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

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

華為MindSpore ModelZoo模型庫(kù)：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
會(huì)議版本論文（ICLR 2023）：https://arxiv.org/abs/2302.00244