[deep learning] how does deep learning affect operations research?

---

『 Operational research OR A strategy 』 original

author ： Hao Jinghua and other four people

Author's brief introduction ： @ Hao Jinghua ： Doctor of operations research, Tsinghua University , Currently, he is the architect of meituan Distribution Algorithm , Researcher of meituan comments [email protected] Chengfeng ： Department of intelligent science, Peking University master China International Finance and trade innovation and development strategic cooperation research center · Distinguished researcher . Fat Xiao ： @ Fat Xiao  . @ Liu Jiageng  ：UCLA Mathematics graduate .
editor ： @ Wen Yuzhi  ： Doctor of systems engineering, Northeastern University , @ Fan Ye who loves cattle hooligans  ： Master of systems engineering, Northeastern University .
This article is an excellent answer from the above four authors , It is compiled and modified by two responsible editors . At the same time, two reviewers also put forward suggestions for revision , And some contents are extended and supplemented .
Please follow and spread this official account and the column of the same name , World renowned scholars will be invited to publish operations research 、 Optimization theory and other related dry goods in artificial intelligence 、 You know Live And industry trends ：

『 Operational research OR A strategy 』 Operations research in the era of big data and artificial intelligence -- Know about columns ：http://t.cn/RlNoO3P

『 Operational research OR A strategy 』 There are special posts for prize solicitation in the column

Preface

Recently I saw an answer ,YouTube Video recommendation has been fully implemented by deep learning . But traditionally , Recommendation system falls into the category of operations research , It can be reduced to a matrix complement （matrix completion） problem , Use positive semidefinite programming （SDP） The method in , Such as nonnegative matrix decomposition （NMF） solve , and YouTube The results show that the prediction accuracy of deep learning is much better than that of traditional methods 、 Much faster .

Other operational research problems （ Such as advertising search 、 Path planning 、 Pricing valuation 、 Warehousing logistics ）、 form （ Such as LP、CP、SDP、MIP）、 And methods （ Such as interior point method 、 Cutting plane method ） Will you also encounter such challenges from deep learning ？ If so , How will it affect ？ What are the existing discussions and achievements in academia and industry ？

The text mentions the answer ： Wang Ke ：YouTube What is the video recommendation algorithm of ？

:http://t.cn/RQR9nhK

This problem is more cutting-edge , The technology field that seems to be less relevant , machine learning VS Operations research , Because of the development and breakthrough of deep learning , Become more and more closely connected .

1. Introduction to operations research

Operations research in a narrow sense , Often refers specifically to the use of LP/MILP/MIP/QP/NP Wait for mathematical model modeling 、 Adopt accurate algorithm / Heuristic algorithm is a kind of technology to solve online and get a satisfactory solution as well as carry out relevant theoretical analysis . therefore , Operations research was first used as a branch of Applied Mathematics , It is a kind of basic mathematical tools that serve people to solve optimization problems in all walks of life .

OR/optimization The revival of the two disciplines in recent years undoubtedly needs to be attributed to machine learning .2005 Since then ,Lasso And other methods just fit the spirit of Bayesian learning ;2010 year ,Boyd Rediscover the distributed among the old papers ADMM Used to solve constrained machine learning problems （ Matrix decomposition and so on ）, It has become the standard paradigm of traditional machine learning （objective+regularization）;2014 Since then , The rise of deep learning has directly led to a fire of first-order random algorithms ：ADAM/RMSprop etc. . for example ,SVM Training process of , In essence, it is to solve a problem SQP problem ; Gradient descent algorithm for training neural network , It is a local optimization algorithm in the sense of minimizing the training error . From this we can see that , The training process of most machine learning models , It is first modeled as an operational research problem , Then the corresponding algorithm is used to solve . Look at it this way , machine learning （ Including deep learning ）, It is an application field of operations research .

In the process of using operations research to solve all kinds of problems in all walks of life , Researchers have developed many types of optimization algorithms in theory and Application , It has also solved many practical problems . Various journals of operations research 、 There are many meetings , There are at least thousands of papers every year 、 Patents are published . However , In addition to several classic algorithms that have been developed more mature decades ago （ Convex programming algorithm 、 Dynamic programming 、 Several graph algorithms 、 Trust domain algorithm 、 Meta heuristic algorithm, etc ） outside , @ Hao Jinghua   Think , At the basic algorithm level , There is not much breakthrough . People have nonlinear 、NP-Hard Characteristic large-scale optimization problem , There is still a lack of useful processing tools and general solving algorithms , Researchers are often required to combine domain knowledge , Adopt model simplification and transformation 、 Divide and conquer and other methods to approximate the solution . However, with the gradual deepening of people's research on deep learning , New ideas have emerged for the solution of operational research problems . This article will briefly introduce the interaction between operations research and deep learning , And some interesting research results emerging in recent years .

2. The influence of deep learning on operations research

The emergence of deep learning , It provides a very effective technical way for the field of operations research to deal with the above complex optimization problems . Before the combination of deep learning and operational research , In the academic research circle of operations research , There have been many 『 Operations research + machine learning 』 The case of . for example , Response surface method is often used in the field of industrial product design (RSM)、 Interpolation method is used to establish the model and solve it according to the limited experimental data points ; Evolutionary algorithms ,EDA（Estimation of Distribution Algorithm）
The algorithm uses some machine learning models to learn the approximate relationship between the coding and the objective function to improve the iterative efficiency , wait . Those of you who are interested can Google Let's talk about the papers in this field .

EDA Such distribution probability estimation algorithm , Very good thinking , But the follow-up did not achieve great success , The reason lies in , The solution space of complex nonlinear optimization problems is often very 『 rugged 』,Landscape Very complicated , Through some conventional linear models 、 Nuclear model 、 Neural network and so on , It is difficult to approach its solution space with high accuracy . So the corresponding optimization algorithm , There will be some improvements , But it is difficult to make a qualitative breakthrough .

3. Comparison between deep learning and operational research

First , Compared with the problems concerned by traditional operations research , The parameter quantity of a typical deep learning problem （ The number of variables to be solved M） It's usually very big （ for example , For visual recognition Alexnet The parameter quantity is about 100M This magnitude ）, The number of variables that convex optimization algorithm can solve efficiently is generally 1k-100k This magnitude . Because many algorithms once involve solving Hessian/Jacobian Matrix will involve storage and computing efficiency , This is the bottleneck of many traditional algorithms , This is also a background for the resurgence of first-order algorithms since the new century . It's for this reason ,LBFGS Once a standard optimization algorithm is rarely used in modern machine learning ： Each iteration requires one O(M^2) The cost of updating variables is too high ！

secondly , The size of data set accompanying machine learning and deep learning （N） It's usually very big , For example, standard vision toy Data sets ImageNet yes 120 ten thousand *4096, and google,Amazon, Alibaba and other big factories are PB Grade , This has even reached the traditional oil field , The atmosphere , The storage scale of financial and other issues . The problem caused by the size of data sets can not be ignored , A series of random algorithms （SGD-based method)、 Distributed algorithms are proposed to deal with these problems .

In terms of computational difficulty , Oil field 、 The atmosphere 、 The calculation of financial and other issues is generally very good formulation, Problem solving is not necessarily good （ For example, solve Levy Process Because of the existence of jumping , It also involves many 0- The problem of norms , In essence NP-hard Of ）, But at least there can be some theoretical guarantee . And deep learning is extremely distorted due to problems （ deep ）, The degree of nonlinearity is very high , Therefore, the convergence speed and convergence of the solution process are not guaranteed . Of course, there are also some recently under relatively strong assumptions , The shallow neural network arrives saddle point perhaps local minima Some proof of , But the problem of calculation is still a fundamental difficult problem .

However , Given a large number of high-quality data , Deep networks and deep learning algorithms show much more accurate approximation ability than traditional machine learning models , It can provide high-precision approximation effect . essentially , This is the biggest impact of deep learning on operations research . In the right application scenario , Get high-quality approximation model through deep network offline learning , And combine it with the optimization algorithm that conforms to the characteristics of the problem , It will bring unexpected application effects . I believe that in the next few years , A large number of papers in this field will emerge .

From the application level , Machine learning is in ‘ forecast ’ It is inevitable that it performs better than traditional operational research and statistical models , The reason is that traditional models are based on simple assumptions , Because complex assumptions may not be able to quickly solve the optimal solution . More parameters mean a better fit , Although there is the risk of fitting , But the machine learning model can be regularized by the model ,Bagging, Boosting Wait for some columns to prevent over fitting , So as to achieve a good prediction effect . Yes, of course , Good prediction is not the whole of a model , Compared with traditional statistical models, what they lack is explicability and insight.

4. The development of deep learning

for instance , Game problems such as go , It is a typical complex optimization problem . and AlphaGo The essential reason for success , It is through deep network offline learning that we get a more accurate evaluation of the state and the value of the drop points , Then online and search algorithm （ Monte Carlo tree search algorithm ） Combination , Achieved a breakthrough effect .

lately , The machine learning community is also rethinking ,Neural Network+BP=AI Whether such a play is tenable .Hinton Just jump out and say ：“BP It is not necessary in deep learning ”, And put forward a call Capsule For everyone to think about . Including we also know that there are many non-gradient Methods （ Particle swarm optimization, ant colony optimization, etc , Areas that were once played down by small circles , But is there any possibility of resurgence in the new era ？ and OR It can really bring great help to the machine learning community ： for example , With SMO solve SVM Equal duality method is now a standard idea .

5. Some achievements of the combination of machine learning and integer programming

Integer programming is a very important part of the theoretical system of operations research , It provides a powerful modeling method for solving the problems in the actual industrial demand , But the machine learning model can be regularized by the model ,Bagging, Boosting Wait for some columns to prevent over fitting , So as to achieve a good prediction effect .

Branch-and-Bound(B&B) and Cutting Plane Methods are two commonly used methods to solve the exact solution of integer programming . all the time , These two methods play a very important role in the development and application of machine learning theory . for example ,B&B Can be used in MAP It is estimated that 、 Scene understanding 、 and dependency parsing in . The development of machine learning also plays a strong role in promoting the theory of integer programming , Especially in the decision-making part involved in the process of solving the integer model , Machine learning models will play an increasingly important role .

for example , When using algorithms or commercial solvers to find the exact solution of the integer model , There are usually three kinds of decisions involved ：

-Cutting Plane: There will be many effective cutting planes , But how to select only a part of them to join the solution process .

-Node Selection： How to generate in the existing Node Choose one of them , Take the next step of relaxation .

-Branching： At every Node in , Choose which variable to Branch.

Current commercial solvers such as Cplex, Gurobi And open source non-commercial solvers Scip When dealing with three kinds of decisions , Usually use Heuristic To deal with . for example , stay Cut Selection in , Generally, a multivariable scoring system is used for each Valid Cut Score and make choices , Such a treatment is very subjective . The existing solver is in progress Node selection when , Usually by default best-bound and best-estimate Two ways , The characteristics of solving the model are not considered at all . The same problem exists Branching rule In the design of .

The development of machine learning , It provides a new idea for the decision-making part in the algorithm of integer programming . For example, you can define appropriate reward and transition function, It can be used Online learning Algorithm , simulation node selection The process . The unsupervised model can be used to Danzig-Wolfe decompose . You can also learn from Surrogate Evaluation function , To learn Strong Branching The process , Thus reducing the solution time .

In recent years, , More and more such achievements have emerged , However, most of the achievements are also published at the top computer conferences , Among them, the computer department of Georgia Institute of Technology Song Le, Bistra Dilkina Team and Department of Industrial Engineering George Nemhauser The team is the most outstanding . Under the joint guidance of two AI experts and traditional optimization Masters , The doctoral students in the group have made outstanding achievements in the field of traditional integer programming by using the cutting-edge deep learning . It also proves that , Operations research should be deeply combined with AI , It is possible to break through the problems encountered by the current theory .

Besides , In many industries , Affected by the scale of the problem 、 Complexity and response time constraints , Many planning problems need a lot of heuristic rules / Program (heuristics) To approximately solve . These heuristic rules / Procedures often come from long-term observation and thinking of the system , Its quality may be critical to system performance . There is a field of evolutionary computing in operations research “ Evolutionary planning ” Branch , We try to use evolutionary computation to explore and generate better heuristic rules , Such as genetic programming etc. , Similar studies also include approximate
dynamic programming、 Decision tree, etc . In recent years, , More and more scholars in this field have begun to combine the method of deep learning , Especially deep reinforcement learning , Some interesting progress has also been made .

6. Conclusion

1） The development of operations research , More and more machine learning tools such as deep networks need to be introduced into optimization algorithms , Realize the combination of offline and online , Combination of data and mechanism , To achieve better application effect , This is the inevitable trend of the development of operations research .

2） Operations research contributes optimization theory to machine learning , At the same time, we should absorb the concept of machine learning to better solve traditional problems , And deep learning also makes a new development of the existing operational research theory .

3） Operations research and deep learning , There are not two opposite concepts & Tools , In many cases, it needs to be used together .

---

Thank reviewer yangchangpeng  @Changpeng Yang, Nanyang University of technology, Singapore / The University of California, Berkeley, CO educates doctors , At present, SF Technology ---- Aviation and logistics optimization , Some achievements of the combination of machine learning and integer programming are added to this article, as well as suggestions and modifications to the whole article .

Thank the reviewer  @ Wang mengchang   Alibaba optimization algorithm expert - Scheduling optimization , Integer programming , Some achievements of the combination of machine learning and integer programming are added to this article, as well as the processing and suggestions of the framework of the whole article .

source ： Know user ： How does deep learning affect operations research ？https://www.zhihu.com/question/65151551/answer/240063280

reference ：
[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.

 Past highlights 




 It is suitable for beginners to download the route and materials of artificial intelligence ( Image & Text + video ) Introduction to machine learning series download Chinese University Courses 《 machine learning 》（ Huang haiguang keynote speaker ） Print materials such as machine learning and in-depth learning notes 《 Statistical learning method 》 Code reproduction album machine learning communication qq Group 955171419, Please scan the code to join wechat group