運籌學中的問題不是認知問題，而深度學習由於從海量資料中學習到有效特徵的能力很強大，所以更適合”聽說讀寫看”這些跟認知和理解相關的問題。所以個人拙見運籌學受深度學習的影響有限。只就像svm和貝葉斯這些很成熟的機器學習演算法對運籌學影響有限一樣

但是由深度學習推動的高效能計算體系的發展，比如gpu，fpga，cuda等有可能被運籌學所使用，畢竟運籌學的最底層也是數值演算法，各種矩陣計算問題，平行計算框架大有用武之地。

另外一點，理論上深度學習演算法可以擬合任何函式，因為運籌學最終也是針對cost function在約束函式下的求解問題，未來或者沒準已經有大神搞出個深度學習演算法思路來解決。特別是實時性要求較強的運籌學問題，如果有深度演算法預訓練出模型，解題時只是一次inference幾秒鐘就有結果，還是蠻令人期待的

前言

最近看到一篇回答，YouTube 已將影片推薦全面改用深度學習實現。但傳統上，推薦系統落在運籌學的範疇，可以歸結為一個矩陣補全（matrix completion）問題，用半正定規劃（SDP）裡的方法，如非負矩陣分解（NMF）解決，而 YouTube 的結果顯示深度學習的預測準確率比傳統方法好很多、快很多。

文中提及回答：王科：YouTube 的影片推薦演算法是怎樣的？

:http://t.cn/RQR9nhK

這個問題比較前沿一些，原來看起來相關性不那麼強的技術領域，機器學習 VS 運籌學，因為深度學習的發展和突破，變得聯絡越來越緊密了。

1. 運籌學簡介

狹義的運籌學，往往特指採用LP/MILP/MIP/QP/NP 等數學模型建模、採用精確演算法/啟發式演算法線上求解並得到滿意方案以及進行相關理論分析的一類技術。所以，運籌學最早是作為應用數學的一個分支，服務於人們解決各行各業最佳化問題的一類基本數學工具而存在的。

OR/optimization兩個學科近年的復興無疑需要歸功於機器學習。2005年以來，Lasso等方法的提出正好契合了貝葉斯學習的精神；2010年，Boyd 在故紙堆中重新找出分散式ADMM用來求解帶約束機器學習問題（矩陣分解等等），成為了傳統機器學習的標準正規化（objective+regularization）；2014年以來，深度學習的興起則直接帶火了一片一階隨機演算法：ADAM/RMSprop 等。例如，SVM 的訓練過程，本質上是求解一個 SQP問題；訓練神經網路的梯度下降演算法，是在使得訓練誤差極小化意義下的一個區域性最佳化演算法。由此可以看出，絕大部分機器學習模型的訓練過程，都是首先將其建模為一個運籌學問題，然後採用相應演算法來求解的。從這個角度看，機器學習（包括深度學習），是運籌學的一個應用領域。

在使用運籌學來解決各行各業形形色色問題的過程中，研究者在理論和應用層面發展出了許多型別的最佳化演算法，也解決了不少實際問題。各類運籌學的期刊、會議有很多，每年至少有幾千篇論文、專利發表出來。然而，除了幾十年前已經發展比較成熟的幾類經典演算法（凸規劃演算法、動態規劃、若干圖演算法、信任域演算法、元啟發式演算法等）之外， @郝井華 認為，在基礎演算法層面，並無太大的突破。人們對具有非線性、NP-Hard特點的大規模最佳化問題，仍然缺少好用的處理工具和通用求解演算法，往往需要研究者結合領域知識，採用模型簡化和變換、分而治之等辦法來近似求解。然而隨著人們對深度學習研究的逐步深入，運籌學問題的求解初步的湧現出了新的思路。本文將簡單的介紹運籌學和深度學習的相互影響，以及近些年湧現出的一些比較有意思的研究成果。

2. 深度學習對運籌學的影響

深度學習的出現，為運籌學領域處理上述複雜最佳化問題提供了一個非常有效的技術途徑。在深度學習和運籌學結合之前，在運籌學的學術研究圈裡，已經出現了不少『運籌學+機器學習』的案例。例如，在工業產品設計領域常使用響應曲面法(RSM)、插值法來根據有限的實驗資料點來建立模型並求解；進化演算法大類中，EDA（Estimation of Distribution Algorithm）演算法透過一些機器學習模型來學習編碼和目標函式之間的近似關係來提升迭代效率，等等。感興趣的同學可以 Google 一下這個領域的論文。

EDA之類的分佈機率估計算法，思想非常好，但是後續並沒有取得很大的成功，原因在於，複雜非線性最佳化問題的解空間往往非常『崎嶇』，Landscape 非常複雜，透過一些常規的線性模型、核模型、神經網路等，很難對其解空間進行高精度的逼近。所以相應的最佳化演算法，會有一些改進，但是很難有質的突破。

3. 深度學習與運籌學的對比

首先，與傳統運籌學關注的問題相比，一個典型的深度學習問題引數量（待求解的變數個數M）一般很大（例如，用於視覺識別的Alexnet引數量大約在100M這個量級），而凸最佳化演算法一般能夠高效解決的變數個數一般在1k-100k這個量級。因為很多演算法一旦涉及到求Hessian/Jacobian矩陣就會涉及到儲存和計算效率問題了，這正是很多傳統演算法的瓶頸之處，而這也是新世紀以來一階演算法重新興起的一個背景。正是由於這樣的原因，LBFGS一度作為標準的最佳化演算法在現代機器學習界應用較少：每步迭代需要一個O(M^2)變數的更新的代價太大了！

其次，機器學習以及深度學習所伴隨的資料集規模（N）一般也很大，例如標準視覺toy資料集ImageNet是120萬*4096，而google，Amazon，阿里巴巴等大廠的的規模則是PB級別的，這甚至已經達到傳統油田，大氣，金融等問題的儲存規模了。資料集大小方面帶來的問題也是不可忽視的，一系列的隨機演算法（SGD-based method)、分散式演算法被提出來應對這些問題。

從計算難度的角度而言，油田、大氣、金融等問題的計算一般都有很好的formulation，問題求解雖然不見得性質很好（例如解Levy Process因為跳的存在，也涉及到很多0-範數的問題，本質上還是NP-hard的），但是起碼能夠有一些理論的保證。而深度學習由於問題極其扭曲（深），非線性程度很高，所以求解過程收斂速度和收斂性並沒有任何的保證。當然最近也有一些在比較強的假設下，淺層的神經網路到達saddle point或者local minima的一些證明，但是計算上的問題還是一個根本的困難問題。

然而，在給定大量高質量資料的前提下，深度網路和深度學習演算法展現出了相比較傳統機器學習模型精準得多的逼近能力，能夠提供高精度的逼近效果。從本質上說，這一點就是深度學習帶給運籌學的最大影響。在合適的應用場景下，透過深度網路離線學習得到高質量的逼近模型，並把它和符合問題特點的最佳化演算法相結合，將會帶來意想不到的應用效果。我相信未來幾年內，這方面的論文會湧現出一大批。

從應用層面來說，機器學習在‘預測’上比傳統運籌和統計模型表現好是必然的，原因是傳統模型基於簡單的假設，因為複雜的假設可能無法快速的解出最優解。更多的引數意味著這更好的擬合程度，雖然有過擬合的風險，但機器學習模型可以透過模型增加正則化，Bagging, Boosting等一些列方式防止過擬合，從而達到很好的預測效果。當然了，預測好並不是一個模型的全部，相對於傳統的統計模型所缺少的是可解釋性和insight。

4. 深度學習的發展

舉個例子，博弈問題如圍棋，就是一個典型的複雜最佳化問題。而AlphaGo 成功的本質原因，是透過深度網路離線學習得到了對於狀態和落子點價值的較為準確的評估，然後線上地和搜尋演算法（蒙特卡洛樹搜尋演算法）相結合，取得了突破性的效果。

最近，機器學習界也在反思，Neural Network+BP=AI這麼一個打法究竟是否成立。Hinton直接就跳出來說：“BP在深度學習中不是必要的”，並且提出了一個叫Capsule的東西給大家思考。包括我們也知道有很多non-gradient的方法（粒子群蟻群最佳化等，一度被小圈子玩壞的領域，但是在新時代有無重新興起的可能？而OR也確實能夠給機器學習界帶來很大的幫助：例如，以SMO求解SVM等對偶方法現在已經是標準思路。

5. 機器學習和整數規劃結合的一些成果

整數規劃作為運籌學理論體系中很重要的一部分，對解決實際工業需求中的問題提供了強有力的建模方式，但機器學習模型可以透過模型增加正則化，Bagging, Boosting等一些列方式防止過擬合，從而達到很好的預測效果。

Branch-and-Bound(B&B)和 Cutting Plane方法是求解整數規劃精確解的兩種常用的方法。一直以來，這兩種方法對機器學習理論的發展和應用都起到非常重要的作用。例如，B&B可以用在MAP 估計、場景理解、和dependency parsing中。機器學習的發展同樣對整數規劃理論具有很強的推動作用，尤其在整數模型求解過程中所涉及到的決策部分，機器學習模型將越來越發揮重要的作用。

例如，在使用演算法或者商用求解器求整數模型的精確解時，通常會涉及到以下三種決策：

-Cutting Plane: 會有很多有效的割平面，但如何只選擇其中一部分加入求解過程中。

-Node Selection：如何在現有產生的Node中選擇一個，進行下一步的鬆弛。

-Branching：在每個Node中，選擇哪個變數進行Branch.

當前的商用求解器比如Cplex, Gurobi 和開源非商用求解器Scip在處理三種決策時，通常使用Heuristic的方法進行處理。例如，在Cut Selection中，一般使用一個多變數打分系統對每個Valid Cut進行打分做出選擇，這樣的處理方式是非常的主觀的。現有求解器在進行Node selection 時, 通常預設使用best-bound 和best-estimate 兩種方式，根本沒有考慮求解模型的特性。同樣的問題存在Branching rule的設計中。

機器學習的發展，為整數規劃的演算法中涉及到決策的部分提供了一種新的思路。比如可以透過定義合適的reward 和transition function, 可以用Online learning 演算法，模擬node selection過程。可以用非監督模型對整數模型進行Danzig-Wolfe 分解。也可以透過學習Surrogate 評價函式，來學習Strong Branching過程，從而減少求解時間。

近些年，越來越多這樣的成果湧現出來，但大部分成果還都是在各大計算機頂尖會議上進行發表，其中以佐治亞理工計算機系的Song Le， Bistra Dilkina團隊和工業工程系George Nemhauser團隊最為突出。在兩個人工智慧專家和傳統最佳化大師聯合指導下，組內的博士生使用最前沿的深度學習在傳統整數規劃領域做出了突出的成果。也從側面證明了，運籌學要和人工智慧深度的結合，才有可能突破現在理論所遇到的問題。

此外，在很多行業中，受問題規模、複雜度以及響應時間的制約，很多規劃問題需要大量應用啟發式規則/程式(heuristics)來近似求解。這些啟發式規則/程式往往來自對系統長期的觀察和思考，其質量可能對系統性能至關重要。運籌學中演化計算領域中有一個“演化規劃”分支，試圖利用演化計算的方法來探索和生成更優的啟發式規則，如genetic programming 等，類似的研究還包括approximatedynamic programming、決策樹等。近年，這一領域越來越多的學者開始結合深度學習的方法，尤其是深度增強學習，也取得了一些有趣的進展。

6. 結論

1）運籌學學科的發展，需要在最佳化演算法中越來越多的引入深度網路等機器學習工具，實現離線線上相結合，資料和機理相結合，以取得更好的應用效果，這是運籌學發展的必然趨勢。

2）運籌學為機器學習貢獻最佳化理論，同時吸取機器學習的理念來更好的解決傳統問題，而深度學習也對現有的運籌學理論進行了新的發展。

3）運籌學和深度學習，並不是對立的兩個概念&工具，在很多時候需要結合起來使用。

感謝審稿人楊昌鵬 @Changpeng Yang, 新加坡南洋理工大學/加州大學伯克利分校聯合培養博士，現任順豐科技----航空和物流最佳化 ，為本文添加了機器學習與整數規劃結合的一些成果這一小節的內容以及對整體文章的建議和修改。

感謝審稿人 @王孟昌 阿里巴巴運籌最佳化演算法專家-排程最佳化，整數規劃，為本文添加了機器學習與整數規劃結合的一些成果這一小節的內容以及對整篇文章的框架的處理和建議。

參考文獻：[1]Khalil E B. Machine Learning for Integer Programming[C]//IJCAI. 2016: 4004-4005.[2]Khalil E B, Dilkina B, Nemhauser G L, et al. Learning to run heuristics in tree search[C]//Proceedings of the international joint conference on artificial intelligence. AAAI Press, Melbourne, Australia. 2017.[3]He H, Daume III H, Eisner J M. Learning to search in branch and bound algorithms[C]//Advances in neural information processing systems. 2014: 3293-3301.[4]Comments on: On learning and branching: a survey[5]Lodi A, Zarpellon G. On learning and branching: a survey[J]. TOP, 2017: 1-30.[6]Dai H, Khalil E B, Zhang Y, et al. Learning Combinatorial Optimization Algorithms over Graphs[J]. arXiv preprint arXiv:1704.01665, 2017.

深度學習的出現，為運籌學領域處理上述複雜最佳化問題提供了一個非常有效的技術途徑。在深度學習和運籌學結合之前，在運籌學的學術研究圈裡，已經出現了不少『運籌學+機器學習』的案例。例如，在工業產品設計領域常使用響應曲面法(RSM)、插值法來根據有限的實驗資料點來建立模型並求解；進化演算法大類中，EDA（Estimation of Distribution Algorithm） 演算法透過一些機器學習模型來學習編碼和目標函式之間的近似關係來提升迭代效率，等等。