并非無(wú)所不能——評(píng)DeepMind近期神經(jīng)網(wǎng)絡(luò)求解MIP的論文

作者：皇甫琦，葛冬冬，杉數(shù)科技COPT開(kāi)發(fā)組

引言：本文對(duì)DeepMind近期的神經(jīng)網(wǎng)絡(luò)求解MIP（混合整數(shù)規(guī)劃）的論文進(jìn)行了一些初步解讀。事實(shí)上，相較于此領(lǐng)域近期的類(lèi)似工作，DeepMind的工作在MIP的求解開(kāi)發(fā)某些環(huán)節(jié)，如分支定界，啟發(fā)式算法上所做的利用神經(jīng)網(wǎng)絡(luò)的嘗試，更加的精細(xì)化和高度工程化，并且與開(kāi)源求解器的耦合程度明顯更高，也取得了相對(duì)良好的進(jìn)展，但是并未看到太多有突破性和顛覆性的思想。

Google的DeepMind團(tuán)隊(duì)最近官宣了一篇神經(jīng)網(wǎng)絡(luò)(Neural Networks)求解MIP論文。一石激起千層浪，在國(guó)內(nèi)外的運(yùn)籌優(yōu)化社群引起了討論。

部分圍觀吃瓜群眾紛紛表示：

“This is uber cool”

“Excited to see this merging of ML and combinatorial optimization finally happening”

“攻破OR（運(yùn)籌學(xué)）只是時(shí)間問(wèn)題”

而一些實(shí)踐派已經(jīng)在伸手要代碼了：

“Is the code open-source? Would love to test it on some standard hard problems”

“Going to need to see some code here”

“It would be very interesting to test this”

其實(shí)，把機(jī)器學(xué)習(xí)和整數(shù)規(guī)劃結(jié)合在一起并不是一個(gè)新課題。為什么Google的這篇論文引起這么大的關(guān)注。Google和DeepMind團(tuán)隊(duì)的名氣當(dāng)然是最大的因素，從圍棋的AlphaGo到最近的蛋白質(zhì)結(jié)構(gòu)預(yù)測(cè)的AlphaFold2，DeepMind的每次出手都是風(fēng)口浪尖上的大動(dòng)作，也確實(shí)在某些領(lǐng)域帶來(lái)過(guò)突破性的進(jìn)展。但這篇論文是否有顛覆性的研究成果，以至于可以“攻破OR（運(yùn)籌學(xué)）”？

DeepMind并沒(méi)有回應(yīng)開(kāi)源這部分代碼的要求，因此想要看看他們的工作只能讀論文。這篇論文的原文可在arXiv獲取：
https://arxiv.org/abs/2012.13349。杉數(shù)科技的COPT求解器開(kāi)發(fā)團(tuán)隊(duì)詳細(xì)地學(xué)習(xí)、研究了這篇論文。在此我們把團(tuán)隊(duì)的分析討論奉上，以資對(duì)機(jī)器學(xué)習(xí)和優(yōu)化算法結(jié)合做進(jìn)一步探討。

MIP（混合整數(shù)規(guī)劃）一般特指混合整數(shù)線性規(guī)劃，它在滿足線性約束條件Ax≤b和整數(shù)約束條件x∈Z的前提下，求解目標(biāo)函數(shù)f(x) = c·x的最小值。其中數(shù)組x叫做決策變量，數(shù)組c是這些決策變量的目標(biāo)系數(shù)，矩陣A是線性約束矩陣，Z是整數(shù)集合。整數(shù)規(guī)劃在現(xiàn)實(shí)世界中的用途極為廣闊，例如在航空航天，能源電網(wǎng)，生產(chǎn)制造，交通物流，軍事與通訊等領(lǐng)域都起著不可替代的基礎(chǔ)建模與求解功能。但是整數(shù)規(guī)劃也是非常困難的問(wèn)題，在計(jì)算機(jī)的復(fù)雜性理論上，是屬于NP難問(wèn)題類(lèi)的，也是美國(guó)庫(kù)蘭所公布的數(shù)學(xué)七個(gè)千年大獎(jiǎng)難題之一，對(duì)于此類(lèi)問(wèn)題，是否存在多項(xiàng)式時(shí)間的精確求解算法，至今仍未有定論。

求解整數(shù)規(guī)劃的主要算法部件有：預(yù)求解、分支定界、啟發(fā)式算法、割平面、沖突分析和線性規(guī)劃求解器等模塊。鑒于DeepMind此次的論文主要涉及分支算法和啟發(fā)式算法，我們分別重點(diǎn)從這兩個(gè)方向進(jìn)行探討。下文會(huì)對(duì)DeepMind的基本結(jié)論先做一個(gè)分析，然后分別就DeepMind論文中提到的Neural Branching和Neural Diving這兩項(xiàng)成果，介紹混合整數(shù)規(guī)劃相關(guān)的背景知識(shí)，然后對(duì)比分析論文中的新思路和傳統(tǒng)算法的關(guān)系。

文末，也對(duì)杉數(shù)科技在求解器內(nèi)部開(kāi)發(fā)和外部應(yīng)用過(guò)程中對(duì)機(jī)器學(xué)習(xí)，強(qiáng)化學(xué)習(xí)等技術(shù)探索和使用做了一些簡(jiǎn)單的舉例，也是想說(shuō)明運(yùn)籌與優(yōu)化技術(shù)從誕生的第一天起，就注定了是一門(mén)廣泛交叉的科學(xué)，多種大數(shù)據(jù)與人工智能技術(shù)的興起，為它注入了新的活力，在智能決策的領(lǐng)域，可以預(yù)見(jiàn)將會(huì)發(fā)揮越來(lái)越大的作用。

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

DeepMind的論文引起了廣泛的關(guān)注，并不止因?yàn)閳F(tuán)隊(duì)的名聲，也來(lái)自于論文中報(bào)告了非常驚人的性能提升數(shù)據(jù)。如論文摘要中提到的，對(duì)于測(cè)過(guò)的5組問(wèn)題里，在3組上分別實(shí)現(xiàn)了1.5倍，2倍，以及1萬(wàn)倍的更好的Gap。

其實(shí)這里玩了一個(gè)小小的文字游戲。作為MIP求解器開(kāi)發(fā)人員，一般不把一定時(shí)間內(nèi)能拿到的Gap作為主要衡量標(biāo)準(zhǔn)。因?yàn)檫@有一定的誤導(dǎo)性。設(shè)想一類(lèi)較特殊的整數(shù)規(guī)劃問(wèn)題，如可行性問(wèn)題，它沒(méi)有目標(biāo)函數(shù)，只需要找到一組整數(shù)解即可完成。那么在找到整數(shù)解之前，其Gap就是100%，找到之后就是0%。如果某個(gè)啟發(fā)式（或者割平面）算法，在開(kāi)啟和關(guān)閉的的情況下，分別可以于1小時(shí)和3小時(shí)找到可行解。則如果以兩小時(shí)為觀察點(diǎn)，則可以說(shuō)在開(kāi)啟這項(xiàng)算法的前提下，實(shí)現(xiàn)的Gap提升就是無(wú)窮多倍，而若以半小時(shí)或者三個(gè)小時(shí)作為觀察點(diǎn)，則Gap沒(méi)有提升。鑒于DeepMind并未公布計(jì)算這些性能指標(biāo)的原始數(shù)據(jù)，我們無(wú)法用MIP業(yè)內(nèi)的公認(rèn)方式來(lái)對(duì)它做出評(píng)價(jià)。一般來(lái)說(shuō)，根據(jù)目前公認(rèn)的測(cè)試標(biāo)準(zhǔn)，一般是在MIPLIB的問(wèn)題集上，以兩小時(shí)為限，考慮能求解的問(wèn)題數(shù)量和平均求解時(shí)間進(jìn)行比較。

對(duì)于特定的測(cè)試集取得驚人的性能提升并不意外，因?yàn)檫@正是機(jī)器學(xué)習(xí)擅長(zhǎng)的地方：它可以捕捉同一類(lèi)問(wèn)題的特征結(jié)構(gòu)，并且給出優(yōu)化趨勢(shì)的判斷。如后文所述，我們自己在開(kāi)發(fā)的過(guò)程中也有類(lèi)似的經(jīng)歷。真正值得關(guān)注的是它在MIPLIB上的表現(xiàn)。MIPLIB 2017 由1000多個(gè)來(lái)自各行各業(yè)的實(shí)例構(gòu)成，而MIPLIB2017 Benchmark則是其中挑選的240個(gè)結(jié)構(gòu)各異的問(wèn)題組成，在篩選的時(shí)候就充分的做到了差異化，因此它和電網(wǎng)優(yōu)化和ＮＮ Verification等測(cè)試集有本質(zhì)的區(qū)別。這也解釋了在MIPLIB上算法性能提升效果并不如其他數(shù)據(jù)集明顯的原因。為了避嫌， Google也一早就在論文中表明，訓(xùn)練集用的是MIPLIB完整版的1000多個(gè)問(wèn)題，去掉這240個(gè)問(wèn)題剩余的例子。但是這依然難以避免訓(xùn)練集和測(cè)試集的結(jié)構(gòu)相似性。例如MIPLIB 2017的完整版在收集的時(shí)候，往往會(huì)從同一個(gè)來(lái)源收集多個(gè)大小不同稍有差異的算例。在遴選測(cè)評(píng)（Benchmark）集的時(shí)候，為了避免測(cè)評(píng)集的重復(fù)性，會(huì)盡量避免使用來(lái)自同一個(gè)來(lái)源的例子，這使得MIPLIB 2017 完整版中剩下的例子包含了測(cè)評(píng)（Benchmark）集的高度結(jié)構(gòu)相似問(wèn)題。如MIPLIB 2017 Benchmark中有g(shù)raph20-20-1rand這個(gè)問(wèn)題，而在MIPLIB 2017全集中有g(shù)raph-20-80-1rand, graph-40-20-1rand, graph-40-40-1rand, graph-40-80-1rand四個(gè)結(jié)構(gòu)高度類(lèi)似的問(wèn)題。因此在訓(xùn)練集上獲得的經(jīng)驗(yàn)，必然會(huì)對(duì)求解最后的測(cè)試集有幫助。而這些幫助能否泛化推廣到任何通用問(wèn)題集上，高度存疑。

分支算法與Neural Branching

分支（Branching) 算法是整數(shù)規(guī)劃求解器的核心框架。求解MIP通常需要求解多個(gè)LP（線性規(guī)劃）問(wèn)題完成。其中第一個(gè)LP問(wèn)題是原始問(wèn)題去掉全部的整數(shù)約束得來(lái)。如果第一個(gè)LP問(wèn)題的最優(yōu)解碰巧滿足整數(shù)條件，則這個(gè)解也是整數(shù)規(guī)劃的最優(yōu)解。如果LP松弛問(wèn)題的解不都滿足整數(shù)條件，則可以通過(guò)分支算法繼續(xù)尋找整數(shù)解。

分支算法通過(guò)選擇一個(gè)取值不為整數(shù)的變量x=x*進(jìn)行分支，通過(guò)分別添加x≤floor(x*)（即取值不大于x*的最大整數(shù)下界）和x≥ceil(x*)（即取值不小于x*的最小整數(shù)上界）這兩個(gè)約束來(lái)把原始問(wèn)題分解為兩個(gè)子問(wèn)題。原整數(shù)規(guī)劃問(wèn)題的最優(yōu)解一定在這兩個(gè)分支之一。接下來(lái)繼續(xù)求解這兩個(gè)新的問(wèn)題，并以此類(lèi)推，直到找到最優(yōu)的整數(shù)解或者證明整數(shù)解不存在為止。不難看出，分支算法的本質(zhì)是枚舉，在有n個(gè)0-1變量的混合整數(shù)規(guī)劃問(wèn)題里，最壞情況要遍歷所有2的n次方個(gè)分支節(jié)點(diǎn)。也因?yàn)榛旌险麛?shù)規(guī)劃問(wèn)題是個(gè)NP難問(wèn)題，所以目前精確求解的算法，基本上都基于分支算法的框架，最壞情況下復(fù)雜度是指數(shù)時(shí)間級(jí)別，耗時(shí)可能會(huì)極端漫長(zhǎng)。

在實(shí)踐中，求解整數(shù)規(guī)劃通常遠(yuǎn)不需要枚舉全部的節(jié)點(diǎn)。這是因?yàn)榉种惴梢砸砸环N更聰明的方式選擇進(jìn)行分支的變量。在眾多分支算法中，最有效果的算法是完整的強(qiáng)分支算法（Full strong branching簡(jiǎn)稱FSB）。該算法原理非常簡(jiǎn)單，即通過(guò)分別對(duì)當(dāng)前LP（線性規(guī)劃）問(wèn)題的各個(gè)取值不為整數(shù)的變量進(jìn)行分支，求解全部的分支后的LP問(wèn)題，并通過(guò)LP的目標(biāo)函數(shù)值判斷選取哪個(gè)分支是可以最快的完成MIP求解。實(shí)踐中FSB所需要的計(jì)算量非常巨大，因此對(duì)每個(gè)LP節(jié)點(diǎn)使用很不現(xiàn)實(shí)。在MIP求解過(guò)程中，會(huì)不定期的做限定循環(huán)數(shù)的Strong branching來(lái)獲取每個(gè)變量分支的最佳估計(jì)。

Google提出的Neural branching其本質(zhì)是先通過(guò)神經(jīng)網(wǎng)絡(luò)離線學(xué)習(xí)FSB的真實(shí)計(jì)算結(jié)果，再在實(shí)際應(yīng)用中模擬FSB計(jì)算，在追求FSB效果的同時(shí)，節(jié)省計(jì)算時(shí)間。其實(shí)這項(xiàng)工作過(guò)去幾年間有很多類(lèi)似的論文。Google的論文在相關(guān)工作中也提到了其他8篇相關(guān)的研究論文，多數(shù)的基本想法是比較類(lèi)似的。因此論文在這個(gè)點(diǎn)上的創(chuàng)新有一定的局限性，正如Google的論文所說(shuō)：是通過(guò)用GPU和ADMM方式大量計(jì)算原始問(wèn)題的FSB近似值，以便可以生成大量的機(jī)器學(xué)習(xí)數(shù)據(jù)。不過(guò)這也從另一個(gè)方面反應(yīng)了FSB的計(jì)算量，即使產(chǎn)生離線學(xué)習(xí)的數(shù)據(jù)，都不得不設(shè)法讓它算的更快一些。

和傳統(tǒng)的分支算法相比，Neural branching以及其他在這個(gè)方面的研究確實(shí)是（離線）機(jī)器學(xué)習(xí)和優(yōu)化算法的一種有趣的結(jié)合。但值得指出的是，經(jīng)典的分支算法，也是基于歷史數(shù)據(jù)對(duì)將來(lái)分支的預(yù)測(cè)，它的本質(zhì)也是一種在線的機(jī)器學(xué)習(xí)機(jī)制。例如在杉數(shù)求解器里，使用strong branching只是其中一項(xiàng)，此外還有偽價(jià)格(Pseudocost)、可靠性(Reliability)和推斷(Inference)等公開(kāi)和其他不公開(kāi)的判斷標(biāo)準(zhǔn)。這些算法均是通過(guò)在求解的過(guò)程中積攢信息，并以此來(lái)判斷、選擇新的分支變量等。

啟發(fā)式算法與Neural Diving

啟發(fā)式算法，是在主體的分支定界算法之外尋找整數(shù)解的算法的總稱。啟發(fā)式算法是MIP研究的一項(xiàng)熱點(diǎn)，相關(guān)的論文不勝枚舉，目前僅在SCIP中實(shí)現(xiàn)的啟發(fā)式算法就有57種之多。這些啟發(fā)式算法又大致可以分為四類(lèi)：取整（Rounding）、下潛（Diving）、子問(wèn)題（Sub-MIP）和上述三類(lèi)之外的其他算法。

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

子混合整數(shù)規(guī)劃問(wèn)題Sub-MIP）的啟發(fā)式算法是一個(gè)大類(lèi)，它通過(guò)構(gòu)造并求解子MIP問(wèn)題來(lái)尋找高質(zhì)量的整數(shù)解。在構(gòu)造子問(wèn)題的時(shí)候，又有多種構(gòu)造方式，例如：固定或縮緊變量，添加約束以及修改目標(biāo)函數(shù)值。其中如固定變量類(lèi)的算法，比較有名的有松弛導(dǎo)向鄰域搜索（Relaxation induced neighborhood search或簡(jiǎn)稱RINS），它的工作原理是當(dāng)某個(gè)整數(shù)變量在LP松弛解中的值與當(dāng)前最好整數(shù)解中的值一致，則將該變量固定在這個(gè)整數(shù)值。如果大量變量可以被固定，則可以把這個(gè)固定變量后的子問(wèn)題當(dāng)作一個(gè)全新的MIP求解，以期望可以找到高質(zhì)量的整數(shù)解。由于大量的變量被固定了，子問(wèn)題的搜索空間會(huì)變小，且預(yù)求解可以進(jìn)一步的削減問(wèn)題的規(guī)模，因此解子問(wèn)題會(huì)相對(duì)容易些。

DeepMind提出的Neural Diving這個(gè)算法，是通過(guò)機(jī)器學(xué)習(xí)和神經(jīng)網(wǎng)絡(luò)，給定一個(gè)問(wèn)題結(jié)構(gòu)，預(yù)判如何固定部分整數(shù)變量的取值，然后去求解子MIP。因此，盡管用到了Diving這個(gè)詞，但是我們認(rèn)為它還是可以歸類(lèi)為求解子問(wèn)題的啟發(fā)式算法?？梢钥闯鲞@個(gè)算法在原理上和上述的RINS有諸多相似之處，只是固定變量的方式不同。

雖然思路和很多既有啟發(fā)式算法形式類(lèi)似，但Neural Diving還是有它的獨(dú)特之處。Neural Diving最大的優(yōu)勢(shì)之一，是它可以在正式求解原始問(wèn)題之前，即生成多組差異化的部分變量取值，啟動(dòng)啟發(fā)式算法。這一方面提升了該算法找到高質(zhì)量整數(shù)解的成功率，另一方面也提前了找到整數(shù)解的時(shí)間，因此可以較早的獲得較小的Gap。我們也認(rèn)為這是DeepMind這篇論文的最有價(jià)值的部分。

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

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

例如求解子MIP的啟發(fā)式算法，是一個(gè)有效但非常耗時(shí)的算法。我們?cè)陂_(kāi)發(fā)的過(guò)程中，求解大量的子問(wèn)題，提取子問(wèn)題特征（例如再次預(yù)求解效果，變量種類(lèi)等），交給機(jī)器學(xué)習(xí)幫助判斷預(yù)測(cè)某個(gè)子問(wèn)題是否值得花時(shí)間啟動(dòng)求解，避開(kāi)耗時(shí)且無(wú)效的方法，提升求解速度。

此外我們的線性規(guī)劃LP求解器開(kāi)發(fā)也得益于機(jī)器學(xué)習(xí)。例如我們對(duì)部分有特殊結(jié)構(gòu)的LP使用機(jī)器學(xué)習(xí)的方式，預(yù)測(cè)一個(gè)變量是否在最優(yōu)解的基解的一部分，并通過(guò)小幅的目標(biāo)函數(shù)擾動(dòng)將這個(gè)預(yù)測(cè)結(jié)果應(yīng)用到LP問(wèn)題上，實(shí)現(xiàn)快速求解。

除以上內(nèi)嵌在求解器內(nèi)部的機(jī)器學(xué)習(xí)成果之外，在過(guò)去幾年里，杉數(shù)在使用求解器解決多個(gè)行業(yè)的困難問(wèn)題時(shí)，也從機(jī)器學(xué)習(xí)，深度學(xué)習(xí)，強(qiáng)化學(xué)習(xí)中獲益很大。

一個(gè)例子是國(guó)家電網(wǎng)安全約束機(jī)組組合問(wèn)題（Security Constrained Unit Commitment簡(jiǎn)稱SCUC）問(wèn)題。SCUC問(wèn)題的特點(diǎn)是規(guī)模不大，但是要求快速求解。我們遇到的實(shí)際問(wèn)題只有數(shù)千個(gè)整數(shù)變量，需要求每隔15分鐘求解一次，并且要在15分鐘內(nèi)盡快解完。我們通過(guò)深度神經(jīng)網(wǎng)絡(luò)等機(jī)器學(xué)習(xí)的方法去預(yù)測(cè)MIP模型最優(yōu)解中每個(gè)決策變量取1的概率，從而固定部分置信度最高的變量和對(duì)中間置信度的部分變量添加多變量分支的割平面，使得最后的問(wèn)題可行的概率最高。這樣的方法能夠有效減少分支定界樹(shù)的搜索規(guī)模，一方面能夠?qū)崿F(xiàn)快速收斂，另一方面能夠快速尋找到高質(zhì)量的初始解。最后的實(shí)驗(yàn)顯示，借助該方法在達(dá)到相同質(zhì)量解(Gap=0.01%)的速度提升為5-10倍左右。其中不乏有原始問(wèn)題3分鐘無(wú)法完成求解，而結(jié)合使用機(jī)器學(xué)習(xí)算法僅需10秒就能完成求解的時(shí)候。這種速度的提升對(duì)需要每15分鐘都需要快速計(jì)算決策的SCUC問(wèn)題非常重要。

電網(wǎng)中的優(yōu)化也是DeepMind指出的智能化MIP可以重點(diǎn)發(fā)力的領(lǐng)域。但是，值得著重指出的是，電網(wǎng)另一個(gè)特性就是對(duì)于安全性和魯棒性的極端要求。而在新問(wèn)題的數(shù)據(jù)結(jié)構(gòu)突發(fā)巨變，歷史數(shù)據(jù)已經(jīng)不能指導(dǎo)未來(lái)的時(shí)候，例如戰(zhàn)爭(zhēng)，自然或者人為因素導(dǎo)致的發(fā)電廠和輸電線路的極大變化，機(jī)器學(xué)習(xí)能起到的作用會(huì)弱化很多。這個(gè)時(shí)候，更多的時(shí)候還是依靠MIP求解器自身六個(gè)模塊那些獨(dú)立于數(shù)據(jù)之外的經(jīng)典算法的實(shí)現(xiàn)能力。

另一個(gè)例子是中國(guó)郵政的路由網(wǎng)絡(luò)規(guī)劃問(wèn)題。我們?cè)趯?shí)踐中遇到的此類(lèi)問(wèn)題通常需要求解數(shù)十萬(wàn)整數(shù)變量的MIP來(lái)決定發(fā)車(chē)安排。如果直接拋給求解器，則往往需要花費(fèi)一至兩個(gè)小時(shí)才能找到第一個(gè)整數(shù)解（Gap在30%左右甚至更差）。通過(guò)觀察，我們發(fā)現(xiàn)盡管無(wú)法預(yù)測(cè)全部的發(fā)車(chē)安排，但是可以預(yù)測(cè)部分高概率的車(chē)輛安排。我們進(jìn)而通過(guò)機(jī)器學(xué)習(xí)歷史數(shù)據(jù)，形成了一套根據(jù)線性約束關(guān)系生成數(shù)千發(fā)車(chē)安排的部分初始解的方法。在此基礎(chǔ)上，我們通過(guò)臨時(shí)固定這些決策變量，構(gòu)造子MIP問(wèn)題，用求解器快速的計(jì)算、補(bǔ)全子問(wèn)題的解。這個(gè)子問(wèn)題由于部分關(guān)鍵變量確定，使得預(yù)求解模塊可以對(duì)問(wèn)題規(guī)模進(jìn)行大幅度的削減，促成快速求解。盡管這個(gè)子問(wèn)題的最優(yōu)解不是原始問(wèn)題的最優(yōu)解，但在實(shí)踐中這個(gè)解（Gap在10%之內(nèi)）明顯優(yōu)于花費(fèi)一至兩小時(shí)算出的第一個(gè)可行解。而從預(yù)測(cè)到解子問(wèn)題，通常只需要不到1分鐘的時(shí)間。因此可以說(shuō)，機(jī)器學(xué)習(xí)幫助我們以50倍的速度提升找到了同等質(zhì)量（其實(shí)是更好）的整數(shù)解。

另一個(gè)更有廣泛意義的例子是，在近期的科研論文與多個(gè)號(hào)稱從事智能決策公司的宣稱中，可以看到一些諸如車(chē)輛調(diào)遣，路線規(guī)劃等交通類(lèi)問(wèn)題，因?yàn)槠涫录l次高，數(shù)據(jù)結(jié)構(gòu)相對(duì)穩(wěn)定，所以無(wú)論是分支策略，初始解固定，甚至割平面產(chǎn)生，都可以通過(guò)機(jī)器學(xué)習(xí)技術(shù)獲得，從而加速問(wèn)題的MIP模型求解。而且也確實(shí)有很多學(xué)者在這個(gè)問(wèn)題上取得了相對(duì)多的進(jìn)展。因此，交通領(lǐng)域也是機(jī)器學(xué)習(xí)，智能決策等技術(shù)近些年來(lái)一直關(guān)注的領(lǐng)域。

其實(shí)，不僅僅是路線規(guī)劃。在五年前，杉數(shù)就曾經(jīng)與某國(guó)內(nèi)最大的出行平臺(tái)合作，考慮過(guò)司機(jī)與乘客的智能動(dòng)態(tài)匹配系統(tǒng)，問(wèn)題從最開(kāi)始的單純機(jī)器學(xué)習(xí)計(jì)算匹配系數(shù)，進(jìn)行啟發(fā)式算法分配，到后來(lái)進(jìn)行全城的時(shí)間切片網(wǎng)絡(luò)流匹配，再到將削峰填谷，智慧出行的理念融合，建立起整個(gè)系統(tǒng)的動(dòng)態(tài)規(guī)劃模型，并在強(qiáng)化學(xué)習(xí)框架下，進(jìn)行未來(lái)趨勢(shì)與決策的近似方法，最后得到一個(gè)在時(shí)間和空間上都接近全局優(yōu)化的方案。整個(gè)系統(tǒng)隨著數(shù)據(jù)的完備，算力的到位，在雙方攜手建立的強(qiáng)化學(xué)習(xí)框架下不斷進(jìn)化，從簡(jiǎn)單的線性函數(shù)逼近到神經(jīng)網(wǎng)絡(luò)近似，越發(fā)智能與精準(zhǔn)，在2017年的時(shí)候，就已經(jīng)得到了廣泛的應(yīng)用，創(chuàng)造了極大的經(jīng)濟(jì)效益與社會(huì)效益。

結(jié)語(yǔ)：

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

在今天討論的這個(gè)例子里，簡(jiǎn)單地說(shuō)，神經(jīng)網(wǎng)絡(luò)和機(jī)器學(xué)習(xí)技術(shù)進(jìn)展，更像是給MIP開(kāi)發(fā)的六大模塊中的兩個(gè)模塊探索的武器庫(kù)增加了一些昂貴（算力資源需求）而有力的武器，豐富了這些模塊加速的能力，遠(yuǎn)遠(yuǎn)談不上攻破OR。這些技術(shù)展示出來(lái)的潛力是值得歡呼的，但是在現(xiàn)實(shí)中求解MIP問(wèn)題，需要的數(shù)學(xué)技巧和工程經(jīng)驗(yàn)是極其厚重的。

傳統(tǒng)的MIP求解工具有數(shù)十年的理論論證和理論分析基礎(chǔ)。相較之下，MIP求解中的機(jī)器學(xué)習(xí)工具因其模型結(jié)構(gòu)的復(fù)雜性，理論論證成果較少。大量的相關(guān)機(jī)器學(xué)習(xí)研究都是依靠某一類(lèi)或者某幾類(lèi)的數(shù)據(jù)集的數(shù)值實(shí)驗(yàn)結(jié)果用以驗(yàn)證其有效性。所以機(jī)器學(xué)習(xí)方法對(duì)現(xiàn)實(shí)中一般性問(wèn)題求解的可靠性還有待進(jìn)一步的論證。另一方面，絕大多數(shù)機(jī)器學(xué)習(xí)的算法設(shè)計(jì)是需要將模型轉(zhuǎn)化成經(jīng)典的整數(shù)，線性，凸或者非凸數(shù)學(xué)規(guī)劃模型，再對(duì)其分析的。

回到MIP，可以說(shuō)利用機(jī)器學(xué)習(xí)進(jìn)行某些點(diǎn)上的突破是遠(yuǎn)遠(yuǎn)不夠的。一般性的整數(shù)規(guī)劃乃至廣大的NP難問(wèn)題，在真正的顛覆性技術(shù)突破之前（比如量子計(jì)算機(jī)的真正實(shí)用化），依然可預(yù)期在未來(lái)很多年，會(huì)是人類(lèi)智力的極限之一。

說(shuō)明：此文寫(xiě)作中獲得了香港中文大學(xué)（深圳）王子卓、斯坦福大學(xué)葉蔭宇、紐約大學(xué)陳溪、約翰霍普金斯大學(xué)江弘億等多位學(xué)者的指導(dǎo)和建議，在此一并表示感謝。

作者簡(jiǎn)介：

皇甫琦，杉數(shù)科技副總裁，博士畢業(yè)于愛(ài)丁堡大學(xué)優(yōu)化算法方向。曾在XPRESS求解器工作多年，數(shù)學(xué)規(guī)劃求解器開(kāi)發(fā)領(lǐng)域的資深專家，曾獲得國(guó)際著名優(yōu)化期刊Mathematical Programming Computation的年度最佳論文獎(jiǎng)（2018），Computational Optimization and Applications的年度最佳論文獎(jiǎng)（2015）。

葛冬冬，杉數(shù)科技聯(lián)合創(chuàng)始人&首席科學(xué)官，上海財(cái)經(jīng)大學(xué)交叉科學(xué)研究院院長(zhǎng)、教授。博士畢業(yè)于斯坦福大學(xué)運(yùn)籌學(xué)專業(yè)。開(kāi)源求解器項(xiàng)目LEAVES和商業(yè)求解器項(xiàng)目COPT的負(fù)責(zé)人。在人工智能，理論計(jì)算機(jī)，運(yùn)籌學(xué)的期刊和會(huì)議NeurIPS，ICML，F(xiàn)OCS，SODA，Operations Research，Mathematical Programming等發(fā)表過(guò)多篇論文。

分享到