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

其中，混合整數(shù)線(xiàn)性規(guī)劃 (Mixed-Integer Linear Programming, MILP) 是數(shù)學(xué)規(guī)劃求解器的關(guān)鍵組件，可建模大量實(shí)際應(yīng)用，如工業(yè)排產(chǎn)，物流調(diào)度，芯片設(shè)計(jì)，路徑規(guī)劃，金融投資等重大領(lǐng)域。

近期，中科大 MIRA Lab 王杰教授團(tuán)隊(duì)和華為諾亞方舟實(shí)驗(yàn)室聯(lián)合提出分層序列模型（Hierarchical Sequence Model, HEM），大幅提升混合整數(shù)線(xiàn)性規(guī)劃求解器求解效率，相關(guān)成果發(fā)表于ICLR 2023。

目前，算法已整合入華為 MindSpore ModelZoo 模型庫(kù)，相關(guān)技術(shù)和能力并將于今年內(nèi)整合入華為天籌（OptVerse）AI求解器。該求解器旨在將運(yùn)籌學(xué)和AI相結(jié)合，突破業(yè)界運(yùn)籌優(yōu)化極限，助力企業(yè)量化決策和精細(xì)化運(yùn)營(yíng)，實(shí)現(xiàn)降本增效！

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

論文鏈接：https://openreview.net/forum?id=Zob4P9bRNcK

開(kāi)源數(shù)據(jù)集：https://drive.google.com/drive/folders/1LXLZ8vq3L7v00XH-Tx3U6hiTJ79sCzxY?usp=sharing

PyTorch 版本開(kāi)源代碼：https://github.com/MIRALab-USTC/L2O-HEM-Torch

MindSpore 版本開(kāi)源代碼：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 與求解器默認(rèn)策略（Default）求解效率對(duì)比，HEM 求解效率最高可提升 47.28%

1 引言

割平面（cutting planes, cuts）對(duì)于高效求解混合整數(shù)線(xiàn)性規(guī)劃問(wèn)題至關(guān)重要。

其中割平面選擇（cut selection）旨在選擇待選割平面的恰當(dāng)子集以提高求解 MILP 的效率。割平面選擇在很大程度上取決于兩個(gè)子問(wèn)題： （P1）應(yīng)優(yōu)先選哪些割平面，以及（P2）應(yīng)選擇多少割平面。

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

然而，許多現(xiàn)有的學(xué)習(xí)類(lèi)方法側(cè)重于學(xué)習(xí)應(yīng)該優(yōu)先選擇哪些割平面，而忽略了學(xué)習(xí)應(yīng)該選擇多少割平面。此外，我們從大量的實(shí)驗(yàn)結(jié)果中觀(guān)察到又一子問(wèn)題，即（P3）應(yīng)該優(yōu)先選擇哪種割平面順序，對(duì)求解 MILP 的效率也有重大影響。

為了應(yīng)對(duì)這些挑戰(zhàn)，我們提出了一種新穎的分層序列模型（Hierarchical Sequence Model, HEM），并通過(guò)強(qiáng)化學(xué)習(xí)框架來(lái)學(xué)習(xí)割平面選擇策略。

據(jù)我們所知，HEM 是首個(gè)可同時(shí)處理（P1），（P2）和（P3）的學(xué)習(xí)類(lèi)方法。實(shí)驗(yàn)表明，在人工生成和大規(guī)模真實(shí)世界 MILP 數(shù)據(jù)集上，與人工設(shè)計(jì)和學(xué)習(xí)類(lèi)基線(xiàn)相比，HEM 大幅度提高了求解 MILP 的效率。

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

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

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

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

（1）

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

（2）

由于問(wèn)題（2）擴(kuò)展了問(wèn)題（1）的可行集，因此我們可有，即 LPR 問(wèn)題的最優(yōu)值是原 MILP 問(wèn)題的下界。

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

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

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)題 [6,7]。

因此，研究者們提出了割平面選擇（cut selection），割平面選擇旨在選擇候選割平面的適當(dāng)子集，以盡可能提升 MILP 問(wèn)題求解效率。割平面選擇對(duì)于提高解決混合整數(shù)線(xiàn)性規(guī)劃問(wèn)題的效率至關(guān)重要 [8,9,10]。

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

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

它們都在選擇了一批割平面后，以隨機(jī)順序?qū)⑦x擇的割平面添加到 MILP 問(wèn)題中。如圖2結(jié)果顯示，選定同一批割平面的情況下，以不同的順序添加這些選定割平面對(duì)求解器求解效率有極大的影響（詳細(xì)結(jié)果分析見(jiàn)原論文第3章節(jié)）。

圖2. 每一個(gè)柱子代表在求解器中，選定相同的一批割平面，以10輪不同的順序添加這些選定割平面，求解器最終的求解效率的均值，柱子中的標(biāo)準(zhǔn)差線(xiàn)代表不同順序下求解效率的標(biāo)準(zhǔn)差。標(biāo)準(zhǔn)差越大，代表順序?qū)η蠼馄髑蠼庑视绊懺酱蟆?/p>

3 方法介紹

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

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

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

在本節(jié)中，我們?cè)敿?xì)闡述了我們提出的 RL 框架。

首先，我們將割平面選擇任務(wù)建模為馬爾科夫決策過(guò)程（Markov Decision Process, MDP）；然后，我們?cè)敿?xì)介紹我們提出的分層序列模型（hierarchical sequence model, HEM）；最后，我們推導(dǎo)可高效訓(xùn)練 HEM 的分層策略梯度。我們整體的 RL 框架圖如圖3所示。

圖3. 我們所提出的整體 RL 框架圖。我們將 MILP 求解器建模為環(huán)境，將 HEM 模型建模為智能體。我們通過(guò)智能體和環(huán)境不斷交互采集訓(xùn)練數(shù)據(jù)，并使用分層策略梯度訓(xùn)練 HEM 模型。

3.1 問(wèn)題建模

狀態(tài)空間：由于當(dāng)前的 LP 松弛和生成的待選 cuts 包含割平面選擇的核心信息，我們通過(guò)定義狀態(tài)。這里  表示當(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)原文第4章節(jié)。

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

獎(jiǎng)勵(lì)函數(shù)：為了評(píng)估添加 cut 對(duì)求解 MILP 的影響，我們可通過(guò)求解時(shí)間，原始對(duì)偶間隙積分（primal-dual gap integral），對(duì)偶界提升（dual bound improvement）。具體細(xì)節(jié)請(qǐng)見(jiàn)原文第4章節(jié)。

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

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

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

如圖3所示，我們將 MILP 求解器建模為環(huán)境，將 HEM 建模為智能體，下面詳細(xì)介紹所提出的 HEM 模型。為了方便閱讀，我們簡(jiǎn)化方法動(dòng)機(jī)，聚焦于講清楚方法實(shí)現(xiàn)，歡迎感興趣的讀者參見(jiàn)原論文第4章節(jié)，了解相關(guān)細(xì)節(jié)。

如圖3中 Agent 模塊所示，HEM 由上下層策略模型組成。上下層模型分別學(xué)習(xí)上層策略（policy）  和下層policy 。

首先，上層策略通過(guò)預(yù)測(cè)恰當(dāng)?shù)谋壤齺?lái)學(xué)習(xí)應(yīng)該選擇的 cuts 的數(shù)量。假設(shè)狀態(tài)長(zhǎng)度為，預(yù)測(cè)比率為，那么預(yù)測(cè)應(yīng)該選擇的 cut 數(shù)為

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

其次，下層策略學(xué)習(xí)選擇給定大小的有序子集。下層策略可以定義，其中表示給定狀態(tài)S和比例K的動(dòng)作空間上的概率分布。具體來(lái)說(shuō)，我們將下層策略建模為一個(gè)序列到序列模型（sequence to sequence model, sequence model）。

最后，通過(guò)全概率定律推導(dǎo)出 cut 選擇策略，即

3.3 訓(xùn)練方法：分層策略梯度

給定優(yōu)化目標(biāo)函數(shù)

圖4. 分層策略梯度。我們以此隨機(jī)梯度下降的方式優(yōu)化 HEM 模型。

4 實(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è)計(jì)的消融實(shí)驗(yàn)，以提供對(duì)HEM的深入洞察。

實(shí)驗(yàn)3. 測(cè)試 HEM 針對(duì)問(wèn)題規(guī)模的泛化性能。

實(shí)驗(yàn)4. 可視化我們的方法與基線(xiàn)所選擇的割平面特點(diǎn)。

實(shí)驗(yàn)5. 將我們的方法部署到華為實(shí)際的排產(chǎn)規(guī)劃問(wèn)題中，驗(yàn)證 HEM 的優(yōu)越性。

我們?cè)诖宋恼轮兄唤榻B實(shí)驗(yàn)1，更多實(shí)驗(yàn)結(jié)果，請(qǐng)參見(jiàn)原論文第5章節(jié)。請(qǐng)注意，我們論文中匯報(bào)的所有實(shí)驗(yàn)結(jié)果都是基于 PyTorch 版本代碼訓(xùn)練得到的結(jié)果。

實(shí)驗(yàn)1結(jié)果如表1所示，我們?cè)?個(gè)開(kāi)源數(shù)據(jù)集上對(duì)比了 HEM 和6個(gè)基線(xiàn)的對(duì)比結(jié)果。實(shí)驗(yàn)結(jié)果顯示，HEM 可平均提升約 20% 求解效率。

圖5. 對(duì)easy、medium 和 hard 數(shù)據(jù)集的策略評(píng)估。最優(yōu)性能我們用粗體字標(biāo)出。以m表示約束條件的平均數(shù)量，n表示變量的平均數(shù)量。我們展示了求解時(shí)間和primal-dual gap 積分的算術(shù)平均值（標(biāo)準(zhǔn)偏差）。