干货 | 运筹学、数学规划、离散优化求解器大PK，总有一款适合你

前言

不知道大家，

对于复杂的线性规划问题，

特别是变量很多的那种，有什么办法呢？

难道真的要亲自用电脑撸一遍代码，

把结果跑出来？

几十年前，

当市面上这些求解器还不存在的时候，

很不幸的告诉你：当然需要！

当时作为一名运筹学研究精确算法的博士生

毕业难度（代码能力）可想而知。

而今，正因为有了优化求解器的存在，

我们只需将以上整数规划模型的系数矩阵，

输入到优化求解器中，

它就能够给我们快速求出最优解或可行解

（除了分支定界法还集成了各种花式启发式和割平面算法）！

那么，整数规划求解器是什么？

大家可以把它理解为，

一个专门求解整数规划模型的算法包，

你可以用

任何编程语言（C/C++、Java、Python），

去调用这个包里的方程，

只要你把你要求解的，

整数规划模型目标方程和系数矩阵输进去，

告诉它你要求解的具体问题，

它就会给你求解出结果。

怎么样，是不是很神奇？

废话不多说，今天我们来梳理一遍市面上流行的整数规划求解器！

Part1 商业整数规划求解器

1. IBM ILOG Cplex

CPLEX 是IBM公司的一个优化引擎。软件IBM ILOG CPLEX Optimization Studio中自带该优化引擎。该软件具有执行速度快、其自带的语言简单易懂、并且与众多优化软件及语言兼容（与C++，JAVA，EXCEL，Matlab等都有接口），因此在西方国家应用十分广泛。由于在中国还刚刚全面推广不久，因此应用还不是很广，但是发展空间很大。

支持模型：

该优化引擎用来求解线性规划（LP）、二次规划（QP）、带约束的二次规划（QCQP）、二阶锥规划（SOCP）等四类基本问题，以及相应的混合整数规划（MIP）问题。

支持语言：C/C++、Java、Python、Matlab等

当前版本：12.8

CPLEX Studio IDE（集成开发环境）的主窗口及其主要区域和控件如下：

CPLEX具有的优势：

（1）能解决一些非常困难的行业问题；

（2）求解速度非常快；

（3）有时还提供超线性加速功能的优势。

2. Gurobi

Gurobi 是由美国Gurobi公司开发的新一代大规模数学规划优化器，在 Decision Tree for Optimization Software 网站举行的第三方优化器评估中，展示出更快的优化速度和精度，成为优化器领域的新翘楚。

支持模型：

Gurobi 可以解决的数学问题：

l 线性问题（Linear problems）

l 二次型目标问题（Quadratic problems）

l 混合整数线性和二次型问题（Mixed integer linear and quadratic problems）

支持语言：C/C++、Java、Python、Matlab等。

当前版本：8.0

Gurobi 优势特点：

（1）采用最新优化技术，充分利用多核处理器优势

（2）任何版本都支持并行计算，并且计算结果确定而非随机

（3）提供了方便轻巧的接口，支持 C++, Java, Python, .Net 开发，内存消耗少

（4）支持多种平台，包括 Windows, Linux, Mac OS X

（5）支持 AMPL, GAMS, AIMMS, Tomlab 和 Windows Solver Foundation 建模环境

（6）单一版本，开发版本也就是发布版本，程序转移便捷

（7）Gurobi 为学校教师和学生提供了免费版本。

（8）和 Matlab 有便捷接口。

3. FICO Xpress

FICO Xpress是一款出色的商业优化求解器。

支持模型：混合整数（非线性）规划、Constraint programming

支持语言：C、C#、Java、VB.NET、Python、Matlab等

特点：速度Top3，支持鲁棒优化

当前版本：8.5

4. MOSEK

MOSEK提供了特定解决线性编程、混合整数编程以及其它非线性转换优化问题。

支持模型：混合整数（平方）规划、Second-order cone programming、Semidefinite programming、General convex nonlinear

支持语言：C/C++、Java、R、Python、Matlab等

特点：解SOCOP、SDP更快

当前版本：8.1

价格如何？

因为都是商业软件，当然涉及价格问题啦。

以下这份价格列表转自高级建模语言AMPL的官网：

MOSEK售价为1950刀起。从价格可以看出，Gurobi是目前的NO.1。

好在学生|高校|科研用途都是免费的，只需学校邮箱即可免费下载并使用！

Part2 开源整数规划求解器

1. SCIP

官网介绍：SCIP is currently one of the fastest non-commercial solvers for mixed integer programming (MIP) and mixed integer nonlinear programming (MINLP). It is also a framework for constraint integer programming and branch-cut-and-price. It allows for total control of the solution process and the access of detailed information down to the guts of the solver.

开发地：德国柏林ZIB研究中心（该中心毕业的博士就职于二中各大求解器公司，share着办公室并一起交流，得益于德国的一个政府项目）

支持：混合整数（非线性）规划、Constraint integer programming

支持语言：C/C++、Java、Python、Matlab等

特点：支持Branch&Price（仅此一家）

当前版本：6.0

2. GLPK

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

GLPK实现了对windows的支持，但是为此，你同样需要学习它的建模语言，并且所有的操作都在 glpsol.exe 提共的命令行下完成，比较不方便，且耗时长。如果要在matlab下使用，还需要下载额外的驱动文件。

GLPK英文介绍：

GLPK for windows：

3. lpsolve

lpsolve是sourceforge下的一个开源项目，它的介绍如下：

Mixed Integer Linear Programming (MILP) solver lp_solve solves pure linear, (mixed) integer/binary, semi-cont and special ordered sets (SOS) models.lp_solve is written in ANSI C and can be compiled on many different platforms like Linux and WINDOWS

它是一个混合整数线性规划求解器，可以求解纯线性、（混合）整数/二值、半连续和特殊有序集模型。并且经过实际验证，有极高的求解效率。

从sourceforge主页上可以下载lpsolve的IDE版本，界面比较简陋，类似于如下的样子：

4. yalmip

可以说，yalmip是一位“集大成者”，它不仅自己包含基本的线性规划求解算法，比如linprog（线性规划）、bintprog（二值线性规划）、bnb（分支界定算法）等，他还提供了对cplex、GLPK、lpsolve等求解工具包更高层次的包装。更为可贵的是，yalmip真正实现了建模和算法二者的分离，它提供了一种统一的、简单的建模语言，针对所有的规划问题，都可以用这种统一的方式建模；

至于用哪种求解算法，你只需要通过一次简单的参数配置指定就可以了，甚至不用你指定，yalmip会自动为你选择最适合的算法。

总而言之，你只需要知道在matlab下如何用yalmip的方式建模，而不需要单独针对每一种工具包学习新的建模语法。

有了yalmip，你不再需要针对每一种工具包去学习特定的建模语言（比如用cplex要专门学习cplex的建模语言，用lingo要专门学习lingo的建模语言，还有GLPK、lpsolve、Matlab自带的求解器等等，如果每一种求解器都要学习新的建模语言的话，这个工作量是可想而知的）。相反，如果你选择使用yalmip，那么你只需要学习yalmip一种建模语法，因为yalmip真正实现了建模和算法的分离，所有的问题都可以用统一的方法建模，如果需要使用不同的求解器，只需要一句简单的配置即可。

因此，yalmip不仅仅是一个线性规划求解器，更强大的地方在于，它提供了一个统一的建模平台，支持现有的几乎所有的求解算法。有了yalmip，一切都变得简单起来。

5. CBC和SYMPHONY

CBC和SYMPHONY是COIN-OR旗下的两大求解器。

COIN-OR成立于17th International Symposium on Mathematical Programming (ISMP) conference in Atlanta in the summer of 2000，是一个公益组织，维护着市面上几乎所有的开源优化求解器，并且使得它们之间的交互变得可能。

其中有关CBC和SYMPHONY的介绍如下：

CBC：

Cbc (Coin-or branch and cut) is an open-source mixed integer programming solver written in C++. It can be used as a callable library or using a stand-alone executable. It can be called through AMPL (natively), GAMS (using the links provided by the Optimization Services and GAMSlinks projects), MPL (through the CoinMP project), AIMMS (through the AIMMSlinks project), PuLP, CMPL, OpenSolver for Excel, JuMP, or MiniZinc.

SYMPHONY：

SYMPHONY is an open-source solver for mixed-integer linear programs (MILPs) written in C. It can be used in four different main modes:

As a callable library through either the native C interface or through the Osi.

As an interactive solver using a command-line interface.

As a framework to build customized solvers for specific problem classes.

Through a number of different modeling languages: AMPL, GMPL, GAMS, PuLP (see below).

6. 华人求解器

LEAVES优化求解器

目前国内最知名的该是杉数科技与上海财经大学正在开发开源和商业俩个版本的求解器。

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

杉数科技的Cardinal Solver目前由斯坦福大学的叶荫宇教授带队，核心团队的六位核心科学家均为国外毕业博士，而且多人在国外各个求解器开发中曾经担任过核心职位。核心团队自2017年开始工作，进展一直比较平稳顺利。按照目前进度，按照开发进度，预期2019年夏天，线性规划求解器可以达到接近最好的商业求解器如CPLEX Gurobi的水准，整数规划求解器可以达到世界最好的开源求解器SCIP级别。二次和锥优化求解器则会以团队已有的DSDP求解器为基础进行二次开发。

CMIP

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

CMIP代码总量已经超过五万行，涵盖国际现有求解器预处理、启发式、割平面、分支、节点选择、区域传播等各种功能模块，并已经较好地具备了求解大规模整数规划的能力。例如对于MIPLIB2010测试库中具有164547个变量、328818个约束的例子MAP18，CMIP仅需847秒可求得全局最优解。

Part3 求解器大PK

目前求解器主要有开源和商业两个流派。开源的求解器国际知名的约有五六个，尤其以德国的SCIP和美国的Coin-OR为线性和整数规划代表，二次规划里Sedumi，SDPT3和DSDP比较优秀。商业求解器最有名的有四个，美国IBM的CPLEX，Gurobi，英国的Xpress，三家的线性和整数规划求解器基本上从速度和稳定性一直稳居世界前三，丹麦的MOSEK在二次规划和锥优化优势明显。

开源求解器跟商业的从表现上来讲，差别还是很大。例如最好的开源求解器SCIP在整数规划上的表现，在中小型问题上跟Gurobi和CPLEX有七倍左右差距。大问题上差距可能更明显。

求解器的开发，基本上是属于难度大，门槛高，时间长，投入高，回报有风险的行业。尤其需要对优化理论极度深入了解的基础上，对大规模计算机系统工程的开发也非常精熟。这种人才基本上国内也没有能力培养，因此人才是完全匮乏的。国内几十年来，一直没有单位愿意，也没有能力尝试。

目前，仅有少数几个发达国家拥有自己的整数规划求解器，如美国有GUROBI、CPLEX、SAS、MATLAB、CBC、SYMPHONY，德国有SCIP，俄罗斯有MIPCL和GLPK，英国有XPRESS（后被美国FICO公司收购），芬兰有LPSOLVE。

以下是的简单介绍！

国际上成熟整数规划求解器

开源整数规划求解器时间性能对比图

关于其他的性能，这时候就需要Public Dataset和Benchmark给你一些参考了

最后再补充几点

下表列出了一些优化软件库的比较，这些库目前来说，使用都是比较广泛的。

关于更多的优化器和优化软件库的介绍，大家可以点开下面的阅读原文，那里列出了更多更全面的优化器，任君选择~

---The End---

文案 && 编辑：邓发珩

指导老师： 秦时明岳（华中科技大学管理学院）

如对文中内容有疑问，欢迎交流。PS:部分资料来自网络。

如有需求，可以联系：

秦虎老师（professor.qin@qq.com）

邓发珩 （华中科技大学管理学院本科二年级：2638512393@qq.com、个人公众号：程序猿声）