国内外优化求解器研究现状

2021-12-09 02:39:19

1.优化求解器

1.1.CPLEX

IBM ILOG CPLEX Optimization Studio（CPLEX）是一个优化软件包。2004年，CPLEX的工作获得了首届INFORMS影响力奖。CPLEX Optimizer以使用C编程语言实现的单纯形方法而命名，尽管今天它还支持其他类型的数学优化并提供除C之外的接口。它最初由Robert E.Bixby开发，并于1988年由CPLEX商业出售，随后ILOG在2009年1月被IBM收购。

专门用于求解大规模的线性规划（LP）、二次规划（QP）、带约束的二次规划（QCQP）、二阶锥规划（SOCP）等四类基本问题，以及相应的混合整数规划（MIP）问题。

CPLEX Optimizer具有一个称为Concert的建模层，该层提供了与C++、C＃和Java语言的接口，有一个基于C接口的Python语言接口。此外，还提供了Microsoft Excel和MATLAB的连接器。最后，提供了一个独立的Interactive Optimizer可执行文件，用于调试和其他目的。

1.2.GUROBI

Gurobi是由美国 Gurobi Optimization 公司开发新一代大规模优化器。Gurobi成立于2008年，以其创始人命名：Zonghao Gu、Edward Rothberg和Robert Bixby。Bixby还是CPLEX的创始人，而Rothberg和Gu领导CPLEX开发团队近十年。

Gurobi 是全局优化器，支持的模型类型包括：

(1) 连续和混合整数线性问题

(2) 凸目标或约束连续和混合整数二次问题

(3) 非凸目标或约束连续和混合整数二次问题

(4) 含有对数、指数、三角函数、高阶多项式目标或约束，以及任何形式的分段约束的非线性问题

(5) 含有绝对值、最大值、最小值、逻辑与或非目标或约束的非线性问题

Gurobi Optimizer支持多种编程和建模语言，包括：

(1) C ++、Java、.NET和Python的面向对象接口

(2) 适用于C、MATLAB和R的面向矩阵接口

(3) 可以链接到标准建模语言AIMMS、AMPL、GAMS和MPL

(4) 通过其分析求解器和求解器SDK产品链接到Excel

Gurobi Optimizer还包括许多功能来支持优化模型的构建，其中包括：

(1) 可以灵活确定多个目标的优先级

(2) 诸如MIN / MAX、ABS、AND / OR之类的常规约束以及指标约束

(3) 具有凸、分段线性目标函数的模型用于描述某些非线性问题

(4) 任意分段线性目标函数

(5) 分布式调参，以加快参数设置的探索速度，加快求解时间

Gurobi Optimizer还可以部署在云上，以及用于服务器-客户端模式。

1.3.Xpress

Xpress优化器是商业优化求解器,主要用于求解线性规划（LP），混合整数线性规划（MILP），凸二次规划（QP），凸二次约束二次规划（QCQP），二阶锥规划（SOCP）和它们的混合整数对应物。Xpress 包括通用非线性求解器 Xpress NonLinear，逐次线性规划算法（SLP，一阶方法）和Artelys Knitro（二阶方法）。

Xpress 最初由 Dash Optimization 开发，并于 2008 年被FICO收购。其最初的作者是 Bob Daniel 和 Robert Ashford。Xpress 的第一个版本只能解决 LP；1986 年添加了对 MIP 的支持。Xpress 于 1983 年发布，是第一个在PC上运行的商业LP和MIP求解器。1992年，发布了并行计算的Xpress版本，五年后扩展到分布式计算。Xpress 是第一个通过在 2010 年引入 64 位索引而跨越十亿决策变量阈值的 MIP 求解器。自 2014 年以来，Xpress 首次实现了并行对偶单纯形方法的商业实现。

线性和二次规划可以通过原始单纯形法、对偶单纯形法或势垒内点法求解。所有混合整数规划变体都通过分支定界法和切割平面法的组合来解决。不可行问题可以通过IIS（不可约不可行子集）方法进行分析。Xpress 提供了一个内置调谐器，用于自动调整控制设置。Xpress 包括其建模语言 Xpress Mosel和集成开发环境 Xpress Workbench。Mosel 包含分布式计算功能，可并行解决优化问题的多个场景。输入数据的不确定性可以通过稳健的优化方法来处理。

Xpress 有一个称为 BCL（构建器组件库）的建模模块，它与C、C++、Java编程语言和.NET 框架接口。独立于 BCL，有Python和MATLAB接口。在 Mosel 旁边，Xpress 连接到其他标准建模语言，例如AIMMS、AMPL和GAMS。

FICO Xpress Executor使用SOAP或REST接口执行和部署 Mosel 模型。它可以从外部应用程序或从FICO 决策管理平台使用。

1.4.MOSEK

MOSEK是由丹麦MOSEK ApS公司开发的一款数学优化求解器，也是公认的求解二次规划、二阶锥规划和半正定规划问题最快的求解器之一，广泛应用于金融、保险、能源等领域。杉数科技是MOSEK在中国大陆唯一官方授权销售商，承担中国市场的销售和售后服务工作。

MOSEK可以解的数学优化问题非常宽泛（如下表格所示），其中最擅长求解的是二次规划、二阶锥和半正定规划问题，在金融、保险、能源等领域均有应用。最典型的是金融领域的资产配置问题，以优化马科维茨模型投资组合为例，本质上，这是一个权衡收益和风险、构建最优投资组合的优化问题，MOSEK求解此类问题快速且稳定。

MOSEK求解问题类型与求解算法

在第 9 版中，Mosek在其求解器中引入了对指数和幂锥的支持。它到C、C#、Java、MATLAB、Python和R语言的接口。此外，Mosek 可以与流行的 MATLAB 包CVX和YALMIP 一起使用。

总体上讲，MOSEK有以下技术优势：

提供优化服务器用于远程优化。
充分利用多核处理器硬件特点进行并行计算；
可求解的问题规模仅受限制于计算机内存容量；
领先世界的内点法实现，用于求解线性、二阶锥和二次规划问题；
提供基于矩阵和Fusion的编程接口，包括C、C++、Python、Java、C#、MATLAB和R；
支持多种建模环境，包括AMPL、GAMS和CVX等商业工具，CVXPY和JuMP等开源工具；
支持多种操作系统，包括Windows、Linux和MacOS；

1.5.SAS

SAS是由SAS Institute开发的一种统计软件套件，用于数据管理、高级分析、多元分析、商业智能、刑事调查和预测性分析。SAS是一个软件套件，可以挖掘、更改、管理和检索来自各种来源的数据，并对其进行统计分析。SAS为非技术用户提供了图形化的点击式用户界面，并通过SAS语言提供了更高级的选项。

SAS程序具有用于检索和处理数据的DATA步骤，以及用于分析数据的PROC步骤。DATA步骤具有使软件采取行动的可执行语句，以及提供读取数据集或更改数据外观的指令的声明性语句。DATA步骤分为两个阶段：编译和执行。在编译阶段，处理声明性语句并识别语法错误。之后，执行阶段按顺序处理每个可执行语句。PROC步骤由调用命名过程的PROC语句组成。程序对数据集执行分析和报告，以生成统计信息、分析和图形。有300多个命名程序，每个程序都包含大量的规划和统计工作。PROC语句还可以显示结果，对数据进行排序或执行其他操作。

SAS的最大系列产品是其客户智能产品线。用于网络、社交媒体和市场分析的众多SAS模块可用于描述客户和潜在客户，预测其行为并管理和优化交流。SAS还提供了SAS欺诈框架。该框架的主要功能是监视不同应用程序、网络和合作伙伴之间的交易，并使用分析来识别表明欺诈的异常情况。SAS Enterprise GRC提供风险建模、场景分析和其他功能，以管理和可视化风险、合规性和公司政策。还有一个主要针对银行和金融服务组织而设计的SAS企业风险管理产品套件。SAS用于监视和管理IT系统操作的产品统称为SAS IT管理解决方案。SAS从各种IT资产收集有关性能和利用率的数据，然后创建报告和分析。SAS的绩效管理产品在员工、部门和组织级别进行合并，并为关键绩效指标（KPI）提供图形显示。SAS供应链智能产品套件可满足供应链需求，例如预测产品需求、管理分销和库存以及优化定价。还有一套“ SAS for Sustainability Management”软件，可以预测环境、社会和经济影响并确定运营之间的因果关系以及对环境或生态系统的影响。SAS具有针对特定行业的产品集，例如政府、零售、电信和航空航天，以及用于营销优化或高性能计算的产品集。

1.6.SCIP

SCIP是一个混合整数规划求解器和一个用于分支定界以及分支定价的框架，主要由柏林楚泽研究所开发。与大多数商业求解器不同，SCIP 为用户提供了对求解过程的低级控制和信息。作为独立求解器运行，它是用于混合整数程序的最快的非商业求解器之一。

SCIP是作为C语言可调用库实现的。对于用户插件，提供了C++封装类。用于LP松弛的求解器不是SCIP的本地组件，而是提供一个开放的LP接口。目前支持的LP求解器有CLP、CPLEX、MOSEK、SoPlex和Xpress。SCIP可以在Linux、Mac、Sun和Windows操作系统上运行。

SCIP的设计是基于约束的概念。它支持大约20种约束类型，用于混合整数线性编程、混合整数非线性编程、混合整数全二次编程和伪布尔优化。它还可以解决斯坦纳树（Steiner Trees）和多目标优化问题。

1.7.CLP

COIN-OR LP (CLP)是 COIN-OR 项目下的 LP 问题求解器,是一个用C++编写的开源线性规划求解器。CLP包括原始和对偶单纯形法求解器，对偶和原始算法都可以使用用户提供的矩阵存储方法（除了默认的稀疏矩阵外，已经支持0-1和网络矩阵）。

它是在通用公共许可证下发布的，因此可以在没有GNU 通用公共许可证限制的情况下用于专有软件。尽管可以构建独立的可执行版本，但COIN-OR主要用作可调用库。它被设计为与任何商业求解器一样可靠，但速度要慢几倍，并且能够解决非常大的问题。

COIN-OR旨在解决线性规划问题，它的主要算法是单纯形算法。

1.8.BARON

BARON(Branch And Reduce Optimization Navigator)是一个用于解决非凸优化问题到全局最优的计算系统。该软件可以解决纯连续、纯整数和混合整数非线性问题。BARON 可在各种平台上的AIMMS、AMPL和GAMS 建模语言下使用。

BARON算法和软件的开发已获得 2004 年 INFORMS 计算协会奖和 2006 年 Beale-Orchard-Hays 奖的认可，以表彰其在数学优化协会的计算数学编程方面的卓越表现。

1.9.COPT

杉数求解器COPT(Cardinal Optimizer)，是杉数自主研发的针对大规模优化问题的高效数学规划求解器套件,也是支撑杉数端到端供应链平台的核心组件,是目前中国唯一一个同时具备大规模线性规划(单纯形法和内点法)和混合整数规划问题求解能力的综合性数学规划求解器，为企业应对高性能求解的需求提供了更多选择。广泛应用于军事、航空、航天、交通、能源等领域。

主要求解线性规划、混合整数规划和二阶锥规划问题。支持所有主流操作系统Windows、MacOS、Linux（包括Arm64平台）。支持所有主流编程接口C、C++、C#、Python、Java、AMPL、GAMS、Pyomo、PuLP等。

1.10.MindOpt

MindOpt是阿里达摩院决策智能实验室自主研发的数学规划求解器套件。通过针对大规模线性规划的快速稳定求解，为客户提供从数据到决策的全链路建模和求解能力。

MindOpt求解器可以快速求解大规模线性规划问题，目前支持命令行和C、C++、Python、Java的API调用，可在Windows，MacOS和Linux系统下使用。

1.11.OPTV

9 月 23 日召开的华为全联接 2021 上，华为云发布了「天筹」AI 求解器(OPTV)。天筹(OptVerse)AI求解器将运筹学和AI相结合，突破业界运筹优化极限，针对线性和整数模型寻找最优解，以通用形式描述问题，高效计算最优方案，助力企业量化决策和精细化运营，提升资源利用率和运转效率，增强决策水平和竞争力。

小到快递员路线选择、商铺选址，大到工厂排程、物流路径规划和金融风控等问题，都可以建成数学规划模型，用天筹(OptVerse)AI求解器进行求解。利用运筹优化算法和决策模型求解方法，将业务问题转化为数学规划模型，适用在多种复杂约束条件限制（如人力、时效、容量等约束限制）和海量数据的基础上获取全局最优方案（如成本最低、时间最短）的业务场景，助力业务实现从数据到决策的闭环。

天筹(OptVerse)AI求解器已成功支撑华为供应能力及冗余分析等13个场景的模拟应用，计划预案周期从周缩短到天，保障了高效的连续性作战。

支持求解混合整数线性规划问题（MIP）和线性规划问题（LP）
AI建模，易用高效，大幅度提升建模效率，让客户聚焦核心业务问题和诉求。
AI赋能求解，基于历史数据和问题特征自适应选择最优参数，不断挖掘求解器自身潜力，适应客户场景和问题特点。
支持基于拓扑感知的分布式并行加速，充分利用华为云分布式并行能力，给客户带来极致性能体验。

1.12.CMIP

著名陈省身数学奖获得者、冯康科学计算奖获得者、中国科学院数学与系统科学院戴彧虹研究员带领CMIP团队从2015年开始，历经30个月，终于自主研发了我国第一个具有国际水平的整数规划求解器CMIP，并于2018年3月确定版本为CMIP 1.0版本。

CMIP代码总量已经超过五万行，涵盖国际现有求解器预处理、启发式、割平面、分支、节点选择、区域传播等各种功能模块，并已经较好地具备了求解大规模整数规划的能力。

2.求解器对比

求解器	国别、性质	提供免费学术版	兼容的编程语言	解决问题	备注
CPLEX（IBM）	美国商业	是	C, C++, Java, C#, Python	线性，整数为主	IBM CPLEX Optimization Studio 是一套优化引擎（用于数学编程的 CPLEX 和用于约束编程的 CP Optimizer）、建模语言 (OPL) 和集成开发环境。进入中国早，积累用户多，在衰退。
GUROBI,独立	美国商业	是	C++, Java, Python, .Net, Matlab, R	综合	各项指标前列，Gurobi 以卓越的性能跻身大规模优化器新领袖地位，成为性价比最为优秀的企业大规模优化器首选。目前客户还在积极拓展。
Xpress(FICO)	美国商业	是	Mosel, BCL, C, C++, Java, R Python, Matlab, .Net, VB6	综合	优化技术和解决方案套件。各项指标均衡，背靠FICO，金融客户多，影响力主要在欧美。
MOSEK,独立	丹麦商业	是	C,C#,Java,MATLAB,Python,R	二次为主	重点是解决大规模稀疏问题，特别是在二次规划、二阶锥和半正定规划领域有着不俗的表现。客户主要在金融，特别是量化计算。
SAS,独立	美国商业	是		综合	SAS是传统的统计软件
SCIP,德国ZIB研究所	德国开源	是	C,C++,MATLAB,Python,Java	整数	作为独立求解器运行，它是用于混合整数程序的最快的非商业求解器之一。
CLP,多个单位和个人	美国开源	是	C++	线性	CLP是 COIN-OR 项目下线性规划问题的求解器,是一个用C++编写的开源线性规划求解器。
BARON,独立商业公司	美国商业	是	C,Python...	非线性为主	用于促进非凸优化问题的全局最优解，在非线性某些模块排名较高
COPT，杉数科技	中国商业	是	C,C++,C,Python,Java	综合	综合性数学规划软件，线性规划排名世界前列，已应用于多个国内项目
MindOpt,阿里云	中国商业	是	C,C++,Python	线性	线性单纯形法目前排第一，已应用于阿里云内部多个项目
OPTV，华为	中国商业	否	C++,Pyhton	线性,整数	将运筹学和AI相结合,针对线性和整数模型寻找最优解。
CMIP,中科院	中国商业	否		整数	涵盖国际现有求解器预处理、启发式、割平面、分支、节点选择、区域传播等各种功能模块，并已经较好地具备了求解大规模整数规划的能力

3.第三方评测

美国亚利桑那州立大学的Hans Mittelmann教授针对多种开源与商业数学规划求解器进行测评已有近20年的历史，是公认的可靠第三方测评平台。

下面列举几个常见的数学规划问题，全部评测结果见评测官网:http://plato.asu.edu/bench.html

3.1.线性规划

评测时间为：2021年11月10日

(1)单纯形法线性规划求解器

基准测试一共有40个问题，第一行表示平均求解时间(s),第二行以时间最小值为标准进行放缩,第三行表示在规定时间内解出问题的数量。

可以看出达摩院MindOpt在单纯形法线性规划评测中取得第一的成绩，杉数科技COPT和华为OPTV分别取得第二和第四的成绩。

(2)内点法线性规划求解器

基准测试一共有47个问题。

在内点法线性规划中，GUROBI求解器取得第一，杉数科技COPT紧接其次，取得第二的成绩。

3.2.混合整数线性规划

(1)混合整数线性规划基准 - MIPLIB2017

评测时间为：2021年11月13日

上半部分为单线程求解，一共有240个问题，GUROBI求解数量最多，并且用时最短，取得第一；

下半部分为多线程求解，GUROBI在求解数量和求解时间上同样领先。

(2)轻微病态的混合整数线性规划案例

评测时间为：2021年11月10日

在默认模式下使用MIPLIB2017脚本在 Intel Xeon E5-4657L（48 核，512GB）的 12 个线程上运行。给出的时间是经过的 CPU 秒数。一共有45个问题，限时3小时。

GUROBI求解出了44个问题，并且运行时间最短。杉数科技COPT取得第二的成绩，但相比GUROBI的求解数量和求解时间都有很大的差距。

(3)MILP问题的不可行性检测

评测时间为：2021年12月3日

针对MIPLIB2017在 Intel i7-11700K（64GB，3.6 GHz，8 核）上的“简单”不可行问题运行。问题规模为32个。

GUROBI求解出了最多数量29个，求解时间花费最短，评分第一。杉数科技COPT在求解数量和求解时间上位于第二位。

3.3.混合整数非线性规划

评测时间为：2021年8月15日

可行性容差设置为 1e-6。所有不成功都计为最大时间。第二行列出了解决的问题数量（共 87 个）。

BARON在混合整数非线性规划中取得第一的成绩。

4.关于Mittelmann测评

在测评网站中，我们可以发现，三大主流求解器只有GUROBI在榜，而CPLEX和Xpress没有任何测评数据。

2018年12月23日，在数学规划求解器业界有些阴霾的天空中，一声惊雷。美国亚利桑那州立大学Hans Mittelmann教授在他维护了多年的数学优化软件测评中删去了IBM Cplex，Gurobi和FICO Xpress这三个主要商业求解器的全部数据。

这一切都要从新版的MIPLIB说起。由德国科研机构ZIB所维护的MIPLIB是整数规划领域最重要的问题集。这个问题集的每个版本都是商业求解器性能评测的标杆。在2018年11月之前，一直沿用的MIPLIB 2010问题集已有七年之久，而MIPLIB 2017的征集遴选工作也持续了一年多时间。各大求解器厂商均翘首以盼，希望自己的求解器可以在最新的版本上拔得头筹。

2018年10月底，跳票许久的MIPLIB 2017终于在即将召开的INFORMS年会之前整理完毕。Mittelmann教授也于11月1日发布了MIPLIB 2017版本的测评预览。近年来在旧版MIPLIB一直领先的Gurobi在其当时刚刚完成的8.1版求解器的助力下，保持了优势。

据Mittelmann当时测评信息显示，Gurobi的速度是Cplex的1.5倍，是Xpress的2倍左右。然而，就在紧接着召开的INFORMS年会上，Gurobi在其宣传中做了一些变化，在Mittelmann教授发布的数据的基础上，有意无意放大了其他两家厂商未能完成部分的求解时间。并以此得出了Gurobi比Cplex快2.6倍，比Xpress快5.5倍的结论。

这个惊人的“优势”给他们带来曝光和名声的同时，也带来了业界的批评和竞争对手的律师函。尽管Gurobi很快的撤回了这些数据，并在其官网上发了致歉声明，此次事件还是不可逆转的改变了这个行业。

2018年12月23日，Mittelmann教授在他的网站上发布了一个简短的声明，说在IBM和FICO的要求下删除了Cplex和Xpress的数据，并在此同时也删除了Gurobi的数据。尽管之前事件的诱因是Gurobi的夸大宣传，但是Mittelmann本人并没有做错什么。Cplex和Xpress的主动退出因此也就显得略有些牵强。所以在后面的测评中不见CPLEX和Xpress的身影，三大主流软件中只有GUROBI的数据存在。