运筹学论文,深度学习如何影响运筹学？

作者简介运筹学论文： @郝井华：清华大学运筹学博士，现任美团配送算法架构师，美团点评研究员。@成丰：北京大学智能科学系 硕士 中国国际金融贸易创新发展战略合作研究中心 · 特聘研究员。胖骁： @胖骁 。 @刘嘉耿 ：UCLA数学系毕业生。责任编辑： @文雨之 ：东北大学系统工程博士生， @爱牛氓的帆爷 ：东北大学系统工程硕士生 。本篇文章是由以上四位作者在知乎上的优秀回答，通过两位责任编辑整理修改而成。同时两位审稿专家也提出了修改建议，并且扩展和补充了一部分内容。敬请关注和扩散本公众号及同名专栏，会邀请全球知名学者陆续发布运筹学、人工智能中优化理论等相关干货、知乎Live及行业动态：

前言

最近看到一篇回答，YouTube 已将视频推荐全面改用深度学习实现。但传统上，推荐系统落在运筹学的范畴，可以归结为一个矩阵补全（matrix completion）问题，用半正定规划（SDP）里的方法，如非负矩阵分解（NMF）解决，而 YouTube 的结果显示深度学习的预测准确率比传统方法好很多、快很多。

其他运筹学的问题（如广告搜索、路径规划、定价估值、仓储物流）、形式（如 LP、CP、SDP、MIP）、和方法（如内点法、割平面法）也会遇到这样来自深度学习的挑战吗？如果会的话，将如何影响？学界和业界有哪些已有的讨论和成果？

文中提及回答：王科：YouTube 的视频推荐算法是怎样的？

:}

这个问题比较前沿一些，原来看起来相关性不那么强的技术领域，机器学习 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.