导读
MindOpt 是阿里巴巴达摩院决策智能实验室研发的优化求解器，它主要用于解决各行各业的决策优化问题。MindOpt 作为我国自主研发的高性能优化求解器，不仅打破了国外技术垄断，还在多个领域内展现出了广泛的应用潜力和卓越的性能表现。
1.
达摩院优化求解器 MindOpt 的诞生与迭代
2.
MindOpt Suite 套件各模块介绍与性能表现
3.
MindOpt 在各场景中的应用
4.
问答环节
分享嘉宾｜
王孟昌
阿里巴巴达摩院
研究员
编辑整理｜
曾晓辉
内容校对｜李瑶
出品社区｜
DataFun
达摩院优化求解器 MindOpt 的诞生与迭代
1.
达摩院优化求解器 MindOpt/敏迭
MindOpt/敏迭求解器是阿里巴巴达摩院决策智能实验室自主研发的高性能国产优化求解器，已广泛应用于互联网、云计算、电力能源、制造、物流、航空、金融等领域中的规划、计划、调度、排产、排班、控制等场景，在电力、制造等调度问题上拥有领先的求解性能。
最早我们通过自研算法来支撑阿里集团内部和外部的一些业务场景应用，如电商、云资源调度、服装生产中的布料裁剪等场景。随着阿里面临的业务问题越来越复杂，规模越来越大，当时最主流的国外求解器也渐渐没法满足应用上的要求。于是到 2019 年，我们开始着手自主研发求解器以满足自身的应用。经过一年多的打磨，MindOpt 于 2020 年 8 月份第一次发布，并在国际权威数学优化求解器榜单 Hans Mittelmann benchmark 榜单上一举夺冠，成为首个在榜单上超过国外竞品的国产求解器。之后的三年，通过阿里云向全社会开放下载，不断完善求解器的功能和效率，同时也积极拥抱 AI 技术做进一步的优化。到 2023 年发布了 MindOpt1.0 版，并在 2023 年底工信部的求解器大赛中摘得桂冠。2024 年发布了 2.0 版本，也开启了国际业务的合作。
在过去几年间，我们深入研究电力场景的优化问题，与电力企业展开了多项长期合作，MindOpt 对电力问题的适应性也得到了业内的认可，同时在国内外和电力优化相关的一些赛事上拿了不少冠军，积累了更多声誉。
2.
从业务问题到优化模型
求解器的应用场景广泛，比如一个机场，有一条跑道供飞机起飞时滑行，现在有很多架飞机都在等待起飞，该如何安排这些飞机的起飞时间才能使整体的准点率最高？
面对这样的求解问题，首先收集已知的数据，比如每架飞机计划的起飞时间，这个时间一般是乘客在购票的时候，票面上显示所在航班的预计起飞时间；然后要知道每架飞机容许的最早和最晚的起飞时间，以及飞机与飞机之间必须要留出来的起飞时间的间隔，防止飞机之间互相影响，造成安全事故。要确定的是每架飞机实际的起飞时间，可以把时间划分到分钟，或者更细的时间颗粒度。
具体的建模过程中，引入待定的未知数，比如 X_it，它是决策变量，用 X_it=1 来表示一架飞机被安排在时刻t起飞，否则 X_it=0。借助 X_it 这个决策变量写出此场景下具体业务目标的表达式，让实际起飞时间与计划起飞时间的偏差最小。
X_it 的确定还受到一些客观条件的限制，比如只有一条跑道，那么在时刻t最多只能有一架飞机起飞，飞机也不允许在它容许的时间窗之外去起飞，如果起飞得太早，可能乘客都还没有到机场，起飞得太晚，乘客的行程会被耽误，因此在时间窗之外的 X_it 强制等于 0。
类似的限制还有起飞间隔之间的数量关系，还有一个隐含的条件，就是飞机只能起飞一次。
把这些数据、目标、变量以及条件组织起来，通过优化模型输入到 MindOpt
”敏迭”求解器，就能够计算出最优的 X_it 值，可以根据优化模型的求解去安排飞机的实际起飞时间。这是一个比较简单的优化模型的例子。
MindOpt Suite
套件各模块介绍与性能表现
1. MindOpt
决策智能套件
MindOpt Solver 求解器是 MindOpt 决策智能套件的一个主要组件，除了 MindOpt Solver 求解器外，还包括 MindOpt APL 建模语言、MindOpt Tuner 调参器、MindOpt Copilot AI 建模工程师，以及由开发环境、机器学习、强化学习、分布式组件等构成的开发平台 MindOpt Studio。
2. MindOpt
优化求解器
MindOpt 开发套件通过集成多种决策智能的开发工具，能够为用户的决策应用提供非常方便快捷的平台支撑。
在构建优化模型时，可通过三种方式把模型输入到求解器中进行求解。
-
第一种方式是通过标准的通用模型文件格式，比如 MPS、LP、NL 等通用优化问题数据格式，直接输入到求解器中，就可以启动求解；
-
第二种方式是通过编程语言，比如 C++、Python、Java 等编程语言来调用求解器的 API，把模型的各个部分在求解器里建立起来，然后启动求解流程；
-
第三种方式是通过建模语言，比如常见的 Gams，以及开源的 pyomo 和 PuLP，还包括达摩院自主研发 MindOpt APL 建模语言。
MindOpt 优化求解器，可以在 X86、ARM 架构的 CPU 上运行，包括国产的鲲鹏、海光等国产 CPU，支持的系统包括 Windows、Linux、OSX 等操作系统以及国内常见的操作系统。目前 MindOpt 已实现对线性规划、非线性规划、整数规划的支持，还包括约束不可行分析以及回调函数等功能。
3
.
MindOpt
优化求解器
阿里达摩院于 2024 年 11 月初在北京发布 MindOpt 求解器 2.0 版本，相比于之前的 1.0 版本，在线性规划以及凸二次规划数据集上，MindOpt 求解器 2.0 版本有效解的算例数量稳步提升，平均求解速度提升了将近 4 倍；在混合整数线性规划的数据集上，求解速度平均提升了 26%。
此外，还新增了对 Convex MIQCP 这一类问题数据集的支持，在相关的数据集上，求解速度、可求解的算例数量上具有明显优势，平均求解速度处于领先地位。
4. MindOpt
APL(MAPL)
：高效的建模语言
MindOpt APL 简称 MAPL，是阿里达摩院自主研发的建模语言，相对于一般的编程语言，它的好处是能够用比较接近数学的方式把模型建立起来。如鲁棒线性回归的问题，用 Python API 进行建模，要写很多 API 的调用代码，若直接使用 MAPL 建模语言，仅需几行代码。
这种建模语言，对于做一些快速的原型验证，以及在复杂问题上的模型搭建，以及之后的检查都非常有帮助。
为了让我们的建模语言效率更高，从问题结构的探测与利用、模型重写以及高效底层数据结构、算数运算互换，还包括基于模型成本的多项式展开技术以及计算图前向-后向计算等角度对建模语言的效率进行提升。
目前针对千万变量的技术组合问题，建模提速了 120 倍，远远超越了其它的建模语言。
针对非线性规划以及非线性混合整数规划，建模速度提高了 20 倍，是开源建模语言的 2 到 8 倍。
5. MindOpt Tuner
：调参器
MindOpt Tuner 是套件中超参调优的工具。
在设计求解算法的时候，不可避免地会引入一些超参数，这些超参数可控制算法求解的流程，或者一些具体行为。不同的超参数可能适用于不同的场景，在我们拿到问题之后，怎么去选择合适的超参数，这对于问题的有效求解是一个非常重要的环节。
如 MIPLIB 的例子，它的矩阵如上图，用开源的 Cbc 对它进行求解，求解时间在默认参数下需要求解 24, 000 秒，若用商用的求解器只要 46 秒。通过去选择、去搜索适合这个问题的超参数，配置到开源的 Cbc 后，比开源求解器求解的时间要更短，也就是说通过配置超参数，能够让求解的速度实现 1, 000 多倍的提升。
怎么找到适应场景的超参数？MindOpt Tuner 调参器通过黑盒优化的方法进行超参数的搜索。通过收集到场景里的一批例子后，通过对不同的超参数进行评估，然后去推理更好的超参数，这种方式可以得到适合对应场景比较有效的超参数。
使用 MindOpt Tuner 调参器，对 MIPLIB 上面的 240 个例子进行调参的试验，发现对 Cbc 进行超参配置的调优，最大的加速倍数达到了 1, 200 倍，平均的加速是 17.85 倍，参数对于算法效率的影响提升是非常明显的。
6. MindOpt Copilot
：基于大语言模型的建模助手
在现实中问题千变万化，每一个具体场景的业务逻辑都会不一样。如果可以使用AI 来辅助场景建模，交付效率可得到大幅提升，甚至可做到端到端的交付。
基于大语言模型构建的 MindOpt Copilot，可帮助用户快速建立数学模型。
为让大语言模型能够进行问题的理解、形式化抽象和数学建模，在准备基础的大语言模型和算力之后，从数学题库、专家标注以及公开的网页渠道获取大量有效的优化问题，然后再通过提示词工程，进行 few-shot 少样本学习，大模型产生回答之后由专家对回答的质量进行评估，正确的回答会连同问题一起进入训练集；错误的回答经专家订正之后再进入训练集，然后扩充训练集到一定规模之后，再对大模型进行 fine tuning 微调。
这样不断提高大模型回答问题的正确率，实现对用户问题的理解，以及能够正确建立相应的数学模型，并且通过后台调用求解器来得到问题的结果。
MindOpt Copilot，可以直接在 MindOpt 官网上进行体验，使用自然语言对问题进行描述，然后 Copilot 就可以把对应的数学模型建立起来，相当于给 AI 一道应用题， AI 理解后把方程给列出来，接下来 AI 会使用我们的建模语言对模型进行建模，然后调用求解器进行求解，得到结果之后再用自然语言的形式对结果进行解释。
7. MindOpt Studio
：集成开发平台
我们将上述功能、组件都集成到了套件中，以 MindOpt Studio 的形式向用户做呈现以及供用户使用。在 MindOpt Studio 中提供了集成的开发环境，包括基于 Vscode 和 Jupyter 的不同开发环境，其中还集成了机器学习、深度学习以及强化学习的一些常用组件，以及我们自主研发的 eForecaster 预测组件。
这些组件集成到平台上，大家可快速基于 MindOpt Solver 开发求解器的应用，以及求解器与机器学习进行结合的应用。平台还集成了分布式计算服务，可以实现对闲置计算资源以及异构计算资源高效的纳管，用户在平台上提交自己的计算任务，由平台去寻找合适的计算资源来执行计算任务。
MindOpt
在各场景中的应用
1. MindOpt
应用：云资源调度
首先要介绍的 MindOpt 应用场景是云资源调度，它需要处理的问题是怎么把用户所需要的虚拟机在物理机器上开辟出来。
对于虚拟机来讲，它有内存的需求，也有 CPU 的需求。如果一台物理机上内存不足，但 CPU 还有剩余，也是无法放置虚拟机的，此时就需要把不同的物理机上面的虚拟机进行重新排布，以腾出空间来容纳新的虚拟机。
比如在上图中的场景，上面的三台物理机都没法容纳新的这一台虚拟机，如果把第三台物理机中这个小的虚拟机挪动到其它物理机上面，就腾出了新的空间，能够容纳新的虚拟机了。通过这种腾挪，能够节省物理机的需求，扩充集群容纳新的虚拟机的能力。
较大的集群可能有数千台物理机，会涉及到上万乃至十万以上的虚拟机。这种情况可以建模成一个混合整数规划问题。经过研究以及算法的改进，求解耗时从之前的几个小时降到了 10 分钟左右，集群的容纳能力得到了显著提升。
对于一个云平台来讲，有很多机群，会涉及到非常多的物理机，10% 容纳能力的提升就意味着数亿元成本的节省，因此在云资源调度场景里，优化求解技术对整个云平台运营是非常重要的。
2. MindOpt
应用：石油生产混流优化
在石油生产里有一个经典的问题是混流（blending）问题，也称 pooling 问题，通常是指把不同的原料进行混合。比如中东的石油、北欧的石油，以及国内生产的石油，其成分、质量都不一样，pooling 问题要解决的问题是把不同的原材料按照一定的比例进行混合，使得成分能够满足下游不同的需求。这里需要确定的是不同的混合比例，这是一个非线性规划问题。
对这一类问题，MindOpt 无论在有效求解数量还是求解速度上，和国外竞品相比都处于比较领先的地位；特别是在大规模的非线性规划问题上，相比于国外的求解器，能够有效求解更多的算例，并且在求解时间上也具有优势。
3. MindOpt
应用：投资组合优化
在投资组合场景中，也可以应用 MindOpt 优化求解器。
假设有一笔资金，需要投资到不同的项目上，不同的项目预期收益率会有差异，可以收集这些项目预期收益率的数据，形成预期收益率向量；同时不同项目之间，预期收益率不一定是完全相互独立，可能会存在相关关系，可用收益率协方差矩阵来表示资产之间的风险关系。
针对投资组合问题，需要确定有限的资金按照什么样的比例投资到不同的项目里去。这里比例的和等于 1，同时比例得是非负的，防止做空。它的投资收益，就是每个项目的投资比例乘以它的预期收益率。如果再考虑到风险控制的要求，可以写出不同的投资比例所对应的风险，让这个风险小于预定的风险水平，然后考虑对风险的厌恶程度，可以写出如上图中所示的效益函数，用预期的收益率减去对风险的厌恶系数（越大表示我们越不能接受风险）。再考虑到交易的成本，可得到最终的效益函数。
做投资组合需要实现效益函数最大化，可写出如下的优化模型。
这个模型属于二次规划模型，使用 MindOpt 可高效求解。
在实际场景里，可能有些项目是必投的，有些项目有最大、最小投资量要求，模型就需要引入额外的整数变量，问题就变为混合整数二次规划模型。
对于混合整数二次规划模型，MinpOpt 也具备领先的性能，在投资组合的优化数据集上，和国外的竞品相比，MindOpt 有效求解的数量，以及求解时间都具有明显的优势。
4. MindOpt
应用：资金调度优化
资金调度优化场景与投资组合优化场景类似，也是需要考虑投资的风险。
如在一个平台上有很多资金池，每一个资金池在这个平台上持有的资产会有一个目标的规模，不同的资产风险水平会不一样。如果把高风险资产全部集中到一个资金池，那资金池就会承担非常高的风险。平台通过对高风险资产进行腾挪，就可以实现整个平台上整体风险的最小化，这时可建立以下的模型。
这个模型可以很方便把问题转换成一个标准的线性规划模型。而线性规划模型的一个难点在于变量的规模特别大，达到 10 亿的规模，一台机器可能装不下。
一个简单的处理方法是把它切成一个个小块，分别进行求解，然后再把求解的结果拼起来，作为原问题的一个解。这个方法在实际中是能够得出一个解的，但是离最优解还有一段差距，也就意味着通过这种方法所得到的资金调度方案没有达到最小的风险水平。
我们引入了如上图所示的算法，在原来线性规划模型进行切分之后分别求解，求解之后再引入迭代机制，对这个解进行修正，之后再对构建的子问题再进行求解，通过这种迭代求解的方式，可以收敛到原问题的最优解。
在具体实施的时候，把原模型进行分解，不同的切片分配到不同的计算资源上，然后在计算资源上去调用 MindOpt 去求解二次规划的子问题，得到结果之后进行迭代，不断修改这个子问题里面的一些参数，最终得到的解就是原问题的最优解。
这种迭代求解的方法和原来那种粗暴的切分方式进行对比，求解的时间确实会慢一些，但可以保证最优性，同时得到最优解的整体风险水平会比原来的方法显著降低。
5. MindOpt
应用：发电机组调动优化
阿里达摩院对电力领域的优化求解问题也展开了研究，在电网领域发电机组调度是一个很重要的问题，发电机组调度问题在业内也称为机组组合问题，主要用于确定电网中数百、数千台发电机组在未来各个时段的开关机状态以及发电功率，在确保发电量与用电量平衡且电网线路安全的同时，尽可能减少整体的发电成本。
这个问题本身是一个非线性问题，但在实际求解的时候会做线性化或是线性的近似处理，把它转化成一个混合整数线性规划模型。这个模型规模会非常巨大，若一个电网里面有 100 台机组，那么相应的整数变量就有 3 万个。对于像南方电网这种大规模的区域电网来讲，规模会更大。
考虑发电成本的分段线性特点，以及不同机组最小开停机时间的要求，以及比如火电机组不能随意调整调节发电功率，需要遵循爬坡的条件约束，综合这些约束之后，可以写出以下的模型（这是一个简化的模型，实际生产中的模型要复杂得多）。
对于一个区域电网来讲，模型变量可以达到上百万的规模，求解时间可能要求在十几分钟、二十分钟或者半个小时之内进行求解，这对于求解器是一个非常大的挑战，现在学术界也有很多研究关于如何加速求解的问题。
为此我们用省级电网的数据集，以及大规模区域电网的数据集，对我们的求解器进行了测试。在测试的过程中不断改进我们的算法，使得我们的算法在效率上能够更加适应场景的需求。在省级电网数据集的性能表现上，和国外的求解器进行对比，在一部分模型里面，能够比较明显的优于国外的竞品，在一部分上面能够做到基本持平。
在这种大规模的区域电网技术组合的数据集上，比如机组 1, 000 多个、节点超过 5, 000 个，变量数量达到 200 万，约束的数量达到 100 万，对于这么大规模的求解问题，需要控制在 1% 精度内，是相当困难的。在这一问题上，我们能够显著超过国外竞品。在此基础上，结合强化学习做进一步加速的求解，效率能够达到国外竞品的两倍。
在电网里常见的优化问题包括日前机组组合问题，日内的前瞻调度问题，以及实时断面越限恢复的场景等。目前已实现大规模日前调度问题的快速求解，求解效率可以追平甚至超越国外竞品。
在日内前瞻调度领域，我们求解了世界上规模最大的超过 5 万个节点的日内前瞻调度问题，在这个问题上实现了 4.36 倍的效率领先。在这个场景里，客户要求在五分钟之内解决，使用国外的求解器需要将近 20 分钟才能够解完，这显然是无法满足用户诉求的，而使用 MindOpt 求解器能够在五分钟之内顺利得到最优解。
实时断面越限恢复问题的产生原因包括一些突发事件，比如大型风力发电机突然没风不发电了，这会对电网产生比较大的冲击，有可能造成一些线路电流或功率过大，如果不及时采取措施的话，可能会造成严重的安全事故，这时就需要在很短的时间内做出调节的动作。之前完全依赖老专家的经验来做调节，现在通过强化学习和求解器的结合，实现了秒级的辅助决策，平均耗时只需要 10 毫秒就能够生成高质量的调节方案，准确率也达到了这些老专家的水平。
MindOpt Studio 除了应用在阿里自身的交付项目的开发之外，还支撑了南方电网两届 AI 调度大赛，支持近百支队伍同台开发测试，机器学习应用的开发以及训练都可以通过 MindOpt
Studio 平台来进行，还可以和业务数据进行对接来实现比赛中应用与真实数据在流程上的打通。
以上就是关于 MindOpt 求解器以及 MindOpt Suite 套件在一些具体场景的应用情况。
问答环节
A1：可以，通过官网就可以进入到这个平台上面，可以直接跑起来。
Q2
：
计算性能快是用的特别的线性计算库，还是针对不同场景去做算法迭代细节的优化？
A2：计算性能快源于多方面因素。有时候要看问题本身的结构，若有些问题的结构以前没有碰到过的，这时我们的算法里可能没有对这种结构做相应的处理，此时它的求解速度就会比较慢；一旦我们识别了这种结构，知道怎么把它转化成能够快速求解的形式，它的速度就会快起来。也还包括其他一些方法的结合，是一个综合的结果。
Q3
：
很多人关注 AI +求解器的模式，您如何看待这个技术方向？如何处理两者融合的难题？比如优化方案的最优性、可解释性、复现、求解实现等。
A3：从求解器的角度来讲，AI 确实能够帮助求解器去做计算以及建模的加速。
如最优超参的问题，怎么针对一个新的问题快速去获取它所对应的最佳的超参数，若用图神经网络对问题进行表征，通过我们已知的某些问题，它在某些超参数下效果就特别好，就可以通过这个匹配的形式去找到这个问题所对应的超参数来实现加速。比如上面提到的最快的加速可以实现 1, 000 倍的加速，这在很多场景里会有很大的影响。
从 AI 的角度，比如断面越限恢复的场景，使用 AI 能够快速推理的特点， AI 的推理非常容易得到一个不能够满足约束的结果，这在很多场景里可能会造成比较严重的安全事故，因此会限制 AI 的应用，这时可以通过求解器去把 AI 的推理结果向可行域做一个投影，推理是 AI 非常擅长的，而且在很多情况下可以做得非常快，通常先通过 AI 来做推理，然后再用求解器把它拉回可行域，就能够大大加强求解结果的可解释性以及安全性。
