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

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

"This is suber cool!"

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

"攻破OR(運籌學)只是時間問題"

而一些實踐派已經(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ù)規(guī)劃結合在一起并不是一個新課題。為什么Google的這篇論文引起這么大的關注。Google和DeepMind團隊的名氣當然是最大的因素，從圍棋的AlphaGo到最近的蛋白質(zhì)結構預測的AlphaFold2，DeepMind的每次出手都是風口浪尖上的大動作，也確實在某些領域帶來過突破性的進展。但這篇論文是否有顛覆性的研究成果，以至于可以“攻破OR(運籌學)”?

DeepMind并沒有回應開源這部分代碼的要求，因此想要看看他們的工作只能讀論文。這篇論文的原文可在arXiv獲?。?/p>

杉數(shù)科技的COPT求解器開發(fā)團隊詳細地學習、研究了這篇論文。在此我們把團隊的分析討論奉上，以資對機器學習和優(yōu)化算法結合做進一步探討。

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

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

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

1

DeepMind論文求解結果分析

DeepMind的論文引起了廣泛的關注，并不止因為團隊的名聲，也來自于論文中報告了非常驚人的性能提升數(shù)據(jù)。如論文摘要中提到的，對于測過的5組問題里，在3組上分別實現(xiàn)了1.5倍，2倍，以及1萬倍的更好的Gap。

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

對于特定的測試集取得驚人的性能提升并不意外，因為這正是機器學習擅長的地方：它可以捕捉同一類問題的特征結構，并且給出優(yōu)化趨勢的判斷。如后文所述，我們自己在開發(fā)的過程中也有類似的經(jīng)歷。真正值得關注的是它在MIPLIB上的表現(xiàn)。MIPLIB 2017 由1000多個來自各行各業(yè)的實例構成，而MIPLIB2017 Benchmark則是其中挑選的240個結構各異的問題組成，在篩選的時候就充分的做到了差異化，因此它和電網(wǎng)優(yōu)化和NN Verification等測試集有本質(zhì)的區(qū)別。這也解釋了在MIPLIB上算法性能提升效果并不如其他數(shù)據(jù)集明顯的原因。

為了避嫌， Google也一早就在論文中表明，訓練集用的是MIPLIB完整版的1000多個問題，去掉這240個問題剩余的例子。但是這依然難以避免訓練集和測試集的結構相似性。例如MIPLIB 2017的完整版在收集的時候，往往會從同一個來源收集多個大小不同稍有差異的算例。在遴選測評(Benchmark)集的時候，為了避免測評集的重復性，會盡量避免使用來自同一個來源的例子，這使得MIPLIB 2017 完整版中剩下的例子包含了測評(Benchmark)集的高度結構相似問題。如MIPLIB 2017 Benchmark中有graph20-20-1rand這個問題，而在MIPLIB2017全集中有graph-20-80-1rand,graph-40-20-1rand,graph-40-40-1rand,graph-40-80-1rand四個結構高度類似的問題。因此在訓練集上獲得的經(jīng)驗，必然會對求解最后的測試集有幫助。而這些幫助能否泛化推廣到任何通用問題集上，高度存疑。

2

分支算法與Neural Branching

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

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

在實踐中，求解整數(shù)規(guī)劃通常遠不需要枚舉全部的節(jié)點。這是因為分支算法可以以一種更聰明的方式選擇進行分支的變量。在眾多分支算法中，最有效果的算法是完整的強分支算法(Full strong branching簡稱FSB)。該算法原理非常簡單，即通過分別對當前LP(線性規(guī)劃)問題的各個取值不為整數(shù)的變量進行分支，求解全部的分支后的LP問題，并通過LP的目標函數(shù)值判斷選取哪個分支是可以最快的完成MIP求解。實踐中FSB所需要的計算量非常巨大，因此對每個LP節(jié)點使用很不現(xiàn)實。在MIP求解過程中，會不定期的做限定循環(huán)數(shù)的Strongbranching來獲取每個變量分支的最佳估計。

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

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

3

啟發(fā)式算法與NeuralDiving

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

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

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

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

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

4

人工智能與MIP結合的實例應用

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

例如求解子MIP的啟發(fā)式算法，是一個有效但非常耗時的算法。我們在開發(fā)的過程中，求解大量的子問題，提取子問題特征(例如再次預求解效果，變量種類等)，交給機器學習幫助判斷預測某個子問題是否值得花時間啟動求解，避開耗時且無效的方法，提升求解速度。

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

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

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

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

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

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

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

5

結語

最后，我們想強調(diào)，如"機器學習之父"MichaelJordan指出的，未來的人工智能最重要的突破應該與優(yōu)化算法緊密結合。而這正是運籌學的核心基礎。

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

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

回到MIP，可以說利用機器學習進行某些點上的突破是遠遠不夠的。一般性的整數(shù)規(guī)劃乃至廣大的NP難問題，在真正的顛覆性技術突破之前(比如量子計算機的真正實用化)，依然可預期在未來很多年，會是人類智力的極限之一。

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