本文經(jīng)AI新媒體量子位（公眾號ID:QbitAI）授權(quán)轉(zhuǎn)載，轉(zhuǎn)載請聯(lián)系出處。

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

Google的DeepMind團(tuán)隊(duì)最近官宣了一篇神經(jīng)網(wǎng)絡(luò)（Neural Networks）求解MIP論文。

一石激起千層浪，在國內(nèi)外的運(yùn)籌優(yōu)化社群引起了討論。

[[417732]]

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

This is uber cool.

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

攻破OR（運(yùn)籌學(xué)）只是時間問題。

而一些實(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é)合在一起并不是一個新課題。

而為什么Google的這篇論文引起這么大的關(guān)注？

Google和DeepMind團(tuán)隊(duì)的名氣當(dāng)然是最大的因素，從圍棋的AlphaGo到最近的蛋白質(zhì)結(jié)構(gòu)預(yù)測的AlphaFold2，DeepMind的每次出手都是風(fēng)口浪尖上的大動作，也確實(shí)在某些領(lǐng)域帶來過突破性的進(jìn)展。

但這篇論文是否有顛覆性的研究成果，以至于可以“攻破OR（運(yùn)籌學(xué)）”？

DeepMind并沒有回應(yīng)開源這部分代碼的要求，因此想要看看他們的工作只能讀論文。

杉數(shù)科技的COPT求解器開發(fā)團(tuán)隊(duì)詳細(xì)地學(xué)習(xí)、研究了這篇論文。

在此我們把團(tuán)隊(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ī)劃也是非常困難的問題，在計(jì)算機(jī)的復(fù)雜性理論上，是屬于NP難問題類的，也是美國庫蘭所公布的數(shù)學(xué)七個千年大獎難題之一，對于此類問題，是否存在多項(xiàng)式時間的精確求解算法，至今仍未有定論。

求解整數(shù)規(guī)劃的主要算法部件有：預(yù)求解、分支定界、啟發(fā)式算法、割平面、沖突分析和線性規(guī)劃求解器等模塊。

鑒于DeepMind此次的論文主要涉及分支算法和啟發(fā)式算法，我們分別重點(diǎn)從這兩個方向進(jìn)行探討。

下文會對DeepMind的基本結(jié)論先做一個分析，然后分別就DeepMind論文中提到的Neural Branching和Neural Diving這兩項(xiàng)成果，介紹混合整數(shù)規(guī)劃相關(guān)的背景知識，然后對比分析論文中的新思路和傳統(tǒng)算法的關(guān)系。

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

DeepMind的論文引起了廣泛的關(guān)注，并不止因?yàn)閳F(tuán)隊(duì)的名聲，也來自于論文中報(bào)告了非常驚人的性能提升數(shù)據(jù)。

如論文摘要中提到的，對于測過的5組問題里，在3組上分別實(shí)現(xiàn)了1.5倍，2倍，以及1萬倍的更好的Gap。

其實(shí)這里玩了一個小小的文字游戲。

作為MIP求解器開發(fā)人員，一般不把一定時間內(nèi)能拿到的Gap作為主要衡量標(biāo)準(zhǔn)。

因?yàn)檫@有一定的誤導(dǎo)性。設(shè)想一類較特殊的整數(shù)規(guī)劃問題，如可行性問題，它沒有目標(biāo)函數(shù)，只需要找到一組整數(shù)解即可完成。

那么在找到整數(shù)解之前，其Gap就是100%，找到之后就是0%。如果某個啟發(fā)式（或者割平面）算法，在開啟和關(guān)閉的的情況下，分別可以于1小時和3小時找到可行解。

則如果以兩小時為觀察點(diǎn)，則可以說在開啟這項(xiàng)算法的前提下，實(shí)現(xiàn)的Gap提升就是無窮多倍，而若以半小時或者三個小時作為觀察點(diǎn)，則Gap沒有提升。

鑒于DeepMind并未公布計(jì)算這些性能指標(biāo)的原始數(shù)據(jù)，我們無法用MIP業(yè)內(nèi)的公認(rèn)方式來對它做出評價(jià)。

一般來說，根據(jù)目前公認(rèn)的測試標(biāo)準(zhǔn)，一般是在MIPLIB的問題集上，以兩小時為限，考慮能求解的問題數(shù)量和平均求解時間進(jìn)行比較。

對于特定的測試集取得驚人的性能提升并不意外，因?yàn)檫@正是機(jī)器學(xué)習(xí)擅長的地方：它可以捕捉同一類問題的特征結(jié)構(gòu)，并且給出優(yōu)化趨勢的判斷。

如后文所述，我們自己在開發(fā)的過程中也有類似的經(jīng)歷。真正值得關(guān)注的是它在MIPLIB上的表現(xiàn)。

MIPLIB 2017 由1000多個來自各行各業(yè)的實(shí)例構(gòu)成，而MIPLIB2017 Benchmark則是其中挑選的240個結(jié)構(gòu)各異的問題組成，在篩選的時候就充分的做到了差異化，因此它和電網(wǎng)優(yōu)化和ＮＮ Verification等測試集有本質(zhì)的區(qū)別。

這也解釋了在MIPLIB上算法性能提升效果并不如其他數(shù)據(jù)集明顯的原因。

為了避嫌， Google也一早就在論文中表明，訓(xùn)練集用的是MIPLIB完整版的1000多個問題，去掉這240個問題剩余的例子。但是這依然難以避免訓(xùn)練集和測試集的結(jié)構(gòu)相似性。

例如MIPLIB 2017的完整版在收集的時候，往往會從同一個來源收集多個大小不同稍有差異的算例。在遴選測評（Benchmark）集的時候，為了避免測評集的重復(fù)性，會盡量避免使用來自同一個來源的例子，這使得MIPLIB 2017 完整版中剩下的例子包含了測評（Benchmark）集的高度結(jié)構(gòu)相似問題。

如MIPLIB 2017 Benchmark中有g(shù)raph20-20-1rand這個問題，而在MIPLIB 2017全集中有g(shù)raph-20-80-1rand, graph-40-20-1rand, graph-40-40-1rand, graph-40-80-1rand四個結(jié)構(gòu)高度類似的問題。

因此在訓(xùn)練集上獲得的經(jīng)驗(yàn)，必然會對求解最后的測試集有幫助。而這些幫助能否泛化推廣到任何通用問題集上，高度存疑。

分支算法與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進(jìn)行分支，通過分別添加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é)點(diǎn)。

也因?yàn)榛旌险麛?shù)規(guī)劃問題是個NP難問題，所以目前精確求解的算法，基本上都基于分支算法的框架，最壞情況下復(fù)雜度是指數(shù)時間級別，耗時可能會極端漫長。

在實(shí)踐中，求解整數(shù)規(guī)劃通常遠(yuǎn)不需要枚舉全部的節(jié)點(diǎn)。

這是因?yàn)榉种惴梢砸砸环N更聰明的方式選擇進(jìn)行分支的變量。在眾多分支算法中，最有效果的算法是完整的強(qiáng)分支算法（Full strong branching簡稱FSB）。

該算法原理非常簡單，即通過分別對當(dāng)前LP（線性規(guī)劃）問題的各個取值不為整數(shù)的變量進(jìn)行分支，求解全部的分支后的LP問題，并通過LP的目標(biāo)函數(shù)值判斷選取哪個分支是可以最快的完成MIP求解。

實(shí)踐中FSB所需要的計(jì)算量非常巨大，因此對每個LP節(jié)點(diǎn)使用很不現(xiàn)實(shí)。在MIP求解過程中，會不定期的做限定循環(huán)數(shù)的Strong branching來獲取每個變量分支的最佳估計(jì)。

Google提出的Neural branching其本質(zhì)是先通過神經(jīng)網(wǎng)絡(luò)離線學(xué)習(xí)FSB的真實(shí)計(jì)算結(jié)果，再在實(shí)際應(yīng)用中模擬FSB計(jì)算，在追求FSB效果的同時，節(jié)省計(jì)算時間。

其實(shí)這項(xiàng)工作過去幾年間有很多類似的論文。

Google的論文在相關(guān)工作中也提到了其他8篇相關(guān)的研究論文，多數(shù)的基本想法是比較類似的。因此論文在這個點(diǎn)上的創(chuàng)新有一定的局限性，正如Google的論文所說：

是通過用GPU和ADMM方式大量計(jì)算原始問題的FSB近似值，以便可以生成大量的機(jī)器學(xué)習(xí)數(shù)據(jù)。

不過這也從另一個方面反應(yīng)了FSB的計(jì)算量，即使產(chǎn)生離線學(xué)習(xí)的數(shù)據(jù)，都不得不設(shè)法讓它算的更快一些。

和傳統(tǒng)的分支算法相比，Neural branching以及其他在這個方面的研究確實(shí)是（離線）機(jī)器學(xué)習(xí)和優(yōu)化算法的一種有趣的結(jié)合。

但值得指出的是，經(jīng)典的分支算法，也是基于歷史數(shù)據(jù)對將來分支的預(yù)測，它的本質(zhì)也是一種在線的機(jī)器學(xué)習(xí)機(jī)制。

例如在杉數(shù)求解器里，使用strong branching只是其中一項(xiàng)，此外還有偽價(jià)格（Pseudocost）、可靠性（Reliability）和推斷（Inference）等公開和其他不公開的判斷標(biāo)準(zhǔn)。

這些算法均是通過在求解的過程中積攢信息，并以此來判斷、選擇新的分支變量等。

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

啟發(fā)式算法，是在主體的分支定界算法之外尋找整數(shù)解的算法的總稱。

啟發(fā)式算法是MIP研究的一項(xiàng)熱點(diǎn)，相關(guān)的論文不勝枚舉，目前僅在SCIP中實(shí)現(xiàn)的啟發(fā)式算法就有57種之多。

這些啟發(fā)式算法又大致可以分為四類：取整（Rounding）、下潛（Diving）、子問題（Sub-MIP）和上述三類之外的其他算法。

取整（Rounding）啟發(fā)式算法顧名思義，是在LP松弛解不滿足整數(shù)約束時，對不滿足的變量進(jìn)行取整，以期望獲得整數(shù)解。

下潛（Diving）啟發(fā)式算法的本質(zhì)是深度優(yōu)先搜索，它在LP松弛解不滿足整數(shù)約束時，從當(dāng)前節(jié)點(diǎn)出發(fā)，不斷的選取最佳分支進(jìn)行深度優(yōu)先搜索，直到找到整數(shù)解或證明子問題為不可行為止。

這兩類算法雖然原理簡單，但是也都有多種實(shí)現(xiàn)變種，在這里不展開討論。

子混合整數(shù)規(guī)劃問題（Sub-MIP）的啟發(fā)式算法是一個大類，它通過構(gòu)造并求解子MIP問題來尋找高質(zhì)量的整數(shù)解。

在構(gòu)造子問題的時候，又有多種構(gòu)造方式，例如：固定或縮緊變量，添加約束以及修改目標(biāo)函數(shù)值。

其中如固定變量類的算法，比較有名的有松弛導(dǎo)向鄰域搜索（Relaxation induced neighborhood search或簡稱RINS），它的工作原理是當(dāng)某個整數(shù)變量在LP松弛解中的值與當(dāng)前最好整數(shù)解中的值一致，則將該變量固定在這個整數(shù)值。

如果大量變量可以被固定，則可以把這個固定變量后的子問題當(dāng)作一個全新的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有諸多相似之處，只是固定變量的方式不同。

雖然思路和很多既有啟發(fā)式算法形式類似，但Neural Diving還是有它的獨(dú)特之處。Neural Diving最大的優(yōu)勢之一，是它可以在正式求解原始問題之前，即生成多組差異化的部分變量取值，啟動啟發(fā)式算法。

這一方面提升了該算法找到高質(zhì)量整數(shù)解的成功率，另一方面也提前了找到整數(shù)解的時間，因此可以較早的獲得較小的Gap。我們也認(rèn)為這是DeepMind這篇論文的最有價(jià)值的部分。

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

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

例如求解子MIP的啟發(fā)式算法，是一個有效但非常耗時的算法。

我們在開發(fā)的過程中，求解大量的子問題，提取子問題特征（例如再次預(yù)求解效果，變量種類等），交給機(jī)器學(xué)習(xí)幫助判斷預(yù)測某個子問題是否值得花時間啟動求解，避開耗時且無效的方法，提升求解速度。

此外我們的線性規(guī)劃LP求解器開發(fā)也得益于機(jī)器學(xué)習(xí)。

例如我們對部分有特殊結(jié)構(gòu)的LP使用機(jī)器學(xué)習(xí)的方式，預(yù)測一個變量是否在最優(yōu)解的基解的一部分，并通過小幅的目標(biāo)函數(shù)擾動將這個預(yù)測結(jié)果應(yīng)用到LP問題上，實(shí)現(xiàn)快速求解。

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

一個例子是國家電網(wǎng)安全約束機(jī)組組合問題（Security Constrained Unit Commitment簡稱SCUC）問題。

SCUC問題的特點(diǎn)是規(guī)模不大，但是要求快速求解。我們遇到的實(shí)際問題只有數(shù)千個整數(shù)變量，需要求每隔15分鐘求解一次，并且要在15分鐘內(nèi)盡快解完。

我們通過深度神經(jīng)網(wǎng)絡(luò)等機(jī)器學(xué)習(xí)的方法去預(yù)測MIP模型最優(yōu)解中每個決策變量取1的概率，從而固定部分置信度最高的變量和對中間置信度的部分變量添加多變量分支的割平面，使得最后的問題可行的概率最高。

這樣的方法能夠有效減少分支定界樹的搜索規(guī)模，一方面能夠?qū)崿F(xiàn)快速收斂，另一方面能夠快速尋找到高質(zhì)量的初始解。

最后的實(shí)驗(yàn)顯示，借助該方法在達(dá)到相同質(zhì)量解（Gap=0.01%）的速度提升為5-10倍左右。

其中不乏有原始問題3分鐘無法完成求解，而結(jié)合使用機(jī)器學(xué)習(xí)算法僅需10秒就能完成求解的時候。這種速度的提升對需要每15分鐘都需要快速計(jì)算決策的SCUC問題非常重要。

電網(wǎng)中的優(yōu)化也是DeepMind指出的智能化MIP可以重點(diǎn)發(fā)力的領(lǐng)域。

但是，值得著重指出的是，電網(wǎng)另一個特性就是對于安全性和魯棒性的極端要求。

而在新問題的數(shù)據(jù)結(jié)構(gòu)突發(fā)巨變，歷史數(shù)據(jù)已經(jīng)不能指導(dǎo)未來的時候，例如戰(zhàn)爭，自然或者人為因素導(dǎo)致的發(fā)電廠和輸電線路的極大變化，機(jī)器學(xué)習(xí)能起到的作用會弱化很多。

這個時候，更多的時候還是依靠MIP求解器自身六個模塊那些獨(dú)立于數(shù)據(jù)之外的經(jīng)典算法的實(shí)現(xiàn)能力。

另一個例子是中國郵政的路由網(wǎng)絡(luò)規(guī)劃問題。

我們在實(shí)踐中遇到的此類問題通常需要求解數(shù)十萬整數(shù)變量的MIP來決定發(fā)車安排。如果直接拋給求解器，則往往需要花費(fèi)一至兩個小時才能找到第一個整數(shù)解（Gap在30%左右甚至更差）。

通過觀察，我們發(fā)現(xiàn)盡管無法預(yù)測全部的發(fā)車安排，但是可以預(yù)測部分高概率的車輛安排。我們進(jìn)而通過機(jī)器學(xué)習(xí)歷史數(shù)據(jù)，形成了一套根據(jù)線性約束關(guān)系生成數(shù)千發(fā)車安排的部分初始解的方法。

在此基礎(chǔ)上，我們通過臨時固定這些決策變量，構(gòu)造子MIP問題，用求解器快速的計(jì)算、補(bǔ)全子問題的解。這個子問題由于部分關(guān)鍵變量確定，使得預(yù)求解模塊可以對問題規(guī)模進(jìn)行大幅度的削減，促成快速求解。

盡管這個子問題的最優(yōu)解不是原始問題的最優(yōu)解，但在實(shí)踐中這個解（Gap在10%之內(nèi)）明顯優(yōu)于花費(fèi)一至兩小時算出的第一個可行解。

而從預(yù)測到解子問題，通常只需要不到1分鐘的時間。因此可以說，機(jī)器學(xué)習(xí)幫助我們以50倍的速度提升找到了同等質(zhì)量（其實(shí)是更好）的整數(shù)解。

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

而且也確實(shí)有很多學(xué)者在這個問題上取得了相對多的進(jìn)展。

因此，交通領(lǐng)域也是機(jī)器學(xué)習(xí)，智能決策等技術(shù)近些年來一直關(guān)注的領(lǐng)域。

其實(shí)，不僅僅是路線規(guī)劃。

在五年前，杉數(shù)就曾經(jīng)與某國內(nèi)最大的出行平臺合作，考慮過司機(jī)與乘客的智能動態(tài)匹配系統(tǒng)，問題從最開始的單純機(jī)器學(xué)習(xí)計(jì)算匹配系數(shù)，進(jìn)行啟發(fā)式算法分配，到后來進(jìn)行全城的時間切片網(wǎng)絡(luò)流匹配，再到將削峰填谷，智慧出行的理念融合，建立起整個系統(tǒng)的動態(tài)規(guī)劃模型，并在強(qiáng)化學(xué)習(xí)框架下，進(jìn)行未來趨勢與決策的近似方法，最后得到一個在時間和空間上都接近全局優(yōu)化的方案。

整個系統(tǒng)隨著數(shù)據(jù)的完備，算力的到位，在雙方攜手建立的強(qiáng)化學(xué)習(xí)框架下不斷進(jìn)化，從簡單的線性函數(shù)逼近到神經(jīng)網(wǎng)絡(luò)近似，越發(fā)智能與精準(zhǔn)，在2017年的時候，就已經(jīng)得到了廣泛的應(yīng)用，創(chuàng)造了極大的經(jīng)濟(jì)效益與社會效益。

結(jié)語

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

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

傳統(tǒng)的MIP求解工具有數(shù)十年的理論論證和理論分析基礎(chǔ)。相較之下，MIP求解中的機(jī)器學(xué)習(xí)工具因其模型結(jié)構(gòu)的復(fù)雜性，理論論證成果較少。

大量的相關(guān)機(jī)器學(xué)習(xí)研究都是依靠某一類或者某幾類的數(shù)據(jù)集的數(shù)值實(shí)驗(yàn)結(jié)果用以驗(yàn)證其有效性。所以機(jī)器學(xué)習(xí)方法對現(xiàn)實(shí)中一般性問題求解的可靠性還有待進(jìn)一步的論證。

另一方面，絕大多數(shù)機(jī)器學(xué)習(xí)的算法設(shè)計(jì)是需要將模型轉(zhuǎn)化成經(jīng)典的整數(shù)，線性，凸或者非凸數(shù)學(xué)規(guī)劃模型，再對其分析的。

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

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

作者簡介

皇甫琦，杉數(shù)科技副總裁，博士畢業(yè)于愛丁堡大學(xué)優(yōu)化算法方向。

曾在XPRESS求解器工作多年，數(shù)學(xué)規(guī)劃求解器開發(fā)領(lǐng)域的資深專家，曾獲得國際著名優(yōu)化期刊Mathematical Programming Computation的年度最佳論文獎（2018），Computational Optimization and Applications的年度最佳論文獎（2015）。

葛冬冬，杉數(shù)科技聯(lián)合創(chuàng)始人&首席科學(xué)官，上海財(cái)經(jīng)大學(xué)交叉科學(xué)研究院院長、教授。

博士畢業(yè)于斯坦福大學(xué)運(yùn)籌學(xué)專業(yè)。開源求解器項(xiàng)目LEAVES和商業(yè)求解器項(xiàng)目COPT的負(fù)責(zé)人。在人工智能，理論計(jì)算機(jī)，運(yùn)籌學(xué)的期刊和會議NeurIPS，ICML，F(xiàn)OCS，SODA，Operations Research，Mathematical Programming等發(fā)表過多篇論文。

論文地址：

https://arxiv.org/abs/2012.13349