<mark id="oztn4"></mark>
0
| 本文作者： 我在思考中 | 2021-08-16 14:14 |
作者 | 皇甫琦、葛冬冬、杉數科技COPT開發組
Google的DeepMind團隊最近官宣了一篇神經網絡(Neural Networks)求解MIP論文。一石激起千層浪，在國內外的運籌優化社群引起了討論。
部分圍觀吃瓜群眾紛紛表示：
"This is suber cool!"
"Excited to see this merging of ML and combinatorial optimization finally happening"
"攻破OR（運籌學）只是時間問題"
而一些實踐派已經在伸手要代碼了：
"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"
其實，把機器學習和整數規劃結合在一起并不是一個新課題。為什么Google的這篇論文引起這么大的關注。Google和DeepMind團隊的名氣當然是最大的因素，從圍棋的AlphaGo到最近的蛋白質結構預測的AlphaFold2，DeepMind的每次出手都是風口浪尖上的大動作，也確實在某些領域帶來過突破性的進展。但這篇論文是否有顛覆性的研究成果，以至于可以“攻破OR（運籌學）”？
DeepMind并沒有回應開源這部分代碼的要求，因此想要看看他們的工作只能讀論文。這篇論文的原文可在arXiv獲取：
地址：https://arxiv.org/abs/2012.13349
杉數科技的COPT求解器開發團隊詳細地學習、研究了這篇論文。在此我們把團隊的分析討論奉上，以資對機器學習和優化算法結合做進一步探討。
MIP（混合整數規劃）一般特指混合整數線性規劃，它在滿足線性約束條件Ax≤b和整數約束條件x∈Z的前提下，求解目標函數f(x) = c·x的最小值。其中數組x叫做決策變量，數組c是這些決策變量的目標系數，矩陣A是線性約束矩陣，Z是整數集合。整數規劃在現實世界中的用途極為廣闊，例如在航空航天、能源電網、生產制造、交通物流、軍事與通訊等領域都起著不可替代的基礎建模與求解功能。但是整數規劃也是非常困難的問題，在計算機的復雜性理論上，是屬于NP難問題類的，也是美國庫蘭所公布的數學七個千年大獎難題之一，對于此類問題，是否存在多項式時間的精確求解算法，至今仍未有定論。
求解整數規劃的主要算法部件有：預求解、分支定界、啟發式算法、割平面、沖突分析和線性規劃求解器等模塊。鑒于DeepMind此次的論文主要涉及分支算法和啟發式算法，我們分別重點從這兩個方向進行探討。下文會對DeepMind的基本結論先做一個分析，然后分別就DeepMind論文中提到的Neural Branching和Neural Diving這兩項成果，介紹混合整數規劃相關的背景知識，然后對比分析論文中的新思路和傳統算法的關系。
文末，也對杉數科技在求解器內部開發和外部應用過程中對機器學習，強化學習等技術探索和使用做了一些簡單的舉例，也是想說明運籌與優化技術從誕生的第一天起，就注定了是一門廣泛交叉的科學，多種大數據與人工智能技術的興起，為它注入了新的活力，在智能決策的領域，可以預見將會發揮越來越大的作用。
DeepMind論文求解結果分析
DeepMind的論文引起了廣泛的關注，并不止因為團隊的名聲，也來自于論文中報告了非常驚人的性能提升數據。如論文摘要中提到的，對于測過的5組問題里，在3組上分別實現了1.5倍，2倍，以及1萬倍的更好的Gap。
其實這里玩了一個小小的文字游戲。作為MIP求解器開發人員，一般不把一定時間內能拿到的Gap作為主要衡量標準。因為這有一定的誤導性。設想一類較特殊的整數規劃問題，如可行性問題，它沒有目標函數，只需要找到一組整數解即可完成。那么在找到整數解之前，其Gap就是100%，找到之后就是0%。如果某個啟發式（或者割平面）算法，在開啟和關閉的的情況下，分別可以于1小時和3小時找到可行解。則如果以兩小時為觀察點，則可以說在開啟這項算法的前提下，實現的Gap提升就是無窮多倍，而若以半小時或者三個小時作為觀察點，則Gap沒有提升。鑒于DeepMind并未公布計算這些性能指標的原始數據，我們無法用MIP業內的公認方式來對它做出評價。一般來說，根據目前公認的測試標準，一般是在MIPLIB的問題集上，以兩小時為限，考慮能求解的問題數量和平均求解時間進行比較。
對于特定的測試集取得驚人的性能提升并不意外，因為這正是機器學習擅長的地方：它可以捕捉同一類問題的特征結構，并且給出優化趨勢的判斷。如后文所述，我們自己在開發的過程中也有類似的經歷。真正值得關注的是它在MIPLIB上的表現。MIPLIB 2017 由1000多個來自各行各業的實例構成，而MIPLIB2017 Benchmark則是其中挑選的240個結構各異的問題組成，在篩選的時候就充分的做到了差異化，因此它和電網優化和ＮＮ Verification等測試集有本質的區別。這也解釋了在MIPLIB上算法性能提升效果并不如其他數據集明顯的原因。
為了避嫌， 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四個結構高度類似的問題。因此在訓練集上獲得的經驗，必然會對求解最后的測試集有幫助。而這些幫助能否泛化推廣到任何通用問題集上，高度存疑。
分支算法與Neural Branching
分支（Branching) 算法是整數規劃求解器的核心框架。求解MIP通常需要求解多個LP（線性規劃）問題完成。其中第一個LP問題是原始問題去掉全部的整數約束得來。如果第一個LP問題的最優解碰巧滿足整數條件，則這個解也是整數規劃的最優解。如果LP松弛問題的解不都滿足整數條件，則可以通過分支算法繼續尋找整數解。
分支算法通過選擇一個取值不為整數的變量x=x*進行分支，通過分別添加x≤floor(x*)（即取值不大于x*的最大整數下界）和x≥ceil(x*)（即取值不小于x*的最小整數上界）這兩個約束來把原始問題分解為兩個子問題。原整數規劃問題的最優解一定在這兩個分支之一。接下來繼續求解這兩個新的問題，并以此類推，直到找到最優的整數解或者證明整數解不存在為止。不難看出，分支算法的本質是枚舉，在有n個0-1變量的混合整數規劃問題里，最壞情況要遍歷所有2的n次方個分支節點。也因為混合整數規劃問題是個NP難問題，所以目前精確求解的算法，基本上都基于分支算法的框架，最壞情況下復雜度是指數時間級別，耗時可能會極端漫長。
在實踐中，求解整數規劃通常遠不需要枚舉全部的節點。這是因為分支算法可以以一種更聰明的方式選擇進行分支的變量。在眾多分支算法中，最有效果的算法是完整的強分支算法（Full strong branching簡稱FSB）。該算法原理非常簡單，即通過分別對當前LP（線性規劃）問題的各個取值不為整數的變量進行分支，求解全部的分支后的LP問題，并通過LP的目標函數值判斷選取哪個分支是可以最快的完成MIP求解。實踐中FSB所需要的計算量非常巨大，因此對每個LP節點使用很不現實。在MIP求解過程中，會不定期的做限定循環數的Strongbranching來獲取每個變量分支的最佳估計。
Google提出的Neural branching其本質是先通過神經網絡離線學習FSB的真實計算結果，再在實際應用中模擬FSB計算，在追求FSB效果的同時，節省計算時間。其實這項工作過去幾年間有很多類似的論文。Google的論文在相關工作中也提到了其他8篇相關的研究論文，多數的基本想法是比較類似的。因此論文在這個點上的創新有一定的局限性，正如Google的論文所說：是通過用GPU和ADMM方式大量計算原始問題的FSB近似值，以便可以生成大量的機器學習數據。不過這也從另一個方面反應了FSB的計算量，即使產生離線學習的數據，都不得不設法讓它算的更快一些。
和傳統的分支算法相比，Neural branching以及其他在這個方面的研究確實是（離線）機器學習和優化算法的一種有趣的結合。但值得指出的是，經典的分支算法，也是基于歷史數據對將來分支的預測，它的本質也是一種在線的機器學習機制。例如在杉數求解器里，使用strongbranching只是其中一項，此外還有偽價格(Pseudocost)、可靠性(Reliability)和推斷(Inference)等公開和其他不公開的判斷標準。這些算法均是通過在求解的過程中積攢信息，并以此來判斷、選擇新的分支變量等。
啟發式算法與Neural Diving
啟發式算法，是在主體的分支定界算法之外尋找整數解的算法的總稱。啟發式算法是MIP研究的一項熱點，相關的論文不勝枚舉，目前僅在SCIP中實現的啟發式算法就有57種之多。這些啟發式算法又大致可以分為四類：取整（Rounding）、下潛（Diving）、子問題（Sub-MIP）和上述三類之外的其他算法。
取整（Rounding）啟發式算法顧名思義，是在LP松弛解不滿足整數約束時，對不滿足的變量進行取整，以期望獲得整數解。下潛（Diving）啟發式算法的本質是深度優先搜索，它在LP松弛解不滿足整數約束時，從當前節點出發，不斷的選取最佳分支進行深度優先搜索，直到找到整數解或證明子問題為不可行為止。這兩類算法雖然原理簡單，但是也都有多種實現變種，在這里不展開討論。
子混合整數規劃問題（Sub-MIP）的啟發式算法是一個大類，它通過構造并求解子MIP問題來尋找高質量的整數解。在構造子問題的時候，又有多種構造方式，例如：固定或縮緊變量，添加約束以及修改目標函數值。其中如固定變量類的算法，比較有名的有松弛導向鄰域搜索（Relaxation induced neighborhood search或簡稱RINS），它的工作原理是當某個整數變量在LP松弛解中的值與當前最好整數解中的值一致，則將該變量固定在這個整數值。如果大量變量可以被固定，則可以把這個固定變量后的子問題當作一個全新的MIP求解，以期望可以找到高質量的整數解。由于大量的變量被固定了，子問題的搜索空間會變小，且預求解可以進一步的削減問題的規模，因此解子問題會相對容易些。
DeepMind提出的Neural Diving這個算法，是通過機器學習和神經網絡，給定一個問題結構，預判如何固定部分整數變量的取值，然后去求解子MIP。因此，盡管用到了Diving這個詞，但是我們認為它還是可以歸類為求解子問題的啟發式算法。可以看出這個算法在原理上和上述的RINS有諸多相似之處，只是固定變量的方式不同。
雖然思路和很多既有啟發式算法形式類似，但Neural Diving還是有它的獨特之處。Neural Diving最大的優勢之一，是它可以在正式求解原始問題之前，即生成多組差異化的部分變量取值，啟動啟發式算法。這一方面提升了該算法找到高質量整數解的成功率，另一方面也提前了找到整數解的時間，因此可以較早的獲得較小的Gap。我們也認為這是DeepMind這篇論文的最有價值的部分。
人工智能與MIP結合的實例應用
杉數求解器在開發的過程中充分使用了機器學習工具。除了上文提到的本質就是在線學習的分支算法之外，我們還在許多其他不同的方向使用了機器學習工具。
例如求解子MIP的啟發式算法，是一個有效但非常耗時的算法。我們在開發的過程中，求解大量的子問題，提取子問題特征（例如再次預求解效果，變量種類等），交給機器學習幫助判斷預測某個子問題是否值得花時間啟動求解，避開耗時且無效的方法，提升求解速度。
此外我們的線性規劃LP求解器開發也得益于機器學習。例如我們對部分有特殊結構的LP使用機器學習的方式，預測一個變量是否在最優解的基解的一部分，并通過小幅的目標函數擾動將這個預測結果應用到LP問題上，實現快速求解。
除以上內嵌在求解器內部的機器學習成果之外，在過去幾年里，杉數在使用求解器解決多個行業的困難問題時，也從機器學習，深度學習，強化學習中獲益很大。
一個例子是國家電網安全約束機組組合問題（Security Constrained Unit Commitment簡稱SCUC）問題。SCUC問題的特點是規模不大，但是要求快速求解。我們遇到的實際問題只有數千個整數變量，需要求每隔15分鐘求解一次，并且要在15分鐘內盡快解完。我們通過深度神經網絡等機器學習的方法去預測MIP模型最優解中每個決策變量取1的概率，從而固定部分置信度最高的變量和對中間置信度的部分變量添加多變量分支的割平面，使得最后的問題可行的概率最高。這樣的方法能夠有效減少分支定界樹的搜索規模，一方面能夠實現快速收斂，另一方面能夠快速尋找到高質量的初始解。最后的實驗顯示，借助該方法在達到相同質量解(Gap=0.01%)的速度提升為5-10倍左右。其中不乏有原始問題3分鐘無法完成求解，而結合使用機器學習算法僅需10秒就能完成求解的時候。這種速度的提升對需要每15分鐘都需要快速計算決策的SCUC問題非常重要。
電網中的優化也是DeepMind指出的智能化MIP可以重點發力的領域。但是，值得著重指出的是，電網另一個特性就是對于安全性和魯棒性的極端要求。而在新問題的數據結構突發巨變，歷史數據已經不能指導未來的時候，例如戰爭，自然或者人為因素導致的發電廠和輸電線路的極大變化，機器學習能起到的作用會弱化很多。這個時候，更多的時候還是依靠MIP求解器自身六個模塊那些獨立于數據之外的經典算法的實現能力。
另一個例子是中國郵政的路由網絡規劃問題。我們在實踐中遇到的此類問題通常需要求解數十萬整數變量的MIP來決定發車安排。如果直接拋給求解器，則往往需要花費一至兩個小時才能找到第一個整數解（Gap在30%左右甚至更差）。通過觀察，我們發現盡管無法預測全部的發車安排，但是可以預測部分高概率的車輛安排。我們進而通過機器學習歷史數據，形成了一套根據線性約束關系生成數千發車安排的部分初始解的方法。在此基礎上，我們通過臨時固定這些決策變量，構造子MIP問題，用求解器快速的計算、補全子問題的解。這個子問題由于部分關鍵變量確定，使得預求解模塊可以對問題規模進行大幅度的削減，促成快速求解。盡管這個子問題的最優解不是原始問題的最優解，但在實踐中這個解（Gap在10%之內）明顯優于花費一至兩小時算出的第一個可行解。而從預測到解子問題，通常只需要不到1分鐘的時間。因此可以說，機器學習幫助我們以50倍的速度提升找到了同等質量（其實是更好）的整數解。
另一個更有廣泛意義的例子是，在近期的科研論文與多個號稱從事智能決策公司的宣稱中，可以看到一些諸如車輛調遣，路線規劃等交通類問題，因為其事件頻次高，數據結構相對穩定，所以無論是分支策略，初始解固定，甚至割平面產生，都可以通過機器學習技術獲得，從而加速問題的MIP模型求解。而且也確實有很多學者在這個問題上取得了相對多的進展。因此，交通領域也是機器學習，智能決策等技術近些年來一直關注的領域。
其實，不僅僅是是路線規劃。在五年前，杉數就曾經與某國內最大的出行平臺合作，考慮過司機與乘客的智能動態匹配系統，問題從最開始的單純機器學習計算匹配系數，進行啟發式算法分配，到后來進行全城的時間切片網絡流匹配，再到將削峰填谷，智慧出行的理念融合，建立起整個系統的動態規劃模型，并在強化學習框架下，進行未來趨勢與決策的近似方法，最后得到一個在時間和空間上都接近全局優化的方案。整個系統隨著數據的完備，算力的到位，在雙方攜手建立的強化學習框架下不斷進化，從簡單的線性函數逼近到神經網絡近似，越發智能與精準，在2017年的時候，就已經得到了廣泛的應用，創造了極大的經濟效益與社會效益。
結語
最后，我們想強調，如"機器學習之父"MichaelJordan指出的，未來的人工智能最重要的突破應該與優化算法緊密結合。而這正是運籌學的核心基礎。
在今天討論的這個例子里，簡單地說，神經網絡和機器學習技術進展，更像是給MIP開發的六大模塊中的兩個模塊探索的武器庫增加了一些昂貴（算力資源需求）而有力的武器，豐富了這些模塊加速的能力，遠遠談不上攻破OR。這些技術展示出來的潛力是值得歡呼的，但是在現實中求解MIP問題，需要的數學技巧和工程經驗是極其厚重的。
傳統的MIP求解工具有數十年的理論論證和理論分析基礎。相較之下，MIP求解中的機器學習工具因其模型結構的復雜性，理論論證成果較少。大量的相關機器學習研究都是依靠某一類或者某幾類的數據集的數值實驗結果用以驗證其有效性。所以機器學習方法對現實中一般性問題求解的可靠性還有待進一步的論證。另一方面，絕大多數機器學習的算法設計是需要將模型轉化成經典的整數，線性，凸或者非凸數學規劃模型，再對其分析的。
回到MIP，可以說利用機器學習進行某些點上的突破是遠遠不夠的。一般性的整數規劃乃至廣大的NP難問題，在真正的顛覆性技術突破之前（比如量子計算機的真正實用化），依然可預期在未來很多年，會是人類智力的極限之一。
說明：此文寫作中獲得了香港中文大學（深圳）王子卓、斯坦福大學葉蔭宇、紐約大學陳溪、約翰霍普金斯大學江弘億等多位學者的指導和建議，在此一并表示感謝。
雷鋒網雷鋒網雷鋒網
雷峰網特約稿件，未經授權禁止轉載。詳情見轉載須知。
