运筹说 第55期丨整数规划先驱——Ralph Gomory

经过前面的学习，相信大家已经对运筹学的目标规划有了更加全面的了解，接下来小编将带你学习新一章的内容，先来看看整数规划的发展简史，然后再带你领略该理论先驱的传奇一生！

引例

EQT能源（Eqt Corporation）总部位于宾夕法尼亚州匹兹堡，已有130余年的历史，是美国最大的天然气生产商。 EQT的主要业务包括页岩地层勘探，天然气开采，以及天然气市场交付。页岩气是蕴藏于页岩层中的天然气。过去十年内，页岩气已成为美国一种日益重要的天然气资源，同时也得到了全世界其他国家的广泛关注。

然而页岩气井可产生不同质量的天然气。传统上区分为干气和湿气。而生产商将天然气输送给客户时，不同客户对天然气的组成和热值（heating value）都有不同的要求，通常为一个区间。面对这些情况时，EQT通常需要做出以下决策：1）根据市场价格预测，选择开采哪个页岩气井；2）何时并且如何混合干湿气以满足客户需求；3）如何决定提纯净化产量。

EQT 公司为了提高运营效率，节约生产成本，与位于卡内基梅隆大学（CMU）的CAPD中心（Center for Advanced Process Decision-making）展开了长期合作。在2016年，由Markus G. Drouven（马库斯·德鲁文）率领的EQT优化工程团队通过建立混合整数规划模型（Mixed-integer Programming）来规划阿巴拉契亚盆地的页岩气开采、处理和输送过程。最终，优化后的净现值达到了2.14亿美元，而优化前的净现值只有8千万美元。

一、整数规划发展简史

简史

20世纪50年代，运筹学创始人和单纯形法发明者George Bernard Dantzig（乔治·伯纳德·丹齐格）首先发现可以用变量来刻画最优化模型中的固定费用、变量上界、半连续变量和非凸分片线性函数等。他对旅行售货员问题（TSP）的研究成为后来分支定界法（branch and bound）和现代混合整数规划算法的开端。

1958年IBM高级副总裁Ralph Gomory（拉尔夫·戈莫里）发表了题为《Outline of an algorithm for integer solutions to linear programs》的论文，介绍了使用单纯形法求解整数规划问题的割平面算法，奠定了整数规划的理论基础。因此，在整数规划领域，1958年被视为具有开创意义的一年。

后来，丹齐格一沃尔夫分解算法（Dantzig-Wolfe）和列生成算法（Column Generation）的提出使一系列交通规划调度和其他领域中的大规模整数规划问题得以求解或近似求解，并在各种应用软件和系统中实现。

了解了整数规划的简史，想必读者们对其奠基人充满好奇，整数规划的奠基人Gomory曾担任 IBM Research 数学科学部主席、IBM 研究总监、Alfred P. Sloan 基金会主席和纽约大学 Leonard N. Stern 商学院研究教授。接下来，小编将对其进行详细介绍。

二、Gomory的一生

                                                                 Ralph Gomory (1929~)

传奇一生

✴1929年5月7日出生于纽约布鲁克林。

✴1950年毕业于威廉姆斯学院。之后，在剑桥大学进修了一年。

✴1954年在普林斯顿大学获得数学博士学位。

✴1954-1957年作为一名军官加入了美国海军。

✴1959年加入IBM新成立的研究部门，成为研究数学家。

✴1964年被评选为IBM Fellow，这是科学家、工程师或程序员在公司所能获得的最高荣誉。

✴1970年被任命为研究总监。

✴1973年当选IBM副总裁。

✴1985年当选IBM高级副总裁。

✴1986年，当选为美国国家工程院理事会和美国哲学学会理事会成员。

✴1987年，成为外交关系委员会成员、哈佛大学应用科学部访问委员会主席、总统高温超导咨询委员会主席。

✴1989年从IBM退休，成为艾尔弗雷德·斯隆基金会的总裁。

三、主要荣誉

荣誉

✔1963年获运筹学学会兰彻斯特奖

✔1964年评为IBM院士

✔1984年获美国信息处理学会联合会哈里·古德纪念奖和约翰·冯·诺依曼理论奖

✔1985年获工业研究学会奖章

✔1988年获IEEE工程领导力认可奖和国家科学奖章

✔1993年获国家工程院的阿瑟·布科奖

✔1998年获亨氏技术、经济和就业年度奖

✔1999年获普林斯顿大学麦迪逊奖章

✔2000年获耶鲁大学工程学院谢菲尔德奖学金

✔2005年入选国际运筹学协会联合会名人堂

✔2006年获运筹学学会哈罗德·拉兰德奖

✔2021年获范内瓦·布什奖

  在Gomory所获荣誉中发现，运筹学伴随了其一生。那么接下来小编为大家分享Gomory与运筹学的不解之缘。

四、Gomory与运筹学的不解之缘

兴趣初始

在Gomory的学生时代，他一直从事非线性微分方程的研究。在海军服役期间，他第一次真正了解到了运筹学，并对其产生了浓厚的兴趣。在回到普林斯顿授课期间，Gomory在华盛顿参加了Alan H. Goldman教授（艾伦·戈德曼）的夜间课程，学习了线性规划。与此同时，Gomory还在海军运筹学小组担任顾问。在海军运筹学小组时，他遇到了一个问题，即使用线性规划设计一支海军特遣部队。部队中有一艘航空母舰时，必须同时配备驱逐舰及一些其他设施，所以海军方面需要了解船只的数量以及它们能走多远。当他们使用线性规划来最小化工作组的成本和工作组的组成方式时，得出的答案是二又四分之一艘航空母舰。这个答案虽然的确是最优解，但在现实问题中并非可行解。因此，戈莫里经过不断思考，最终研究出了Gomory割平面法，并花了一个月的时间证实了它的收敛性。

造纸厂问题

在IBM任职期间，Gomory还遇到了另一个问题——造纸厂制作出巨大的纸卷，但之后他们不得不把纸卷切成人们可以使用的大小，在这个过程中就难免会出现浪费。这种情况可以被看作一个线性规划问题，但减少浪费的方法存在数亿种。因此，线性规划公式涉及数亿列，人们无法将它们一一列举出来，就更不用说在计算机上运行了。所以Gomory与Paul Gilmore（保罗·吉尔摩）开发出了一种叫做列生成的算法，然后在计算机上实现。这种算法被发明出来后，被当时的很多家造纸厂使用。同时，Gomory也在这个过程中获得了大量的造纸数据。通过这些数据，Gomory和Paul发现一旦纸卷滚动到一定的宽度，它就会以某种方式重复，这种现象可以用群论来解释。因此两人基于这种现象，写出了名为《Some polyhedra related to combinatorial problems》的论文，并在学术上获得了巨大的成功。

  在了解Gomory之后，相信大家对整数规划已经有了丰富的兴趣。为此，小编还为大家带来了整数规划领域其他的一些著名研究者。

五、整数规划历史人物拾零

分支定界法的创始人

                                                                               Ailsa Land

                                                                           Alison Doig

total unimodularity（全幺模）概念提出者

                                                                          Alan Hoffman

                                                                        Joseph Kruskal

Dantzig-Wolfe（丹齐格一沃尔夫分解算法）提出者

                                                                   George Bernard Dantzig

相信到这里，大家已经了解了整数规划的由来，敬请持续关注，接下来小编将带你学习整数规划的知识点~

资料来源：

Gomory, Ralph E. - INFORMS

运筹学整数规划领域，有哪些世界著名的教授或研究者？ - 知乎

https://mp.weixin.qq.com/s/uoHo_E5DsopMNALbyT-tsw

孙小玲, 李端. 整数规划新进展[J]. 运筹学学报, 2014, 18(1): 39-68.

END

作者 | 刘文志   林若唯

责编 | 刘文志

审核 | 徐小峰

 ·YUNCHOUSHUO· 

· 知乎｜运筹说 ·

· 简书｜运筹说 ·

· CSDN | 运筹说 ·