报道 | 运筹学发展简史之1979-2004

编者按

由于篇幅原因，本文仅精选该书第八章中具有跨时代意义的发现、巨作或事件进行介绍，强烈推荐感兴趣的朋友自行阅读英文原版，也欢迎大家在评论区指正、补充。

文章作者：留德华叫兽
责任编辑：疑疑
文章发表于微信公众号【运筹OR帷幄】：报道 | 运筹学发展简史之1979-2004
欢迎原链接转发，转载请私信@运筹OR帷幄获取信息，盗版必究。
敬请关注和扩散本专栏及同名公众号，会邀请全球知名学者发布运筹学、人工智能中优化理论等相关干货、知乎Live及行业动态
更多精彩文章，欢迎访问我们的机构号：@运筹OR帷幄

前言

首先向大家隆重介绍一本书：

An Annotated Timeline of Operations Research - An Informal History | Saul I. Gass

此书是我在准备德国博士答辩general exam借相关教材时，偶然发现的“宝贝”，接着就不务正业地泡了一下午浏览了运筹学的发展史。

本书的目录按照年代，分为八个章节：

1.运筹学（OR）的前身：1564-1873

2.运筹学的前身：1881-1935

3.运筹学的诞生：1936-1946

4.运筹学的扩张：1947-1950

5.运筹学中数学、算法的发展：1951-1956

6.运筹学中国际活动、算法、应用、教科书发展：1957-1963

7.运筹学中方法、应用、论文的发展：1964-1978

8.运筹学中方法、应用、技术、论文的发展：1964-1978

由于篇幅原因，本文仅精选地介绍该书第八章中具有跨时代意义的发现、巨作或事件。

如有时间和财力（官方售价90欧元），强烈推荐买来细细一品英文原版。

正文

话不多说，进入正文，以下也将以时间为序。

1979年

1.电子表格和OR插件问世

世界上第一个电子表格软件VisiCalc于1979年10月问世，从那时起，OR相关插件也被引进，可以做例如线性、非线性和整数规划。随后，Excel、Lotus和Quattro Pro等电子表格也引入OR插件。

2. Computers and Intractability; A Guide to the Theory of NP-Completeness 巨著问世

整数规划等问题被归类到NP难问题。

【学界】混合整数规划/离散优化的精确算法--分支定界法及优化求解器

1980年

1.Constraint Programming 引起运筹学重视

源于计算机科学和人工智能领域，被发现可以用来高效地求解优化问题，特别是排序和调度问题。

2. Total Unimodular矩阵的分解定理

TU矩阵被证明有很好的性质，当整数规划的系数矩阵为TU并且系数为整数时，其线性规划松弛解被证明与原问题等价（即多项式时间可解）。

3. LINDO软件问世

LINDO软件由Linus E. Schrage主要开发，可以解线性及整数规划问题。

LINDO的PC版本由1982年发布。

1981年

1.模拟退火（Simulated annealing）算法面世

该算法是以统计物理为原理的优化算法，用来解决NP难的组合优化问题。

2. 分离问题（Separation Problem）和优化问题的等价性

定理概述：如果分离问题可以被多项式时间可解，那么原优化问题也是。

这个定理由线性规划经典算法ellipsoid method引伸出来，对于数学规划领域非常重要，作者凭借此成果获得了1982年的Fulkerson Prize.

【信息汇总】运筹学、数学规划、优化--国际协会、奖项、会议大搜罗

值得一提的是，该篇论文的作者是我老板的老板，Martin Groetschel.

1982年

1.数学建模软件GAMS面世

优化求解器在此之前已经存在，但是需要较深的运筹学背景才能高效使用。由J. Bisschop研发的GAMS解决了这一痛点，让运筹学建模平民化。

2. 单纯型法（Simplex method）的平均运算时间

虽然单纯型法是一种指数级复杂度的算法，但是在实际使用中被发现特别高效。

K.H. Borgwardt在他的论文里指出了这一发现。

1984年

1.线性规划经典算法内点法（interior method）的证明

不同于单纯型法从一个极点跳到另一个极点，内点法从多面体的内部点进行搜索。

N. Karmarkar的论文第一次证明了内点法是多项式时间可解的，并在此后被求解器开发成成熟的线性规划算法。

2. 神经网络模型（Neural networks）被用来解优化问题

NN被J.J. Hopfield和D.W. Tank用来解决组合优化经典问题旅行商问题（Travelling Salesman Problem）。佩服于前人的探索精神。

【学界/编码】分枝定界求解旅行商问题

https://zhuanlan.zhihu.com/p/33580390

1985年

1.组合优化经典算法：分支分割法（Branch and cut）被世人熟知

M. Padberg和他的共同作者证明B&C方法是解决旅行商问题最promising的方法。

留德华叫兽：【学界】整数规划经典方法--割平面法（Cutting Plane Method）

1986年

1.元启发经典算法Tabu search问世

这个算法不断地修改搜索区域以试图跳出局部最优解，由Fred Glover在1986年的论文率先提出了该名词“Tabu search”。

【学界】整数规划精确算法/近似算法/(元)启发算法/神经网络反向传播等算法的区别与关联

2. Theory of Linear and Integer Programming著作问世

该书作者是荷兰阿姆斯特丹大学、蒂尔堡大学、CWI教授Alexander Schrijver

1989年

1.供应链管理（Supply chain management）及运筹学的作用被世人熟知

供应链由来已久很难追溯他的起源，但是1989年惠普集团战略规划和建模部门与斯坦福大学Hau Lee合作的一个项目向世人展示了运筹学在供应链优化的巨大作用。

【学界】供应链管理：理论、模型和应用概述

2. 运筹学顶刊之一的Informs Journal on Computing建刊

建立该刊是因为ORer看到了运筹学和计算机的紧密联系，最初由ORSA出版。

3. Stochastic modeling and the theory of queues, by R. W. WOE, Rentice Hall, Engle 出版

随机优化和排队论的巨著。

1990年

1.运筹学在金融工程、市场的应用被熟知

运筹学早就被应用于资产配置优化问题，但是数学规划和蒙特卡罗模拟等方法开始被应用于例如衍生品定价、交易策略、对冲基金策略等问题。

2. Operations Analysis in the United States Army Eighth Air Force in World War II (History of Mathematics) : Charles W. McArthur 著作问世

众所周知，运筹学是在二战中发展而来的，这本著作讲述了其在二战中的具体应用，如：飞机投弹问题，投弹点的选择。运筹学的使用使得有效目标炸毁率从15%增加到了60%。

1993-1994

1.NETWORK FLOWS Theory, Algorithms,and Applications 1993年问世

网络流的经典教材，作者James B. Orlin, Ravindra K. Ahuja, and Thomas L. Magnanti，我在Clemson上该门课的参考书籍。

2. NEOS (Network-Enabled Optimization System) 1994年问世

NEOS是一个开源免费的网络优化系统，集合了众多优化求解器。

最初由美国阿贡实验室和西北大学联合研发问世。

3. Markov Decision Processes: Discrete Stochastic Dynamic Programming 著作1994年问世

该书汇总了近40年的MDP理论和应用，该书获得1995年Lanchester prize.

1995-1996

1.ORSA和TIMS 于1995年合并为INFORMS

美国运筹协会ORSA和管理科学机构TIMS合并为INFORMS。

2. Scheduling - Theory, Algorithms, and Systems | Michael L. Pinedo 著作于1995年问世

3. Monte Carlo - Concepts, Algorithms, and Applications | George Fishman 于 1996年问世

以上两本领域内的经典教材。

1999-2004

1.INFORMS旗下期刊Manufacturing & Service Operations于1999年建刊

2.Foundations of Inventory Management (January 24, 2000 edition)著作于2000年问世

3.Combinatorial Optimization - Polyhedra and Efficiency | Alexander Schrijver 著作于2003年问世

4.2004年MIT运筹学中心（ORC）建立50周年

MIT ORC由物理系教授Philip M.Morese建立，是一个跨校区的交叉学科中心，每年资助着很多研究生从事运筹学理论和应用方面的研究。

后记

运筹学自二战以来，在西方发达国家引起了足够的重视并得到了长足的发展。

在中国，运筹学是一门被严重低估的学科。

但是，随着最近人工智能、物联网、工业4.0、智慧物流、智能供应链等概念的兴起，运筹学在中国也终于迎来了其发展的春天，行业薪资待遇也水涨船高，可以说完全不输人工智能。

【学界】人工智能的“引擎”--运筹学，一门建模、优化、决策的科学

https://zhuanlan.zhihu.com/p/25579864?refer=operations-research

最后，需要说明的是，本文仅是我对该书的一点浮于表面的介绍。

请大家不要迷信任何一位作者的blog甚至任何知名教授的“教科书”，兼听则明

例如，法国国家科学院（CNRS）教授Denis Bouyssou就本书写了书评：

http://www.lamsade.dauphine.fr/~bouyssou/BR_Gass.pdf

也欢迎大家在评论区指正、补充。

更多精彩文章欢迎关注我们的机构号@运筹OR帷幄