作者：郝井華等四人
作者簡介： @郝井華：清華大學運籌學博士，現任美團配送算法架構師，美團點評研究員。@成豐：北京大學智能科學系 碩士 中國國際金融貿易創新發展戰略合作研究中心 · 特聘研究員。胖骁： @胖骁 。 @劉嘉耿 ：UCLA數學系畢業生。
責任編輯： @文雨之 ：東北大學系統工程博士生， @愛牛氓的帆爺 ：東北大學系統工程碩士生 。
本篇文章是由以上四位作者在知乎上的優秀回答，通過兩位責任編輯整理修改而成。同時兩位審稿專家也提出了修改建議，并且擴充和補充了一部分内容。
敬請關注和擴散本公衆号及同名專欄，會邀請全球知名學者陸續釋出運籌學、人工智能中優化理論等相關幹貨、知乎Live及行業動态：
前言
最近看到一篇回答，YouTube 已将視訊推薦全面改用深度學習實作。但傳統上，推薦系統落在運籌學的範疇，可以歸結為一個矩陣補全（matrix completion）問題，用半正定規劃（SDP）裡的方法，如非負矩陣分解（NMF）解決，而 YouTube 的結果顯示深度學習的預測準确率比傳統方法好很多、快很多。
其他運籌學的問題（如廣告搜尋、路徑規劃、定價估值、倉儲物流）、形式（如 LP、CP、SDP、MIP）、和方法（如内點法、割平面法）也會遇到這樣來自深度學習的挑戰嗎？如果會的話，将如何影響？學界和業界有哪些已有的讨論和成果？
文中提及回答：王科：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 等，類似的研究還包括approximate
dynamic 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.