0


市面上的数学规划求解器都有哪些?

运筹学从形成到发展,在此过程中积累的大量理论和方法在国防、能源、制造、交通、金融、通信等各个领域发挥着越来越重要的作用。我们在生产生活中遇到的很多实际问题,都可以通过运筹学所涉及的优化方法对其进行数学建模,表示为数学问题,而为了解决这些数学问题,求解器应运而生。

优化求解器主要以工业软件的形式,把数学规划方法用于大规模复杂问题的优化求解,是解决各种数学规划问题的核心工具,在实际生产生活中具有重要价值和意义。在工业领域,求解器作为产业链和供应链优化的核心引擎,能够为复杂应用场景提供智能决策,助力企业决策优化,实现降本增效。

目前市面上的主流优化求解器主要分为商用求解器(比如Gurobi、IBM Cplex等)、开源求解器(比如SCIP等)两大类。此外还有一些商业计算软件比如Matlab,甚至是常用的Excel表格中都包含有求解器工具,可以求解部分规模较小的数学规划问题,不过求解效率和商用求解器相比还是有一定差距。

除了上面提到的这些求解器,目前市面上还有哪些优化求解器可供选择?各自又有哪些技术优势,能够支持哪些类型的数学规划模型呢?接下来我们对市面上较常见的国内外优化求解器进行一下梳理总结!

PART1 商用求解器

1,Gurobi

Gurobi是由美国 Gurobi Optimization 公司开发新一代大规模求解器。在全球最著名的专业求解器评比网站 Decision Tree for Optimization Software (http://plato.asu.edu/bench.html) 中,Gurobi 展示出更快的求解速度和精度。Gurobi 全球用户超过2600家,广泛应用在金融、物流、制造、航空、石油石化、商业服务等多个领域。

技术优势:

(1)可以求解大规模线性问题,二次型问题和混合整数线性和二次型问题

(2)支持非凸目标和非凸约束的二次优化

(3)支持多目标优化

(4)支持包括SUM, MAX, MIN, AND, OR等广义约束和逻辑约束

(5)支持包括高阶多项式、指数、三角函数等的广义函数约束

(6)问题尺度只受限制于计算机内存容量,不对变量数量和约束数量有限制

(7)采用最新优化技术,充分利用多核处理器优势。支持并行计算

(8)提供了方便轻巧的接口,支持 C++, Java, Python, .Net, Matlab 和R,内存消耗少

(9)支持多种平台,包括 Windows, Linux, Mac OS X

支持模型:

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

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

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

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

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

支持接口语言: C++, Java, Python, .Net, Matlab 和R

最新版本:9.5

官网:http://www.gurobi.com/(中国区:http://www.gurobi.cn/)

2, IBM CPLEX Optimizer

CPLEX历史悠久,最初版本在1988年就被开发出来,1997年被ILOG公司收购,2009年纳入IBM怀抱,如今已发展成为IBM决策优化系统IBM ILOG CPLEX Optimization Studio(简称COS)。作为COS系统中的关键组件,CPLEX Optimizer 为线性规划、混合整数规划、二次规划和二次约束规划问题提供灵活的高性能数学规划求解器。 这些求解器包括用于混合整数规划的分布式并行算法,支持利用多台计算机来解决难题。

优势特点:

(1)稳健的算法

CPLEX Optimizer 已经求解具有数百万个约束和变量的优化模型

(2)CPLEX Optimization Studio 接口

使用 ILOG Concert Technology 和 CPLEX Callable Library 之类的接口,构建和部署优化应用。

(3)IBM ILOG CPLEX Optimizer 性能基准

(4)快速自动重新启动

修改线性程序,然后重新求解,所用时间只有原始求解过程的一个零头。 从众多先前解决方案开始,混合整数规划可以得到修改并求解。

支持模型:

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

支持接口语言: C, C++, Java, C# or Python APIs

最新版本:22.1

官网:https://www.ibm.com/cn-zh/analytics/cplex-optimizer

3, FICO Xpress

Xpress求解器是商业优化求解器,Xpress 包括通用非线性求解器 Xpress NonLinear,逐次线性规划算法(SLP,一阶方法)和Artelys Knitro(二阶方法)。

Xpress 于 1983 年发布,是第一个在PC上运行的商业LP和MIP求解器。1992年,发布了并行计算的Xpress版本,五年后扩展到分布式计算。2008 年被FICO收购。Xpress 是第一个通过在 2010 年引入 64 位索引而跨越十亿决策变量阈值的 MIP 求解器。自 2014 年以来,Xpress 首次实现了并行对偶单纯形方法的商业实现。

Xpress 包括其建模语言 Xpress Mosel和集成开发环境 Xpress Workbench。Mosel 包含分布式计算功能,可并行解决优化问题的多个场景。输入数据的不确定性可以通过稳健的优化方法来处理。

优势特点:

(1)能解决决策变量数千万的LP和MIP问题,以及决策变量数达数百万的一般非线性问题。数以亿计的非零问题系数在Xpress部署使用中很常见。

(2)支持开箱即用的多线程并行处理,利用多个CPU核心快速高效地解决客户最棘手的问题。

(3)提供了一套全面的高性能非线性问题解决方案,使企业能够快速、准确地解决更复杂的一般非线性问题。Xpress Nonlinear可以在几分钟的实际运行时间内解决实际业务中的数百万决策变量问题。此外,Xpress Nonlinear可以解决黑盒优化问题,允许您以调用函数的形式将外部进程作为系数嵌入和建模。

支持模型:

线性规划(LP)、混合整数线性规划(MILP)、二次规划(QP)、二次约束二次规划(QCQP)、二阶锥规划(SOCP)、混合整数非线性规划(MINLP)、混合整数二次规划(MIQP)、混合整数二次约束二次规划(MIQCQP)、混合整数二阶锥规划 (MISOCP)、一般非线性规划(NLP),一般混合整数非线性规划(MINLP)、约束规划(CP)

支持接口语言:.NET、Java、C、C++、VB、Python、Matlab、Solver API、Mosel API、BCL

最新版本:8.5

官网:https://www.fico.com/en/products/fico-xpress-optimization

4,MOSEK

MOSEK是由丹麦MOSEK ApS公司开发的一款数学规划求解器,也是公认的求解二次规划、二阶锥规划和半正定规划问题最快的求解器之一,广泛应用于金融、保险、能源等领域。

优势特点:

(1)提供优化服务器用于远程优化。

(2)充分利用多核处理器硬件特点进行并行计算;

(3)可求解的问题规模仅受限制于计算机内存容量;

(4)领先世界的内点法实现,用于求解线性、二阶锥和二次规划问题;

(5)提供基于矩阵和Fusion的编程接口,包括C、C++、Python、Java、C#、MATLAB和R;

(6)支持多种建模环境,包括AMPL、GAMS和CVX等商业工具,CVXPY和JuMP等开源工具;

(7)支持多种操作系统,包括Windows、Linux和MacOS;

支持模型:

线性规划(LP),二次约束凸规划(QCQP),二阶锥规划(CQP,SOCP),半正定规划(SDP),一般可分离凸规划(SCP)和混合整数规划(MIP)。

支持接口语言:C, C++, Java, MATLAB, .NET, Python, and R

最新版本:10.0.25

官网:https://www.mosek.com/

5,BARON

BARON(Branch And Reduce Optimization Navigator)是一种通用的非线性优化器,能够将非凸优化问题求解到全局最优。决策变量可以是连续的、整数的或两者的混合。BARON 已用于化学过程工业、制药、能源生产、工程设计和资产管理等领域的应用。BARON 可在各种平台上的AIMMS、AMPL和GAMS 建模语言下使用。BARON算法和软件的开发已获得 2004 年 INFORMS 计算协会奖和 2006 年 Beale-Orchard-Hays 奖的认可,以表彰其在数学优化协会的计算数学编程方面的卓越表现。

优势特点:

(1)用于全局优化的高级分支定界,结合了约束传播、区间分析和对偶性。

(2)对可能具有许多局部最优解的问题进行全局优化。

支持模型:

线性规划(LP)、一般非线性规划(NLP)、混合整数规划(MIP)、一般混合整数非线性规划(MINLP)

支持接口语言:支持所有主要接口,包括Python、Julia、MATLAB、AIMMS、AMPL、GAMS等。

最新版本:22.9.30

官网:https://www.minlp.com/baron-solver

6,Lingo

LINGO是Linear Interactive and General Optimizer的缩写,即“交互式的线性和通用优化求解器”,由美国LINDO系统公司(Lindo System Inc.)推出的专门用于求解最优化问题的软件包。其特色在于内置建模语言,提供许多常用函数方便使用者建立优化模型时调用,并提供与其他数据文件(如文本、EXCEL、数据库等)的接口,易于方便地输入、求解和分析大规模最优化问题。

优势特点:

(1)方便的模型表达

内置建模语言允许您以一种易懂的直观的方式来表达模型,更加容易构建模型,更容易维护。

(2)方便的数据选项

允许您直接与数据库、电子表格程序交换数据来构建模型、生成报告。

(3)众多的内置函数

自带了众多的函数,包含大量数学,财经,集合,概率密度,接口,报告等函数。

(4)方便的数据选项

能够直接以多种方便的格式来管理您的数据。

(5)电子表格程序能力

直接链接到电子表格程序的能力允许您充分利用电子表格程序环境的功能和灵活性。

(6)数据库能力

使用ODBC技术来允许您访问在任何常用Windows数据库应用程序中的集合信息和数据。

(7)强大的求解器

拥有一整套快速的、内建的求解器用来求解多种数学规划问题,甚至不需要指定或启动特定的求解器,LINGO会读取您的方程式并自动选择合适的求解器。

(8)交互式模型或创建Turn-key应用程序

对于开发交互式模型,LINGO提供了一整套建模环境来构建,求解和分析您的模型。对于构建turn-key解决方案,LINGO提供的可调用的DLL和OLE界面能够从用户自己写的程序中被调用。LINGO也能够从Excel宏或数据库应用程序中被直接调用。

(9)详尽的文档和帮助

LINGO提供了所有的您需要快速启动和运行的工具。您能得到一本LINGO User Manual,该手册详尽的描述了程序的命令和功能.同样高级版本带有一本更大的Optimization Modeling with LINGO手册,这是一本综合教科书,讨论了所有主要的线性,整数和非线性优化问题分类.LINGO同时还带有许多基于真实世界的案例可用来修改和扩展。

支持模型:

线性、非线性(凸和非凸/全局)、二次、二次约束、二阶锥、半定、随机和整数规划。

支持接口语言: C/C++, FORTRAN, Java, C#.NET,VB.NET, ASP.NET, Visual Basic, Delphi, Excel.

最新版本:20.0

官网:https://www.lindo.com/index.php/products/lingo-and-optimization-modeling

7,杉数COPT

杉数求解器COPT(Cardinal Optimizer),是杉数自主研发的针对大规模优化问题的高效数学规划求解器套件,也是支撑杉数端到端供应链平台的核心组件。COPT是目前同时具备大规模混合整数规划、线性规划(单纯形法和内点法)、二阶锥规划、半定规划以及凸二次规划和凸二次约束规划问题求解能力的综合性能数学规划求解器,为企业应对高性能求解的需求提供了更多选择。

优势特点:

(1)国产自主知识产权

在通信、能源、军事、电网、航空等领域,出于保障国家重要数据安全的目的,具有自主知识产权的优化求解器和运筹优化算法平台不仅具有极大的商业价值,更具有无可估量的社会价值。

(2)求解性能强大

2022年6月发布求解器COPT5.0版,COPT线性规划性能已超越三大全球领导品牌,整数规划性能也已位列前茅,新增半定规划SDP模块,具有强大的底层技术优势。

(3)定制化求解加速

针对客户大规模问题,进行方法和参数上的调整,和用其他求解器比,求解速度有10%~50%不同程度的提升。

(4)落地化解决方案

COPT线性及整数求解器已被应用于国家和企业的多个重要项目中,拥有丰富的落地场景。并可针对不同行业解决方案定制化,根据需求及实际情况,为客户量身定制服务。

支持模型:

线性规划、混合整数规划、二阶锥规划、半定规划、凸二次(约束)规划

支持接口语言:C、C++、C#、Python、Julia、Java、AMPL、GAMS、Pyomo、PuLP、CVXPY等。

最新版本:5.0

官网:https://www.shanshu.ai/solver

8,阿里MindOPT

MindOpt是阿里达摩院决策智能实验室自主研发的一款具备线性规划等多种功能的数学规划求解器套件。通过对大规模线性规划的快速稳定求解,为客户提供从数据到决策的全链路建模和求解能力。目前已应用于云计算等多项阿里业务,通过对弹性计算资源的调度优化,每年可为阿里云节约数亿元成本。

优势特点:

(1)高速优解:求解器运算快、求解质量优;

(2)适用类型广:可求解的问题规模大、适用问题类型广;

(3)授权方式灵活:可通过阿里账号云端授权,在本地运行求解器。

支持模型:目前上线公测的是线性规划、凸二次规划、混合整数线性规划。

支持接口语言:目前支持命令行和C、C++、Python、Java的API调用。

最新版本:0.21.0

官网:https://solver.damo.alibaba.com/htmlpages/page#/

9,华为天筹AI求解器OPTV

天筹(OptVerse)AI求解器将运筹学和AI相结合,突破业界运筹优化极限,针对线性和整数模型寻找最优解,以通用形式描述问题,高效计算最优方案,助力企业量化决策和精细化运营,提升资源利用率和运转效率,增强决策水平和竞争力。

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

优势特点:

(1)高效建模工具:基于图建模算法,充分利用稀疏性与并行算力,建模效率最大可以提升30倍;

(2)高效、稳定、高质量:求解速度快、优度高、性能稳定,已在华为内部供应链问题上成功求解亿级变量/约束超大规模数学模型;

(3)自适应学习优化:融合前沿AI能力,可根据问题特征自适应进行参数调优和求解策略选取,实现最大30%的求解效率提升;

(4)原生支持分布式加速求解:依托强大云上算力,支持超大规模分布式并行加速;

(5)全行业场景全流程决策支持:支持结合 ModelArts 平台向用户提供全流程决策优化能力;

(6)简单易用,快速上手:支持云服务RESTful API、ModelArts notebook内置SDK的C++/python接口等多种开发和调用方式。

支持模型:混合整数线性规划(MIP)、线性规划(LP)

支持接口语言:云服务RESTful API、ModelArts notebook内置SDK的C++/python接口等

最新版本:0.2.6

官网:https://www.huaweicloud.com/product/modelarts/optverse.html

PART2 开源求解器

1,SCIP

SCIP是目前混合整数规划(MIP)和混合整数非线性规划(MINLP)最快的非商业求解器之一。SCIP也是一个用于约束整数规划、分支定界以及分支定价的框架[CCZ1] ,主要由德国ZIB研究所开发。与大多数商业求解器不同,SCIP 允许用户对求解过程进行完全控制,并允许用户访问求解器内部的详细信息。[JJD2]

优势特点:

(1)用于混合整数规划的最快的非商业求解器之一

(2)支持Branch&Price

支持模型:混合整数(非线性)规划

支持接口语言:C、C++、Java、Python、Matlab等

最新版本:8.0.2

官网:https://scipopt.org/

2,Coin-OR开源项目套件 CLP/CBC/CGL/SYMPHONY等

这里主要介绍下COIN-OR这个开源项目。

COIN-OR (Computational Infrastructure for Operations Research) 是运筹和优化圈维护开源基础软件和项目的著名基金会,是一个公益组织,维护着市面上几乎所有的开源优化求解器,包括cbc, clp, ipopt, pyomo等数十种求解器和建模语言,并且使得它们之间的交互变得可能。可以说 COIN-OR 在开源求解器方面占有举足轻重的位置。目前所有项目都托管在 GitHub 上(https://github.com/coin-or),仅一些原有的基础设施(网站、wiki 和邮件列表)仍然托管在 Clemson 大学的服务器上。

COIN-OR 项目维护的诸多开源求解器和建模工具现在仍被全球数千个组织使用,其中值得注意的是Cbc、Clp、Ipopt这三个求解器在各自的领域中仍然处于十分领先的地位(线性规划、混合整数规划和非线性规划)。

官网:https://www.coin-or.org/

3,LP_solve

LP_solve是一个混合整数线性规划(MILP)求解器,来自sourceforge下的一个开源项目,是一个基于修正单纯形法和分支定界法的免费线性(整数)规划求解器,能够求解纯线性、(混合)整数/二进制、半连续和特殊有序集(SOS)模型。

支持模型:纯线性、(混合)整数/二进制、半连续和特殊有序集(SOS)模型

支持接口语言:C/C++、Java、Delphi、Free Pascal、VB、VBScript、http://VB.NET、C#.NET

最新版本:5.5.2.11

官网:https://lpsolve.sourceforge.net/5.5/

4,GLPK

GLPK (GNU Linear Programming Kit,GNU线性编程工具)是GNU下的一个项目,用于建立大规模线性规划LP和混合型整数规划MIP问题,并对模型进行最优化求解。由于是GNU下的项目,因此没有商业非商业的版本限制,可以自由使用。

最新版本:4.60

官网:https://www.gnu.org/software/glpk/glpk.html

5,谷歌 OR-Tools

OR-Tools是一款谷歌旗下的开源优化工具。支持线性规划、整数规划,可以方便的求解Routing、Bin packing、Network flows、Assignment、Scheduling等问题。

优势特点:

(1)具有跨平台性。OR-Tools的核心算法是用C++进行编写的,这使其具有跨平台性。此外,它同样可以用于Python、Java或C#编译过程。

(2)是面向不同问题的优化工具套件。OR-Tools集合了各种先进的优化算法,它所包含的求解器主要分为约束规划、线性和整数规划、车辆路径规划以及图论算法这四个基本求解器,能够按照优化问题的类型,提供相对应的不同类和接口。例如:对于最简单的线性规划问题,可以使用Linear Solver来解决。

(3)开源且开放。OR-Tools可以免费使用并且公开源代码。此外,OR-Tools还支持第三方求解器,可接入CPLEX等商用求解器以及SCIP等开源求解器。

支持模型:线性规划、整数规划、约束规划、混合整数规划等

支持接口语言:java、c++、c#、python

最新版本:9.4

官网:https://developers.google.cn/optimization

6,中科院CMIP混合整数求解器

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

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

优势特点:

CMIP整数规划求解器采用了一种广义系数缩紧割平面(GCSC)的技术。该割平面技术由CMIP团队自主提出,对于一般的整数规划问题具有一定的改善效果,尤其对于网络设计问题效果显著。通过MIPLIB2010国际公认标准整数规划测试库的测试对比,CMIP求解器的性能已经超过传统的求解器GLPK(俄国2000,Google Optimization Tools中的整数规划求解器)以及LPSOLVE(芬兰2004,GAMS高级建模系统调用其解决整数规划问题)。

7,Leaves优化求解器

开源的LEAVES项目主要由上海财经大学的并行优化国际实验室与杉数科技共同牵头建设,主要聚焦于一些最新大规模一阶和二阶算法的探讨。2017年公布了第一版的线性规划求解器的源代码,包括了内点法求解线性规划的完整算法,这在开源求解器里是比较少见的,代码基本可以通过Netlib的问题集测试。包括了完整的Presolve,LU分解,CrossOver等商业求解器的全流程。目前把求解变量限制在50万以下,在Netlib上测试结果跟Gurobi相比差距还不错。

PART3 其他软件集成

1,MATLAB

MATLAB是一个包含大量数学函数库的应用程序,每个数学函数都可以从用JavaScript编写的脚本中调用。 MATLAB提供了多种面向不同问题的数学规划求解器,适用问题规模较小。

用户可以使用JavaScript编写的称为Solver类的简单构造,在运行时从MATLAB调用任意数学函数。用于MATLAB的求解器类可以通过其API调用外部MATLAB工具,并将强大的数学函数直接链接到正在运行的仿真中。

官网:https://ww2.mathworks.cn/

2,SAS

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

官网:https://www.sas.com/en_us/home.html

3,SCIPy

SciPy 是一个开源的 Python 算法库和数学工具包。Scipy 是基于 Numpy 的科学计算库,用于数学、科学、工程学等领域,很多有一些高阶抽象和物理模型需要使用 Scipy。SciPy 包含的模块有最优化、线性代数、积分、插值、特殊函数、快速傅里叶变换、信号处理和图像处理、常微分方程求解和其他科学与工程中常用的计算。

python科学计算生态栈中的顶级开源库scipy提供了大量的数值优化求解器,尤其以optimize模块最为显著,其提供了统一的数值优化求解器接口minimize(),虽然方便使用,但是也对非数学专业的人员初次使用时带来存选择困难,尤其是十几种方法统一由同一个接口调用,各方法使用限制、优缺点难以把握,

官网:https://scipy.org/

4,Excel

日常使用的office办公套件中的Excel表格也包含一个称为“求解器”的工具,能够针对问题规模较小的线性规划问题进行求解。Excel不会默认加载求解器工具,有需要的用户要进行简单的操作来实现:1,选择”文件“,点击”选项“;2在弹出的Excel选项框中点击”加载项“,选择”excel加载项“,点击”转到“;3,在弹出的加载宏对话框中勾选"规划求解”,点击“确定”;4,在数据选项卡中查看使用已添加的求解器solver工具。


国内外优化求解器还有很多,本文仅做了部分分类整理,如有错误和疏漏,还请大家留言指正。

内容来源声明:本文由【ML OR 智能决策】整理,部分内容来源于官网及网络分享,如有内容侵权,请联系删除!

(关注 ML OR 智能决策。分享更多干货,欢迎交流~)


本文转载自: https://blog.csdn.net/mlorworld/article/details/127518910
版权归原作者 ML OR 智能决策 所有, 如有侵权,请联系我们删除。

“市面上的数学规划求解器都有哪些?”的评论:

还没有评论