[[414820]]

近日，DeepMind 與 Google Research 團(tuán)隊(duì)共同發(fā)布了一項(xiàng)工作，用神經(jīng)網(wǎng)絡(luò)與機(jī)器學(xué)習(xí)方法來解決混合整數(shù)規(guī)劃(MIP)問題!

論文地址：https://arxiv.org/pdf/2012.13349.pdf

在解決現(xiàn)實(shí)中遇到的大規(guī)模混合整數(shù)規(guī)劃(Mixed Integer Programming, MIP)實(shí)例時(shí)，MIP 求解器要借助一系列復(fù)雜的、經(jīng)過數(shù)十年研究而開發(fā)的啟發(fā)式算法，而機(jī)器學(xué)習(xí)可以使用數(shù)據(jù)中實(shí)例之間的共享結(jié)構(gòu)，從數(shù)據(jù)中自動(dòng)構(gòu)建更好的啟發(fā)式算法。

在這篇工作中，他們將機(jī)器學(xué)習(xí)應(yīng)用于 MIP求解器的兩個(gè)關(guān)鍵子任務(wù)，生成了一個(gè)高質(zhì)量的聯(lián)合變量賦值(joint variable assignment)，并縮小了該變量賦值與最優(yōu)賦值之間的目標(biāo)值差距。他們構(gòu)建了兩個(gè)對應(yīng)的、基于神經(jīng)網(wǎng)絡(luò)的組件，即 Neural Diving 與 Neural Branching，使其可用于基本的 MIP 求解器上，比如 SCIP。

其中，Neural Diving 學(xué)習(xí)一個(gè)深度神經(jīng)網(wǎng)絡(luò)，為其整數(shù)變量生成多個(gè)部分賦值，并用 SCIP 來解決由此產(chǎn)生的未賦值變量的較小 MIP，以得到高質(zhì)量的聯(lián)合賦值。而 Neural Branching 學(xué)習(xí)一個(gè)深度神經(jīng)網(wǎng)絡(luò)，在分支定界中進(jìn)行變量選擇決策，以用一棵小樹來縮小目標(biāo)值的差距。這是通過模仿他們所提出的 Full Strong Branching(全強(qiáng)分支)的新變量來實(shí)現(xiàn)。

作者團(tuán)隊(duì)將神經(jīng)網(wǎng)絡(luò)在多個(gè)真實(shí)世界的數(shù)據(jù)集(包括兩個(gè)谷歌生產(chǎn)數(shù)據(jù)集和 MIPLIB)上分別進(jìn)行了訓(xùn)練，以進(jìn)行評估。在所有數(shù)據(jù)集中，大多數(shù)實(shí)例在預(yù)求解后都有 10^3 至 10^6 個(gè)變量和約束，明顯大于以前的學(xué)習(xí)方法。

對比求解器與大時(shí)間限制下原問題與對偶問題在一組留出(hold-out)實(shí)例上的差距平均值，學(xué)習(xí)增強(qiáng)的 SCIP 在3個(gè)具有最大 MIP 的數(shù)據(jù)集(一共有5個(gè)數(shù)據(jù)集)上實(shí)現(xiàn)了 1.5x、2x 和 104x 的更好差距，在第4個(gè)數(shù)據(jù)集上以5x的速度更快實(shí)現(xiàn) 10% 的差距，并在第5個(gè)數(shù)據(jù)集上取得了與 SCIP 不相上下的表現(xiàn)。

該團(tuán)隊(duì)介紹，據(jù)了解，他們的方法是第一個(gè)在大規(guī)模現(xiàn)實(shí)世界應(yīng)用數(shù)據(jù)集和 MIPLIB 上都展示了比 SCIP 有更大進(jìn)步的學(xué)習(xí)方法。

1、概念簡介

1.1 分支定界

常見的解決 MIP 過程是遞歸地構(gòu)建搜索樹，在每個(gè)節(jié)點(diǎn)處分配部分整數(shù)，并使用每個(gè)節(jié)點(diǎn)所收集的信息最終收斂于最佳(或接近最佳)分配。在每一步，我們都必須選擇一個(gè)葉子節(jié)點(diǎn)，從中“分支”。在這個(gè)節(jié)點(diǎn)上，我們可以解決線性規(guī)劃(LP)松弛問題，將在該節(jié)點(diǎn)上的固定變量的范圍限制為它們的指定值。這為我們提供了該節(jié)點(diǎn)中所有子節(jié)點(diǎn)的真實(shí)目標(biāo)值的有效下限。

如果這個(gè)界限大于已知的可行分配，那么我們就可以安全地修剪搜索樹的這一部分，因?yàn)樵摴?jié)點(diǎn)的子樹中不存在原問題的最優(yōu)解。如果我們決定擴(kuò)展這個(gè)節(jié)點(diǎn)，那么我們必須從該節(jié)點(diǎn)的一組未固定變量中選擇一個(gè)變量作為分支。一旦選擇了一個(gè)變量，我們就采取分支步驟，將兩個(gè)子節(jié)點(diǎn)添加到當(dāng)前節(jié)點(diǎn)。一個(gè)節(jié)點(diǎn)有選定變量的域，該域會(huì)被約束為大于或等于其父節(jié)點(diǎn)處的 LP 松弛值的上限。另一個(gè)節(jié)點(diǎn)將所選變量的域約束為小于或等于其 LP 松弛值的下限。樹被更新，過程再次開始。

這個(gè)算法被稱為“分支定界”(branch-and-bound)算法。線性規(guī)劃是這個(gè)過程的主要工作，既可以在每個(gè)節(jié)點(diǎn)上導(dǎo)出對偶邊界，又可以為一些更復(fù)雜的分支啟發(fā)式算法確定分支變量。理論上，搜索樹的大小可以隨著問題的輸入大小呈指數(shù)增長，但在許多情況下，搜索樹可能很小，并且是一個(gè)提出節(jié)點(diǎn)選擇和變量選擇啟發(fā)式算法來使樹盡可能保持小的活躍研究領(lǐng)域。

1.2 原始啟發(fā)式

原始啟發(fā)式是一種嘗試找到可行但不一定最佳的變量賦值的方法。任何此類可行的賦值都提供了 MIP 最佳值的保證上限。在 MIP 求解期間的任何點(diǎn)找到的任何此類邊界都被稱為“原始邊界”。

原始啟發(fā)式可以獨(dú)立于分支定界運(yùn)行，但它們也可以在分支定界樹中運(yùn)行，并嘗試從搜索樹中的給定節(jié)點(diǎn)找到不固定變量的可行賦值。生成較低原始邊界的、更好的原始啟發(fā)式方法允許在分支定界過程中修剪更多的樹。簡單的四舍五入就是原始啟發(fā)式的一個(gè)例子。另一個(gè)例子是潛水(diving)，試圖通過深度優(yōu)先的方式從給定節(jié)點(diǎn)中探索搜索樹來找到可行的解決方案。

1.3 原始-對偶間隙

在運(yùn)行分支定界時(shí)，我們會(huì)跟蹤全局原始邊界(任何可行分配的最小目標(biāo)值)和全局對偶邊界(分支定界樹所有葉子的最小對偶邊界)。我們可以結(jié)合這些來定義次優(yōu)間隙(sub-optimality gap)：

• 間隙=全局原始邊界-全局對偶邊界

構(gòu)造的間隙總是非負(fù)的。如果它為零，那么我們已經(jīng)解決了問題，與原始邊界對應(yīng)的可行點(diǎn)是最優(yōu)的，而對偶邊界是最優(yōu)性的證明。在實(shí)踐中，當(dāng)相對間隙(即以某種方式歸一化)低于某個(gè)依賴于應(yīng)用的數(shù)量時(shí)，我們會(huì)終止分支定界，并生成最佳的已尋原始解決方案作為近似最優(yōu)解決方案。

圖注：用作神經(jīng)網(wǎng)絡(luò)輸入的 MIP 的二部圖表示。n 個(gè)變量的集合 {x1,...,xn} 和 m 個(gè)約束的集合 {δ1,...,δm} 形成了二部圖的兩組節(jié)點(diǎn)。系數(shù)被編碼為節(jié)點(diǎn)和邊的特征。

2、論文介紹

混合整數(shù)規(guī)劃 (MIP) 是 NP-hard 問題中的一類，它的目標(biāo)是在線性約束下將線性目標(biāo)最小化，同時(shí)使部分或全部變量均為整數(shù)值，在容量規(guī)劃、資源分配與裝箱等等現(xiàn)實(shí)場景中得到了廣泛應(yīng)用。

該方向的大量研究與工程投入都集中在了開發(fā)實(shí)用求解器上，比如 SCIP、CPLEX、Gurobi 和 Xpress。這些求解器都是使用復(fù)雜的啟發(fā)式算法來指導(dǎo)求解 MIP 的搜索過程。一個(gè)求解器在特定應(yīng)用上的表現(xiàn)主要是取決于該求解器的啟發(fā)式算法與該應(yīng)用的匹配程度。

在這篇工作中，作者團(tuán)隊(duì)展示了機(jī)器學(xué)習(xí)可用于從 MIP 實(shí)例數(shù)據(jù)集中自動(dòng)構(gòu)建有效的啟發(fā)式算法。當(dāng)一個(gè)應(yīng)用需要解決具有不同問題參數(shù)的同一高級語義問題中的大量實(shí)例時(shí)，機(jī)器學(xué)習(xí)便派上了用場。

這篇工作中，此類“同質(zhì)”數(shù)據(jù)集的例子包括：1)優(yōu)化選擇電網(wǎng)中的發(fā)電廠，以滿足需求(O'Neill 2017)，其中，電網(wǎng)拓?fù)浔３植蛔儯枨蟆⒖稍偕茉窗l(fā)電等則因情況而異;2) 解決谷歌生產(chǎn)系統(tǒng)中的包裝問題，其中，待打包的“物件”(items)和“箱子”(bins)的語義基本保持不變，但它們的尺寸大小會(huì)根據(jù)不同的情況而有所變化。

即使是結(jié)合了許多語義不同的問題的“異構(gòu)”數(shù)據(jù)集，比如 MIPLIB 2017，也可以擁有跨實(shí)例的結(jié)構(gòu)，用于學(xué)習(xí)更好的啟發(fā)式算法。現(xiàn)成的 MIP 求解器無法自動(dòng)構(gòu)建啟發(fā)式算法來利用這種結(jié)構(gòu)。在具有挑戰(zhàn)性的應(yīng)用場景中，用戶可能會(huì)依賴專家來手動(dòng)設(shè)計(jì)此類啟發(fā)式算法，或放棄潛在的大幅性能改進(jìn)。機(jī)器學(xué)習(xí)提供了大幅改進(jìn)的可能性，且無需使用特定應(yīng)用場景的專業(yè)知識(shí)。

這篇工作證明了，機(jī)器學(xué)習(xí)可以構(gòu)建為特定數(shù)據(jù)集定制的啟發(fā)式算法，其性能會(huì)明顯優(yōu)于在 MIP 求解器中所使用過的經(jīng)典方法，包括最先進(jìn)的非商業(yè)求解器 SCIP 7.0.1 。

他們的方法將機(jī)器學(xué)習(xí)應(yīng)用于 MIP 求解器的兩個(gè)關(guān)鍵子任務(wù)：a) 輸出能滿足約束條件的所有變量的賦值(如果存在這樣的賦值);b)證明變量賦值與最優(yōu)賦值之間的目標(biāo)值差距范圍。這兩個(gè)任務(wù)決定了該方法的主要組件，即 Neural Diving 與 Neural Branching(見圖1)。

圖注：我們的方法構(gòu)建了兩個(gè)在 MIP 求解器中使用、基于神經(jīng)網(wǎng)絡(luò)的組件，即 Neural Diving 與 Neural Branching，并將兩者結(jié)合，得到了一個(gè)為特定 MIP 數(shù)據(jù)集量身定做的神經(jīng)求解器(Neural Solver)。

Neural Diving：該組件可找到高質(zhì)量的聯(lián)合變量賦值。它是原始啟發(fā)式算法 (Berthold 2006) 的一個(gè)示例，而原始啟發(fā)式是一類對有效 MIP 求解器十分關(guān)鍵的搜索啟發(fā)式算法 (Berthold 2013)。

作者團(tuán)隊(duì)訓(xùn)練一個(gè)深度神經(jīng)網(wǎng)絡(luò)來生成輸入 MIP 的整數(shù)變量的多個(gè)部分真值(partial assignments)。其余未賦值的變量定義了較小的“sub-MIPs”，它們是用現(xiàn)成的 MIP 求解器(例如 SCIP)求解來完成賦值。如果計(jì)算預(yù)算允許，sub-MIPs 可以并行求解。模型經(jīng)過訓(xùn)練，使用現(xiàn)成求解器離線收集的訓(xùn)練示例，為靈活的、擁有更優(yōu)目標(biāo)值的賦值提供更高的概率。模型是基于所有可用的可行賦值而不是最優(yōu)賦值來進(jìn)行學(xué)習(xí)，且不一定要用到最優(yōu)賦值(因?yàn)槭占某杀究赡芊浅０嘿F)。

Neural Branching：該組件主要用于縮小最好賦值與最優(yōu)賦值的目標(biāo)值之間的差距。

在整數(shù)變量上，MIP 求解器使用了一種樹搜索的形式，即“分支定界”，逐漸收緊邊界并幫助尋找可行的賦值。在給定節(jié)點(diǎn)上，分支變量的選擇是決定搜索效率的關(guān)鍵因素。

他們訓(xùn)練了一個(gè)深度神經(jīng)網(wǎng)絡(luò)策略來模仿專家策略所做出的選擇。模仿目標(biāo)是一個(gè)著名的啟發(fā)式算法，稱為“全強(qiáng)分支”(FSB)，實(shí)踐已證明，F(xiàn)SB 可以生成小型搜索樹。雖然對實(shí)際的 MIP 求解來說，它的計(jì)算成本往往過高，但它仍可以被當(dāng)成一種緩慢且昂貴的一次性計(jì)算，用于離線生成模仿學(xué)習(xí)數(shù)據(jù)。一旦經(jīng)過訓(xùn)練，這個(gè)神經(jīng)網(wǎng)絡(luò)就能夠在測試時(shí)以一小部分計(jì)算成本來接近專業(yè)表現(xiàn)。即使是在離線數(shù)據(jù)的生成上，基于 CPU 的 FSB 實(shí)現(xiàn)在大規(guī)模 MIP 上也可能過于昂貴。他們用交替方向乘子法 (ADMM) 開發(fā)了 FSB 的變體，可以通過在 GPU 上以批處理方式執(zhí)行所需的計(jì)算來擴(kuò)展到大規(guī)模 MIP。

DeepMind與Google Research的團(tuán)隊(duì)在許多包含大規(guī)模 MIP 的數(shù)據(jù)集上對這個(gè)方法進(jìn)行了評估，包括來自 Google 生產(chǎn)系統(tǒng)的兩個(gè)數(shù)據(jù)集，以及 MIPLIB(一個(gè)異構(gòu)數(shù)據(jù)集和標(biāo)準(zhǔn)基準(zhǔn))。

來自所有數(shù)據(jù)集的大多數(shù) MIP 組合集在預(yù)求解后都有 10^3-10^6 個(gè)變量和約束，明顯大于早期工作(Gasse et al. 2019, Ding et al. 2020)。一旦 Neural Diving 與 Neural Branching 模型在給定數(shù)據(jù)集上進(jìn)行了訓(xùn)練，它們會(huì)被整合到 SCIP 中，形成專門針對該數(shù)據(jù)集的“神經(jīng)求解器”(Neural Solver)。SCIP是基線，重點(diǎn)參數(shù)分別在每個(gè)數(shù)據(jù)集上經(jīng)過網(wǎng)格搜索進(jìn)行調(diào)整，他們將其稱為“Tuned SCIP”。

比較 Neural Solver 和 Tuned SCIP 在一組hold-out實(shí)例上原問題對偶問題的差距平均值 (如圖2)，在他們所評估的、具有最大 MIP 的4個(gè)數(shù)據(jù)集(一共有5個(gè)數(shù)據(jù)集)上，神經(jīng)求解器(Neural Solver)在相同的運(yùn)行時(shí)間內(nèi)提供了明顯更好的差距，或在更少時(shí)間內(nèi)提供了相同的差距，同時(shí)在第5個(gè)數(shù)據(jù)集上媲美 Tuned SCIP 的表現(xiàn)。他們介紹，據(jù)他們所知，這是第一項(xiàng)在大規(guī)模現(xiàn)實(shí)世界應(yīng)用數(shù)據(jù)集和 MIPLIB 上，使用機(jī)器學(xué)習(xí)比使用 SCIP 具有更大改進(jìn)的工作。

圖 2：論文的主要結(jié)果：他們的方法(Neural Branching + Neural Divin)在原問題與對偶問題的差距上與 SCIP 媲美，或優(yōu)于 SCIP，在留出實(shí)例上不相上下。

Tuned SCIP 是他們比較的基線，因?yàn)樗麄兪褂?SCIP 作為整合學(xué)習(xí)啟發(fā)式算法的基礎(chǔ)求解器。

作為基礎(chǔ)求解器，SCIP 提供了：a) 用于集成學(xué)習(xí)模型的內(nèi)部狀態(tài)的深入訪問權(quán)限;b) 并行運(yùn)行大規(guī)模求解實(shí)例來進(jìn)行大規(guī)模評估的許可授權(quán)。

作者表示，他們無法使用具有這些功能的商業(yè)求解器，所以它們相當(dāng)于不可用。他們已經(jīng)在兩個(gè)數(shù)據(jù)集上對 Gurobi 與 Neural Diving 進(jìn)行了部分比較，其中 Gurobi 作為 sub-MIP 的求解器。對比原始差距在一組保留實(shí)例上的平均值，具有并行 sub-MIP 求解的 Neural Diving 在兩個(gè)數(shù)據(jù)集上達(dá)到 1% 的平均原始間隔比 Gurobi 的時(shí)間少 3 倍和 3.6 倍。

他們還將 Neural Diving 的修改版本應(yīng)用于 MIPLIB 中“開放”實(shí)例的子集，以找到三個(gè)新的最著名任務(wù)來擊敗商業(yè)求解器。一些早期的工作專注于學(xué)習(xí)原始啟發(fā)式算法。與它們不同的是，Neural Diving 將預(yù)測變量賦值的問題看作生成建模問題提出，提供了一種原則性方法來學(xué)習(xí)所有可用的可行賦值，并在測試時(shí)間內(nèi)生成部分真值。

一些工作也著眼于學(xué)習(xí)分支策略。其中，許多都像DeepMind這個(gè)團(tuán)隊(duì)一樣專注于學(xué)習(xí)模仿 FSB。與它們不同的是，Neural Branching 使用了更可擴(kuò)展的方法來計(jì)算使用 GPU 的目標(biāo)策略，與基于 CPU 的 FSB 實(shí)現(xiàn)相比，這允許它在相同的時(shí)間限制內(nèi)從更大的實(shí)例中生成更多的模仿數(shù)據(jù)。這個(gè)工作還超越了早期獨(dú)立研究學(xué)習(xí)個(gè)體啟發(fā)式的工作，通過在求解器中結(jié)合學(xué)習(xí)的原始啟發(fā)式和學(xué)習(xí)的分支策略，在大規(guī)模實(shí)際應(yīng)用數(shù)據(jù)集和 MIPLIB 上實(shí)現(xiàn)了明顯更優(yōu)的性能。

3、論文貢獻(xiàn)

這個(gè)工作的主要貢獻(xiàn)如下：

• 提出了Neural Diving。這是一種基于學(xué)習(xí)的新方法，可以為 MIP 生成高質(zhì)量的聯(lián)合變量賦值。在同類數(shù)據(jù)集上，Neural Diving 在留出實(shí)例上實(shí)現(xiàn)了 1% 的平均原始差距，比 Tuned SCIP 快了 3-10 倍。在一個(gè)數(shù)據(jù)集上，Tuned SCIP 在時(shí)限內(nèi)沒能達(dá)到 1% 的平均原始差距，而 Neural Diving 做到了。
• 提出了Neural Branching，通過模仿基于 ADMM 的新可擴(kuò)展專家策略來學(xué)習(xí)在分支定界算法中使用的分支策略。在評估時(shí)所使用的兩個(gè)數(shù)據(jù)集上，由于實(shí)例規(guī)模(如有大于105個(gè)變量)或每次的迭代時(shí)間很長，F(xiàn)SB很慢，ADMM 專家在相同的運(yùn)行時(shí)間內(nèi)生成了 1.4 倍和 12 倍訓(xùn)練數(shù)據(jù)。學(xué)習(xí)策略在四個(gè)數(shù)據(jù)集上顯著優(yōu)于 SCIP 的分支啟發(fā)式算法，在大時(shí)間限制下的留出實(shí)例上平均對偶差距提高了 2-20 倍，并在其他數(shù)據(jù)集上取得了可媲美的性能。
• 將 Neural Diving 與 Neural Branching 結(jié)合起來，在具有最大 MIP 的4個(gè)數(shù)據(jù)集(共有5個(gè)數(shù)據(jù)集)中的平均原始對偶差距上獲得了明顯比 SCIP 更好的性能，同時(shí)在第5個(gè)數(shù)據(jù)集中達(dá)到與 SCIP 不相上下的性能。

此外，他們還開源了一個(gè)用于神經(jīng)網(wǎng)絡(luò)驗(yàn)證的數(shù)據(jù)集(第 4、12.6 節(jié))，希望有助于進(jìn)一步研究 MIP 的新學(xué)習(xí)技術(shù)。

4、結(jié)論

這項(xiàng)工作證明了機(jī)器學(xué)習(xí)在大規(guī)模現(xiàn)實(shí)世界應(yīng)用數(shù)據(jù)集和 MIPLIB 上能夠顯著提高 MIP 求解器性能的長期潛力。我們相信，隨著模型和算法的進(jìn)一步改善，這個(gè)方法會(huì)有更大的改進(jìn)。

一些在未來有前景的研究方向是：

• 學(xué)習(xí)切割：使用機(jī)器學(xué)習(xí)更好地選擇和生成切割是性能改進(jìn)的另一個(gè)潛在技術(shù)。
• 熱啟動(dòng)模型：學(xué)習(xí)模型在 MIPLIB 上的強(qiáng)勁表現(xiàn)表明，它可以學(xué)習(xí)在不同 MIP 中都能很好地工作的啟發(fā)式方法。這可用于克服應(yīng)用場景中的“冷啟動(dòng)”問題，即應(yīng)用中早期可用的訓(xùn)練數(shù)據(jù)量可能太少而無法訓(xùn)練好的模型。我們可以從使用在異構(gòu)數(shù)據(jù)集上訓(xùn)練的模型開始，并在為應(yīng)用收集更多數(shù)據(jù)時(shí)，將它們用作通往更專業(yè)模型的橋梁。
• 強(qiáng)化學(xué)習(xí)：使用蒸餾或行為克隆獲得的性能是由現(xiàn)有的最佳專家提供，而強(qiáng)化學(xué)習(xí) (RL) 可能會(huì)超過它。高效探索、長期信用分配和學(xué)習(xí)的計(jì)算可擴(kuò)展性是將 RL 應(yīng)用于大規(guī)模 MIP 的關(guān)鍵挑戰(zhàn)。解決這些問題可以帶來更大的性能改進(jìn)。

本文轉(zhuǎn)自雷鋒網(wǎng)，如需轉(zhuǎn)載請至雷鋒網(wǎng)官網(wǎng)申請授權(quán)。