谷歌的DeepMind 團(tuán)隊最近發(fā)表了一篇關(guān)于使用神經(jīng)網(wǎng)絡(luò)解決MIP 的論文。一石激起千層浪，引發(fā)了國內(nèi)外運(yùn)籌學(xué)和優(yōu)化界的討論。

有看瓜吃瓜的人表示：

“這太酷了！”

“很高興看到機(jī)器學(xué)習(xí)和組合優(yōu)化的融合最終發(fā)生”

“OR（運(yùn)籌學(xué)）被打破只是時間問題”

一些從業(yè)者已經(jīng)開始尋求代碼：

'代碼是開源的嗎？很想在一些標(biāo)準(zhǔn)的難題上測試它”

“需要在這里查看一些代碼”

“測試這個會非常有趣”

事實上，將機(jī)器學(xué)習(xí)和整數(shù)規(guī)劃結(jié)合起來并不是一個新話題。為什么谷歌的這篇論文引起如此多的關(guān)注？谷歌和DeepMind團(tuán)隊的聲譽(yù)當(dāng)然是最大的因素。從圍棋中的AlphaGo到最近蛋白質(zhì)結(jié)構(gòu)預(yù)測中的AlphaFold2，DeepMind的每一步舉動都是走在最前沿的一大步，也確實在一些領(lǐng)域帶來了突破。進(jìn)步。但這篇論文是否有能夠打破OR（運(yùn)籌學(xué)）的顛覆性研究成果呢？

DeepMind 沒有回應(yīng)開源這部分代碼的請求，所以如果你想看到他們的工作，你只能閱讀論文。這篇論文的原文可以在arXiv上找到：

杉樹科技COPT求解器開發(fā)團(tuán)隊對本文進(jìn)行了詳細(xì)的研究和研究。這里我們呈現(xiàn)團(tuán)隊的分析和討論，以進(jìn)一步探索機(jī)器學(xué)習(xí)和優(yōu)化算法的結(jié)合。

MIP（Mixed Integer Planning）一般指混合整數(shù)線性規(guī)劃。它在滿足線性約束Axb和整數(shù)約束xZ的前提下求解目標(biāo)函數(shù)f(x)=cx的最小值。數(shù)組x稱為決策變量，數(shù)組c是這些決策變量的目標(biāo)系數(shù)，矩陣A是線性約束矩陣，Z是整數(shù)集合。整數(shù)規(guī)劃在現(xiàn)實世界中有著極其廣泛的用途，如航空航天、能源網(wǎng)格、制造、交通物流、軍事和通信等，發(fā)揮著不可替代的基礎(chǔ)建模和求解功能。但整數(shù)規(guī)劃也是一個非常困難的問題。從計算機(jī)復(fù)雜性理論來看，它屬于NP-hard問題范疇。這也是美國卡倫宣布的七個數(shù)學(xué)千年獎問題之一。對于這樣的問題，是否存在多項式時間？精確的求解算法尚未確定。

求解整數(shù)規(guī)劃的主要算法組件包括：預(yù)求解、分支定界、啟發(fā)式算法、割平面、沖突分析和線性規(guī)劃求解器模塊。由于DeepMind這次的論文主要涉及分支算法和啟發(fā)式算法，所以我們將分別關(guān)注這兩個方向。下面將首先分析DeepMind 的基本結(jié)論，然后針對DeepMind 論文中提到的Neural Branching 和Neural Diving 兩項成果介紹混合整數(shù)規(guī)劃相關(guān)的背景知識，然后比較分析DeepMind 論文中的新思想和傳統(tǒng)。紙。算法關(guān)系。

文章最后我們還給出了山數(shù)科技在求解器內(nèi)部開發(fā)和外部應(yīng)用過程中對機(jī)器學(xué)習(xí)、強(qiáng)化學(xué)習(xí)等技術(shù)的探索和運(yùn)用的一些簡單例子。我們還想說明，從誕生的第一天起，運(yùn)籌學(xué)和優(yōu)化技術(shù)就注定是一門廣泛交叉的科學(xué)。各種大數(shù)據(jù)和人工智能技術(shù)的興起為其注入了新的活力。在智能決策領(lǐng)域，可以預(yù)見它將發(fā)揮越來越重要的作用。

1

DeepMind論文解題結(jié)果分析

DeepMind 的論文引起了廣泛關(guān)注，不僅因為團(tuán)隊的聲譽(yù)，還因為論文中報告的驚人的性能提升數(shù)據(jù)。正如論文摘要中提到的，在測試的5 組問題中，3 組分別取得了1.5 倍、2 倍和10,000 倍的更好Gap。

其實，這里有一個小小的文字游戲。作為MIP求解器開發(fā)者，我們一般不會以一定時間內(nèi)能夠獲得的Gap作為主要標(biāo)準(zhǔn)。因為這有些誤導(dǎo)。想象一下更特殊類型的整數(shù)規(guī)劃問題，例如可行性問題，它沒有目標(biāo)函數(shù)，只需要找到一組整數(shù)解。那么在找到整數(shù)解之前，它的Gap是100%，找到之后，它是0%。如果開啟和關(guān)閉某種啟發(fā)式（或割平面）算法，分別可以在1小時和3小時內(nèi)找到可行解。如果以兩個小時為觀察點(diǎn)，可以說開啟這個算法后，達(dá)到的Gap增加了無限倍。但如果以半小時或三小時為觀察點(diǎn)，Gap并沒有改善。由于DeepMind 尚未公布用于計算這些性能指標(biāo)的原始數(shù)據(jù)，因此我們無法使用MIP 行業(yè)公認(rèn)的方法對其進(jìn)行評估。一般來說，根據(jù)目前公認(rèn)的測試標(biāo)準(zhǔn)，通常是基于MIPLIB問題集，以兩個小時為限，并考慮可以解決的問題數(shù)量和平均解決時間進(jìn)行比較。

特定的測試集取得驚人的性能提升并不奇怪，因為這正是機(jī)器學(xué)習(xí)所擅長的：它可以捕捉同類型問題的特征結(jié)構(gòu)并給出優(yōu)化趨勢的判斷。正如后面提到的，我們自己在開發(fā)過程中也有類似的經(jīng)歷。真正值得關(guān)注的是它在MIPLIB 上的表現(xiàn)。 MIPLIB 2017由來自各行各業(yè)的1000多個示例組成，MIPLIB2017 Benchmark由從中選出的240個不同結(jié)構(gòu)的問題組成。它在篩選過程中是完全區(qū)分的，因此它與電網(wǎng)優(yōu)化和NN驗證等測試集有本質(zhì)的不同。這也解釋了為什么該算法在MIPLIB上的性能提升不如其他數(shù)據(jù)集那么明顯。

為了避嫌，谷歌早前也在論文中表示，訓(xùn)練集使用了完整版MIPLIB 中的1000 多個問題，并刪除了這240 個問題中剩余的示例。然而，仍然難以避免訓(xùn)練集和測試集之間的結(jié)構(gòu)相似性。例如，在收集MIPLIB 2017 完整版時，通常會從同一來源收集多個大小略有不同的計算示例。在選擇基準(zhǔn)集時，為了避免基準(zhǔn)集重復(fù)，我們會盡量避免使用同一來源的示例。這使得MIPLIB 2017 完整版中的其余示例包含基準(zhǔn)集的高級結(jié)構(gòu)。類似的問題。比如MIPLIB 2017 Benchmark中有g(shù)raph20-20-1rand的問題，有g(shù)raph-20-80-1rand、graph-40-20-1rand、graph-40-40-1rand、graph-40- MIPLIB2017全套中80-。 1r和四個結(jié)構(gòu)高度相似的問題。因此，在訓(xùn)練集上獲得的經(jīng)驗肯定會對解決最終的測試集有幫助。這些幫助是否可以推廣到任何一般問題集是非常值得懷疑的。

2

分支算法和神經(jīng)分支

分支算法是整數(shù)規(guī)劃求解器的核心框架。解決MIP 通常需要解決多個LP（線性規(guī)劃）問題。第一個LP 問題是沒有所有整數(shù)約束的原始問題。如果第一個LP問題的最優(yōu)解恰好滿足整數(shù)條件，那么這個解也是整數(shù)規(guī)劃的最優(yōu)解。如果LP松弛問題的解不全部滿足整數(shù)條件，則可以通過分支算法繼續(xù)尋找整數(shù)解。

分支算法通過選擇值不是整數(shù)的變量x=x* 并添加xfloor(x*)（即值不大于x* 的最大整數(shù)下界）和x 進(jìn)行分支。分別為ceil(x*)。 （即值不小于x*的最小整數(shù)上界）這兩個約束將原問題分解為兩個子問題。原整數(shù)規(guī)劃問題的最優(yōu)解必定位于這兩個分支之一。接下來繼續(xù)解決這兩個問題，以此類推，直到找到最優(yōu)整數(shù)解或者證明整數(shù)解不存在。不難看出，分支算法的本質(zhì)就是枚舉。在具有n個0-1變量的混合整數(shù)規(guī)劃問題中，在最壞的情況下，必須遍歷所有2的n次方分支節(jié)點(diǎn)。又由于混合整數(shù)規(guī)劃問題是一個NP難問題，目前精確求解的算法基本上都是基于分支算法的框架。在最壞的情況下，復(fù)雜度是指數(shù)級的時間級別，并且耗時可能會非常長。

在實踐中，求解整數(shù)規(guī)劃通常需要更少的所有節(jié)點(diǎn)枚舉。這是因為分支算法可以以更智能的方式選擇要從中分支的變量。在眾多分支算法中，最有效的算法是完全強(qiáng)分支算法（Full Strong Branching，簡稱FSB）。該算法的原理很簡單，就是通過對當(dāng)前LP（線性規(guī)劃）問題中每個值不是整數(shù)的變量進(jìn)行分支，求解所有分支的LP問題，并根據(jù)目標(biāo)函數(shù)值判斷選擇哪個分支LP。 MIP解決方案可以盡快完成。在實際應(yīng)用中，F(xiàn)SB所需的計算量非常大，因此對每個LP節(jié)點(diǎn)都使用它是不現(xiàn)實的。在MIP 求解過程中，將不時執(zhí)行有限循環(huán)次數(shù)的強(qiáng)分支，以獲得每個變量分支的最佳估計。

Google提出的Neural Branching的本質(zhì)是首先通過神經(jīng)網(wǎng)絡(luò)離線學(xué)習(xí)FSB的真實計算結(jié)果，然后在實際應(yīng)用中模擬FSB計算，在追求FSB效果的同時節(jié)省計算時間。事實上，在過去的幾年里，關(guān)于這項工作的類似論文已有很多。 Google的論文在相關(guān)工作中還提到了其他8篇相關(guān)研究論文，大部分基本思路都比較相似。因此，論文在這一點(diǎn)上的創(chuàng)新具有一定的局限性。正如Google論文中所說：它使用GPU和ADMM來計算原始問題的大量FSB近似值，從而可以生成大量的機(jī)器學(xué)習(xí)數(shù)據(jù)。不過，這也從另一個側(cè)面反映了FSB的計算量。即使生成了離線學(xué)習(xí)數(shù)據(jù)，我們也必須想辦法讓它更快。

與傳統(tǒng)的分支算法相比，神經(jīng)分支和該領(lǐng)域的其他研究確實是（離線）機(jī)器學(xué)習(xí)和優(yōu)化算法的有趣組合。然而，值得指出的是，經(jīng)典分支算法還根據(jù)歷史數(shù)據(jù)預(yù)測未來的分支。其本質(zhì)也是一種在線機(jī)器學(xué)習(xí)機(jī)制。例如，在冷杉數(shù)求解器中，使用強(qiáng)分支只是其中之一。此外，還有偽價格（Pseudocost）、可靠性（Reliability）、推斷（Inference）等公開和其他非公開的判斷標(biāo)準(zhǔn)。這些算法都是在求解過程中積累信息，并利用這些信息來判斷和選擇新的分支變量。

3

啟發(fā)式算法和神經(jīng)潛水

啟發(fā)式算法是除主要分支定界算法之外尋找整數(shù)解的算法的總稱。啟發(fā)式算法是MIP 研究的熱點(diǎn)，相關(guān)論文眾多。目前，僅SCIP 中就實現(xiàn)了57 種啟發(fā)式算法。這些啟發(fā)式算法大致可以分為四類：Rounding、Diving、Sub-MIP，以及上述三類之外的其他算法。

顧名思義，Rounding 啟發(fā)式算法對不滿足的變量進(jìn)行舍入，以期在LP 松弛解不滿足整數(shù)約束時得到整數(shù)解。潛水啟發(fā)式算法的本質(zhì)是深度優(yōu)先搜索。當(dāng)LP松弛解不滿足整數(shù)約束時，從當(dāng)前節(jié)點(diǎn)開始，不斷選擇最佳分支進(jìn)行深度優(yōu)先搜索，直到找到整數(shù)解或證明子問題。直到不可行為止。這兩類算法的原理雖然簡單，但也有多種實現(xiàn)變體，這里不做討論。

子混合整數(shù)規(guī)劃問題（Sub-MIP）的啟發(fā)式算法是一個大類，它通過構(gòu)造和解決子MIP 問題來找到高質(zhì)量的整數(shù)解。構(gòu)造子問題時，構(gòu)造方法有很多種，例如固定或收緊變量、添加約束、修改目標(biāo)函數(shù)值等。其中，如固定變量算法，比較著名的是松弛誘導(dǎo)鄰域搜索（RINS）。它的工作原理是，當(dāng)LP松弛解中某個整數(shù)變量的值等于當(dāng)前最佳整數(shù)解中的值一致時，該變量就固定為這個整數(shù)值。如果可以固定大量的變量，那么固定變量后的子問題就可以作為一個新的MIP來求解，以期找到高質(zhì)量的整數(shù)解。由于大量變量是固定的，子問題的搜索空間會變小，預(yù)求解可以進(jìn)一步減小問題的規(guī)模，因此子問題的求解會相對容易一些。

DeepMind提出的Neural Diving算法利用機(jī)器學(xué)習(xí)和神經(jīng)網(wǎng)絡(luò)給出問題結(jié)構(gòu)，預(yù)測如何固定一些整數(shù)變量的值，然后求解子MIP。因此，盡管使用了Diving 這個詞，但我們認(rèn)為它可以歸類為解決子問題的啟發(fā)式算法。可以看出，該算法與上述RINS在原理上有很多相似之處，只是固定變量的方式不同。

盡管其思想與許多現(xiàn)有的啟發(fā)式算法類似，但Neural Diving 仍然有其獨(dú)特的功能。 Neural Diving 的最大優(yōu)點(diǎn)之一是它可以生成多組有區(qū)別的部分變量值，并在正式解決原始問題之前啟動啟發(fā)式算法。一方面，這提高了算法尋找高質(zhì)量整數(shù)解的成功率。另一方面也提前了尋找整數(shù)解的時間，因此可以更早地得到更小的Gap。我們也認(rèn)為這是DeepMind論文中最有價值的部分。

4

人工智能與MIP結(jié)合的示例應(yīng)用

山書求解器在開發(fā)過程中充分利用了機(jī)器學(xué)習(xí)工具。除了上面提到的本質(zhì)上是在線學(xué)習(xí)的分支算法之外，我們還在許多其他不同的方向上使用機(jī)器學(xué)習(xí)工具。

例如，求解子MIP 的啟發(fā)式算法是一種有效但非常耗時的算法。在開發(fā)過程中，我們解決了大量的子問題，提取子問題特征（例如重新預(yù)求解結(jié)果、變量類型等），并使用機(jī)器學(xué)習(xí)來幫助確定是否值得花費(fèi)時間從某個子問題開始求解，可以避免耗時，也是提高求解速度的有效方法。

另外，我們線性規(guī)劃LP求解器的開發(fā)也受益于機(jī)器學(xué)習(xí)。例如，我們對一些具有特殊結(jié)構(gòu)的LP使用機(jī)器學(xué)習(xí)方法來預(yù)測某個變量是否是最優(yōu)解的基本解的一部分，并通過對目標(biāo)函數(shù)的小擾動將這種預(yù)測結(jié)果應(yīng)用到LP問題中以實現(xiàn)快速求解。

除了上述嵌入求解器的機(jī)器學(xué)習(xí)成果外，過去幾年，山書在使用求解器解決多個行業(yè)的疑難問題時，也從機(jī)器學(xué)習(xí)、深度學(xué)習(xí)、強(qiáng)化學(xué)習(xí)等方面受益匪淺。大的。

國家電網(wǎng)安全約束單位承諾（SCUC）問題就是一個例子。 SCUC問題的特點(diǎn)是規(guī)模小，但需要快速求解。我們遇到的實際問題只有幾千個整型變量，每15分鐘需要解決一次，并且必須在15分鐘內(nèi)盡快解決。我們利用深度神經(jīng)網(wǎng)絡(luò)等機(jī)器學(xué)習(xí)方法來預(yù)測MIP模型最優(yōu)解中每個決策變量取1的概率，從而固定一些置信度最高的變量，并對一些中間值的變量添加多變量分支切割面。信心。使最終問題以最高概率可行。這種方法可以有效降低分支定界樹的搜索規(guī)模。一方面可以實現(xiàn)快速收斂，另一方面可以快速找到高質(zhì)量的初始解。最終實驗表明，使用該方法，達(dá)到相同質(zhì)量解（Gap=0.01%）的速度提高了約5-10倍。很多情況下，原來的問題3分鐘無法解決，但結(jié)合機(jī)器學(xué)習(xí)算法，只需10秒就可以解決。這種速度的提高對于每15 分鐘需要快速計算決策的SCUC 問題非常重要。

電網(wǎng)方面的優(yōu)化也是DeepMind指出智能MIP可以重點(diǎn)發(fā)力的領(lǐng)域。但值得強(qiáng)調(diào)的是，電網(wǎng)的另一個特點(diǎn)是對安全性和魯棒性的極端要求。當(dāng)新問題的數(shù)據(jù)結(jié)構(gòu)突然發(fā)生巨大變化，歷史數(shù)據(jù)已經(jīng)無法指導(dǎo)未來，比如戰(zhàn)爭、自然或人為因素導(dǎo)致發(fā)電廠和輸電線路發(fā)生巨大變化時，機(jī)器學(xué)習(xí)的作用就會被大大削弱。這時，更多的時候，我們?nèi)匀灰蕾囉贛IP求解器本身的六個模塊中與數(shù)據(jù)無關(guān)的經(jīng)典算法的實現(xiàn)能力。

又如中國郵政的路由網(wǎng)絡(luò)規(guī)劃問題。我們在實際中遇到的此類問題通常需要求解數(shù)十萬個整數(shù)變量的MIP 來確定發(fā)車時刻表。如果直接扔給求解器，通常需要一到兩個小時才能找到第一個整數(shù)解（差距在30% 左右，甚至更糟）。通過觀察，我們發(fā)現(xiàn)雖然不可能預(yù)測所有的出發(fā)安排，但是我們可以預(yù)測一些高概率的車輛安排。我們進(jìn)一步開發(fā)了一套方法，通過歷史數(shù)據(jù)的機(jī)器學(xué)習(xí)，基于線性約束關(guān)系為數(shù)千個列車時刻表生成部分初始解決方案。在此基礎(chǔ)上，我們通過暫時固定這些決策變量來構(gòu)造子MIP問題，并利用求解器快速計算并完成子問題的求解。由于該子問題的一些關(guān)鍵變量已經(jīng)確定，預(yù)求解模塊可以顯著減小問題規(guī)模，有利于快速求解。雖然這個子問題的最優(yōu)解并不是原問題的最優(yōu)解，但在實踐中這個解（差距在10%以內(nèi)）明顯優(yōu)于第一個需要一到兩個小時計算的可行解。從預(yù)測到子問題的解決，通常需要不到1分鐘。因此，可以說機(jī)器學(xué)習(xí)幫助我們以50 倍的速度找到相同質(zhì)量（實際上更好）的整數(shù)解。

另一個具有更廣泛意義的例子是，在最近的科研論文和幾家自稱從事智能決策的公司的聲明中，我們可以看到一些交通問題，例如車輛調(diào)度和路線規(guī)劃，由于其事件頻率高且數(shù)據(jù)結(jié)構(gòu)。它相對穩(wěn)定，因此無論是分支策略、初始解固定，甚至割平面生成，都可以通過機(jī)器學(xué)習(xí)技術(shù)獲得，從而加速問題的MIP模型求解。確實，很多學(xué)者在這個問題上已經(jīng)取得了比較大的進(jìn)展。因此，交通領(lǐng)域也是機(jī)器學(xué)習(xí)、智能決策等技術(shù)近年來重點(diǎn)關(guān)注的領(lǐng)域。

事實上，這不僅僅是路線規(guī)劃。五年前，杉樹與中國最大的出行平臺之一合作，考慮為駕駛員和乘客提供智能動態(tài)匹配系統(tǒng)。該問題從簡單的機(jī)器學(xué)習(xí)計算匹配系數(shù)和啟發(fā)式算法分配，到后來的全城時間分片網(wǎng)絡(luò)流量匹配，再融合削峰填谷、智慧出行等理念，建立了整個城市的動態(tài)規(guī)劃模型。系統(tǒng)，并在強(qiáng)化學(xué)習(xí)框架下，逼近未來的趨勢和決策，最終得到在時間和空間上都接近全局優(yōu)化的解決方案。隨著數(shù)據(jù)的完備和算力的可用，整個系統(tǒng)在雙方共同建立的強(qiáng)化學(xué)習(xí)框架下不斷演化。從簡單的線性函數(shù)逼近到神經(jīng)網(wǎng)絡(luò)逼近，變得更加智能和準(zhǔn)確。 2017年已實現(xiàn)廣泛應(yīng)用，創(chuàng)造了巨大的經(jīng)濟(jì)效益和社會效益。

5

結(jié)論

最后，我們要強(qiáng)調(diào)的是，正如“機(jī)器學(xué)習(xí)之父”邁克爾·喬丹所指出的那樣，未來人工智能最重要的突破應(yīng)該與優(yōu)化算法緊密結(jié)合。這就是運(yùn)籌學(xué)的核心基礎(chǔ)。

在今天討論的例子中，簡單地說，神經(jīng)網(wǎng)絡(luò)和機(jī)器學(xué)習(xí)技術(shù)的進(jìn)步更像是在MIP 開發(fā)的六個模塊中的兩個探索的武器庫中添加一些昂貴的（計算資源需求）。強(qiáng)大的武器豐富了這些模塊的加速能力，這遠(yuǎn)沒有打破OR。這些技術(shù)所展現(xiàn)出的潛力值得歡呼，但解決現(xiàn)實中的MIP 問題需要極其繁重的數(shù)學(xué)技能和工程經(jīng)驗。

傳統(tǒng)的MIP求解工具具有數(shù)十年的理論論證和理論分析基礎(chǔ)。相比之下，MIP解決方案中使用的機(jī)器學(xué)習(xí)工具由于模型結(jié)構(gòu)的復(fù)雜性，理論論證成果很少。大量相關(guān)的機(jī)器學(xué)習(xí)研究依賴于某一類或幾類數(shù)據(jù)集的數(shù)值實驗結(jié)果來驗證其有效性。因此，機(jī)器學(xué)習(xí)方法解決現(xiàn)實中普遍問題的可靠性需要進(jìn)一步論證。另一方面，大多數(shù)機(jī)器學(xué)習(xí)算法設(shè)計需要將模型轉(zhuǎn)換為經(jīng)典的整數(shù)、線性、凸或非凸數(shù)學(xué)規(guī)劃模型，然后對其進(jìn)行分析。

回到MIP，可以說僅僅利用機(jī)器學(xué)習(xí)在某些點(diǎn)上取得突破是遠(yuǎn)遠(yuǎn)不夠的。在真正的顛覆性技術(shù)突破（例如量子計算機(jī)的真正實用化）之前，一般整數(shù)規(guī)劃甚至廣泛的NP 難題仍然有望成為未來許多年人類智能的限制之一。

注：在本文的撰寫過程中，我得到了香港中文大學(xué)（深圳）的王自卓、斯坦福大學(xué)的葉印宇、紐約大學(xué)的陳曦、約翰斯大學(xué)的姜宏毅等多位學(xué)者的指導(dǎo)和建議霍普金斯大學(xué)。我謹(jǐn)向他們表示感謝。