四年求一解，一群达摩院数学家的极限挑战

luyuanhong

四年求一解，一群达摩院数学家的极限挑战

原创 达摩院 达摩院DAMO 2024-01-29 10:58 浙江

“全世界能做这件事的只有 100 多人。”

这是 2019 年加入阿里巴巴达摩院决策智能实验室时，著名应用数学家印卧涛面临的难题。

曾任加州大学洛杉矶分校数学系终身教授，也是运筹学 Egon Balas 奖唯一的中国得主，印卧涛长期致力于运筹优化研究。



这一领域将整个经济社会描绘为无数个交织的方程组。机场航班的起降时间、物流的路径规划、金属冶炼的原料配比、工厂店铺的选址……为了实现经济学最简单而又最权威的目标——“对稀缺资源进行最佳利用”，必须快速求出这些方程组的最优解。

负责计算此类复杂数学题的，是一种名为“求解器”的底层工业软件，被誉为“工业软件之芯”。它支撑起了电子设计自动化（EDA）等关键工具，也被广泛嵌入金融、交通、能源等国计民生行业的核心业务系统。因其技术壁垒高、研发难度大，几十年来，商用求解器一直被少数国外厂商垄断。

印卧涛口中的“这件事”，就是自研一款求解器。

不仅是追赶，更剑指下一代求解器技术。在全球经济发展和数字化浪潮造成的新挑战下，他敏锐地嗅到了人工智能、分布式计算等新技术将给求解器领域带来革命。

因此，他最终没有选择挖那 100 多人，而是招募了一批愿意在这个小众领域闭关修炼的数学天团。

经历 26 个版本的迭代，一度被国外厂商斩断后路，这一闭关，就是四年。

当一帮“赛手车”决定去“造汽车”

“印老师，你就明确说一句话，是不是要做通用求解器。”

王昕等一声发令枪已经等了很久。

“又不是做不出来，”这位曾经的信息学奥赛金牌得主身上带着天才少年式的自信，“但不能中途摇摆。”

在美国哥伦比亚大学读博和麻省理工学院做博士后时，他的研究方向就是运筹学。期间在某金融巨头实习时，王昕深刻感受到商用求解器性能的掣肘，也参与过 “摇摆路线”：

资金资产管理相关的运筹优化异常复杂，如一亿用户和几十家机构的匹配问题，涉及到的决策变量规模就可达到数十亿级，远远超出单个求解器的处理能力。

一个优化问题往往要被拆分成上千个子问题计算后再做合并。购买大量第三方的求解器 License 来并发求解，显然不切实际。

所谓“摇摆路线”，就是走捷径，基于开源技术框架发展一套定制算法。

他印象很深，当时某个攻坚项目起码耗费了十几个资深工程师一年多的时间，调用了数千万元的算力资源，以至于一度触发了公司内部的警报邮件。

但投入这么大，也只能针对当时的业务场景做定制化求解，无法达到商用求解器的通用能力。

王昕想要确认，这一次达摩院是不是下定决心，要做一款能为各行各业通用的求解器。

从加州大学洛杉矶分校博士毕业后，袁坤也正式加入了达摩院求解器团队。

袁坤在中国科学技术大学读硕士时就跟随导师凌青与印卧涛开展过合作研究，在优化领域的顶刊上发表了一篇重要论文，阐明了分布式计算与优化求解相结合的核心理念，至今看来仍富有前瞻性。

在达摩院这支求解器小分队里，他继续扮演“突击队员”的角色，借助在人工智能和分布式计算领域的丰富经验，尝试开拓新的求解器技术路线。

与此同时，正做着一份与求解器毫不相关工作的黄国凌，接到了面试邀约。

在美国西北大学读博时，他师从运筹学泰山北斗桑杰·梅洛特拉（Sanjay Mehrotra）。梅洛特拉在确立两阶段随机优化方法收敛性方面做出突破性成果，广泛应用于能源、库存和财务预算管理等领域。其为美国国家器官移植系统所做的决策优化尤为人称道。

毕业跟随导师创业失败后，他连换了三份其他领域的工作，“就像分手后连恋人的照片都不想看到。”但在工作之余，黄国凌还是忍不住把求解器作为一项爱好，“偷偷”开发并开源到网上。

正是这个表现不俗的玩票作品引起了印卧涛的注意。

带着成熟的工程和产品化经验，黄国凌的加入，大大增强了达摩院求解器团队打通基础科学和产业应用的能力。

除了这些国际顶尖高校的科班毕业生，印卧涛也在阿里巴巴内部发掘了不少“野生”人才。

孙谋、李济炜和王孟昌就是被阿里云 “逼”出来的优化求解专家。如果虚拟机创建方案不够精细，物理服务器上会形成大量“碎片”，不仅浪费巨大的计算资源，也会让新的虚拟机无处放置。

实时调度上百个大型机房，单个集群物理机规模达 10 万以上，这需要求解一系列数百万整数变量的混合整数规划问题。而业务落地能等的时间，通常只有几分钟、甚至几秒。

再放眼外部，规模举世罕见的物理基础设施网络和数字基础设施网络连接着 14 亿人口的生产和生活，这些巨型方程组的求解难度可想而知。


工作之余的孙谋还是全网播放量破百万的 BeatMaker

孙谋觉得，国外“老字号”虽然不断更新，但“它们本质上还是几十年前的单机软件，当时肯定考虑不到现在的机器动不动就几百 G 、几十垓。现在是云计算和数字化的时代，面对的问题规模和并发度完全不一样了。”

哪怕只是一个很小的规则，比如只能应用在 8G 的机器上，都会极大限制上层的生态应用。

规则写在不开源的国外商用求解器里。要想从源头上掌握主动权，只能自己去做求解器。

王昕问出的那个问题，同样早已盘旋在这些人的心头。

这一次，印卧涛给了两个字的答复：

“是”和“做”。

这相当于一帮嫌跑车不够快的赛车手，决定去造汽车。

在一幅画里，找到单纯形法最后的秘密

如果把待求解的数学模型比喻为一个个待加工的零件，那么通用求解器就像一座复杂的工厂，内设十几个车间、上百条生产线用于开展不同的加工操作。

托住整个工厂的底座，是最为古老的线性规划（LP）算法。

1939 年，苏联数学家和经济学家康托罗维奇开创性地提出线性规划，并据此模型研究了工业生产的资源合理利用和计划等问题，获得诺贝尔经济学奖。

1947 年，美国数学家乔治·丹齐格首次写出了基本线性规划模型的数学形式，并提出了著名的求解方法——单纯形法，被 IEEE 评为“二十世纪十大算法”之一。

然而商用求解器中的单纯形法远比书本上的描述要复杂。为了提高效率，它们采用了很多藏在成千上万篇技术资料里的偏门技术，包括规则选择、数值处理以及针对特定结构的算法。

这自然是达摩院求解器团队需要啃下的第一块硬骨头。

他们面临的日常是：好不容易根据教材和论文又开发出来 10 个算法，但这些算法之间怎么衔接、细节怎么处理，都要自己摸索。

他们只能看到一个结果：用目前的方式，比别人慢。

“现在的商用求解器也是人开发出来的，而且他们现在研发进度慢了。我们只要专注，肯定能赶上。”这帮年轻人的傲气，是他们坚持下去的最强动力。

成绩在班里排第一的北大学霸靳哲，当时还是实验室里的一名实习生。因为不善言辞，面试差点被拒掉，最后关头才被印卧涛“捞”了回来。

也是近乎一声不吭地，他花了一个暑假，独立提出了一个新的预处理方法及其后处理，并对该方法做了理论上的研究和推广。

所谓预处理，就是正式求解之前对数学模型进行简化的模块。其中涉及到近百种处理方法，每种处理方法又涉及到上百行逻辑复杂的代码。“这相当于连做了 100 张奥数卷子，且每张得分都在 95 分以上，才能不触发一个 BUG 。”王昕评价。

袁坤在一阶法上的探索，也为单纯形法进一步提速。作为一种在机器学习领域常用的优化方法，一阶法非常擅长应对大规模数据量，缺点是求解精度不高。

但换个思路，一阶法可以先作为粗解，帮助求解器快速锁定一个最优解附近的起点，再交由其他算法完成“最后一公里”的求解。

2020 年的夏天，经历了一年全员“发狠”，达摩院自研求解器逐渐成型。

正如一个交响乐队，在每种乐器、各个声部练习纯熟之后，他们想尝试合奏一曲。

团队把这个雏形版本搬上国际公开的数据集去测试，却被当头浇了一盆冷水：

在将近三分之一的例子上，它都要比商用求解器慢上很多。

这意味着，一定还有“任督二脉”没有打通。他们开始重新排查每一个环节的细节、扎进文献的海洋寻找灵感，卡了好几个星期，却仍然毫无头绪。

内外交困之际，王昕把视线收回到了待求解的问题本身，正如学生时代专注解一道数学题一样——

他把其中一个例子在纸上画了下来。

那是一个工厂的最优选址问题，各个点看似散乱地分布在整张地图上，但渐渐地，核心区域里有一块近似规整的、对称的正方形浮现出来。

模型的对称性。这就是单纯形法最后的秘密。正如电商平台上两个只买过一件商品的用户，或者金融机构两个结构类似的资金池，在求解时其实可以被简化为同一个变量。

那难解的三分之一，由此迎刃而解。

2020 年 8 月，达摩院自研求解器 MindOpt 的的单纯形法模块，登顶国际权威第三方测评 Mittelmann 榜单，一举打破世界纪录。

是从 0 起步，也是后发优势

这个内部定义为 V0.9.0 版本的自研求解器，不仅成功求解出了测评中全部 40 个线性规划问题，并且取得了快于第二名 10% 的速度优势。

这当然绝不是靠破译被巨头厂商们隐藏起来的秘密就能实现的。

将一阶算法从机器学习领域移植到优化求解问题、针对求解器应用场景自主设计的轻量级分布式引擎，以及底层框架原生多机多线程的设计，这些创新设计都呼应了最前沿的发展趋势，充分利用新技术实现求解加速。


MindOpt 成功求解全部 40 个线性规划问题，且速度最快

很快，一封来自某国外巨头厂商的拒信，伴随着荣誉而来：

这家阿里的求解器供应商，在得知达摩院正在自研求解器之后，决定拒绝续费 License 的申请。

惊愕之余，达摩院求解器团队更多感到了一种释然。

毕竟，单纯形法只是最基础的求解器模块，后面本就有更具挑战的山头要跨越。国外厂商的釜底抽薪，在某种意义上反而验证了达摩院走上自研道路、主动掌握话语权的正确性。

被断后路，唯有背水一战。

秉持同样的“追赶+超越”的策略，达摩院求解器又经历了几次大版本更新，新增网络流单纯形法、多线程单纯形法（V0.15）、凸二次规划（V0.19）、混合整数线性规划（V0.20）、半定规划（V0.23）等功能，逐渐覆盖主流的优化问题。


达摩院求解器自研历程

其中，2022 年 8 月正式上线的混合整数线性规划（MILP）至关重要。

这是求解器应用最广泛的模块。毕竟，人们在现实生活中所接触到的事物大多数是整数的，不能启用半个发电机，也无法调派半部送货卡车。但线性规划求解速度上倍数级的差异，在混合整数线性规划上会体现为指数级。

孙谋决定从 0 开始，搭建这座求解器工厂里最具挑战性的车间。

他使用了“敬畏”这个词：

“工业软件我还是很敬畏的，它就好像飞机发动机的一颗螺丝，未来会被搭载到庞然大物上去。所以我们一定不能让它是一个空中楼阁，一定不能让它里面有一些我们不理解、不掌握的东西。”

数学上，混合整数线性规划属于 NP 问题，是一类不确定能在多项式时间内解决的复杂问题，也没有明确最佳的算法。这就意味着，孙谋需要把所有能起到一点作用的几千种算法都实现出来，再加以组合设计。

这是一段国外已经摸索过几十年的路程，退回到起点再出发，孙谋坦言不是没有过压力。

“有将近一年的时间，你在网上随便下载一个开源求解器，都能比我们的算得快。”

但从 0 开始自研，也能带来“后发优势”。

达摩院求解器团队设计的原生并发框架支持灵活的现代多核、多并发的算力利用方式，并预留了 AI 适配工具的接口，帮助解决求解器用户经常需要手动适配特定场景的痛点。

针对能源、金融、物流、云计算等重点场景，达摩院求解器也开发了多种新的预处理、启发式等技术来利用特定的问题结构，进一步加速求解过程。

孙谋尤其感激的是，在那打不过开源版本的一年间，并没有人真的跳出来挑战。达摩院给予了基础科学和颠覆性创新必需的耐心。

根据团队在运筹与管理科学学会（INFORMS）2023 年会上的分享，从 2022 年 4 月到 2023 年 7 月，针对国际权威混合整数线性规划数据集上的 240 个测例，达摩院求解器可求解的问题数从 100 个增加到 193 个，将近翻了一倍，求解时间从 1643 秒降至 400 秒。

同台分享的另一家国外老牌求解器厂商，拿出的则是一张整整 12 年的进化图。

“他们的起点比我们高，终点却比我们低了，”孙谋感慨。


黄国凌在 INFORMS 2023 年会上作分享

黄国凌在学生时代就曾多次参加这个会议，只是都是台下的听众。现在，不管是字面意义上还是比喻意义上，“我们终于站在了同一个舞台上。”

随着各模块不断被验证、完善，共迭代 26 个版本，2023 年 10 月，在印卧涛决定自研求解器的 4 年后，达摩院求解器 MindOpt 的 1.0 版本正式发布。

一块由达摩院主动投下的石头

更让达摩院求解器团队感到欣慰的，是技术在现实业务场景中取得的价值。

从一开始，达摩院就没有把求解器开发视为闭门造车。马云在 2017 年创立达摩院时明确表示，达摩院要活得比阿里巴巴更长久。只有以创新技术帮助解决社会问题，才能活得长久。

因此，早在单纯形法登顶榜单，吸引不少内外部客户问询之后，团队就决定将自研求解器搬上云端，成为国内首个可云上直接使用的商用求解器，与现实场景里的求解问题正面碰撞。

在云计算领域，除了服务器资源的配置优化，帮助实现了上亿元的计算资源节省，达摩院求解器创新性地把故障检测抽象为一个规划问题，故障洞察准确率大于 90% ，风险排查提效近百倍。2023 年，这套“达灵”云计算资源管理系统入选了中国工业与应用数学学会（CSIAM）的落地应用认证名单。

在金融资产管理领域，达摩院求解器从预处理开始去缩减模型规模，引入 Jacobi ADMM 并行计算技术加速整体计算效率，帮助将 10 亿级参数的全链优化求解压缩到半小时内完成。

而最具挑战性的领域之一，是电力调度。

中国发电总量和电网规模位居世界第一，为了满足不停波动的电力需求，同时使整个电网的总发电成本最低、消纳更多绿电、碳排放量最少，电网需要频繁地协调几百上千台发电机组的发电功率。

数百万整数变量被紧紧耦合在一起，任何一处调节的影响都会以光速扩散到整个电网，牵一发而动全身。

通过综合运用基于松弛退化移动的启发式邻域搜索算法、最大团增强的线性约束传播等创新技术，并成功抓取和利用了电力特殊结构，达摩院自研求解器在工信部产业发展促进中心等单位主办的首届能源电子产业创新大赛上拿下“电力用国产求解器”第一名。

在与中国南方电网电力调度控制中心的合作中，达摩院求解器帮助实现从 15 分钟到秒级的调度，准确率超过经验丰富的调度员。国电南瑞南网调控技术分公司业务专家张彦涛表示：“新一代 V1.0 版本达摩院求解器，测试 MILP 的求解性能有非常大的提升，在电力现货市场的部分计算场景里，求解性能比肩海外求解器，甚至有所超越。”

更多人用上达摩院自研求解器的同时，达摩院求解器团队还在不断突破传统框架，相继推出了自研建模语言、调参器、优化平台和“AI工程师”等降门槛利器。

以调参器（MindOpt Tuner）为例，这个工具应用了浙江大学博士张梦源和华中科技大学博士王孟昌负责研发的黑盒优化技术。不同于线性规划或者混合整数线性规划，黑盒优化常用于求解目标函数难以用数学公式解析表达的复杂参数优化问题，比如芯片架构设计优化、工业生产原料配比优化等。

其中的关键，在于不断利用已有输入参数对应的输出函数值学习目标函数的特征，进一步反向调整新的输入参数值，以高效迫近最优参数所在的位置。

在利用黑盒优化技术获得 GECCO 2022 国际竞赛第一名，成功破解虚拟电厂的调度难题后，达摩院求解器团队便决定进一步将该技术应用于云端调参器产品中，以满足求解器用户的自动调参需求。

在 MIPLIB2017 数据集和开源 Cbc 求解器上测试，MindOpt Tuner 调参器可让 75% 的问题求解速度提升 1 倍以上，最大提速 600 多倍。

如今，作为北京航空航天大学副教授，张梦源相信，在其研究的通信网络资源优化问题中，达摩院求解器有望发挥更大的价值。

加入北京大学国际机器学习研究中心的袁坤，也建立了课题组继续与达摩院合作，通过探索超大规模优化问题的自动分解与加速算法，让分布式计算真正成为求解器的“助推器”。


达摩院决策优化平台

自 1952 年丹齐格开发出基于单纯形法的计算机系统算起，求解器已经有超过 70 年的历史。而数字化和智能化浪潮里涌现的数字经济种种新挑战，是新一代求解器必须回应的时代命题。

黄国凌在读大学的时候，最喜欢的一本书是英特尔前总裁安迪·格鲁夫（Andrew S. Grove）写的《10 倍速时代》。这本书说的是，上一个小时造就你的因素，下一个小时就可能颠覆你。无论企业或个人，都必须随时接受改变。

“印老师当时告诉我，那就由我们主动投下一块石头，看看能激荡起什么样的回响。”

Nicolas2050

牛逼哄哄的。