离散优化求解器大搜罗

『运筹OR帷幄』原创

作者：留德华叫兽

1

前言

这篇文章笔者一年前就已开始构思，苦于时间有限而迟迟没有下笔。今天终于鼓足勇气，动笔时间晚上11点，今天就算通宵也要把它写完～

言归正传，由于笔者背景偏重于整数规划，因此本文大量篇幅将介绍整数规划求解器。

当我们费劲千辛万苦对一个实际问题用整数规划建模以后，写成如下优化问题：

http://u6.gg/ebNqf

我们知道，建模完成后要求解具体的实例，下一步便是设计相应算法。

而求解整数规划模型的基本算法便是分支定界法：

那么我们是否要亲自手撸一遍分支定界法呢？

几十年前，当市面上这些求解器还不存在的时候，很不幸的告诉你：当然需要！

这是我与欧洲运筹协会主席、巴塞罗那理工Elena Fernandez（http://u6.gg/ebMR8）教授亲切会谈后她给我的回答。

当时作为一名运筹学研究精确算法的博士生毕业难度（代码能力）可想而知。

而今，正因为有了优化求解器的存在，我们只需将以上整数规划模型的系数矩阵输入到优化求解器中，它就能够给我们快速求出最优解或可行解（除了分支定界法还集成了各种花式启发式和割平面算法）！

因此，运筹学博士生的毕业难度大大降低！

整数规划求解器是什么？

大家可以把它理解为一个专门求解整数规划模型的算法包，你可以用任何编程语言（C/C++、Java、Python）去调用这个包里的方程，只要你把你要求解的整数规划模型目标方程和系数矩阵输入进去（告诉它你要求解的具体问题），它就会给你求解出结果。

怎么样，是不是很神奇？

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

2

商业整数规划求解器

1. IBM ILOG Cplex

没错，就是笔者在意大利Blogna“实习”半年所在的求解器公司

网址：IBM ILOG CPLEX Optimization （Studiohttp://u6.gg/ebMWm）

支持模型：混合整数（平方）规划、Constraint programming

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

特点：支持Benders分解模块（仅此一家）、速度Top2

当前版本：12.8

2. Gurobi

支持模型：混合整数（平方）规划、Constraint programming

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

特点：速度Top1、价格最高

当前版本：8.0

3. FICO Xpress

网址：FICO Xpress Optimization | FICO（http://u6.gg/ebNb5）

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

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

当前版本：8.5

4. MOSEK

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

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

特点：解SOCOP、SDP更快

当前版本：8.1

价格：

因为是商业软件，意味着他们是收费的

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

http://u6.gg/ebNnS

MOSEK售价为1950刀起

从价格可以看出，Gurobi是目前的NO.1（一个小插曲，或许是因为SCIP创始人Tobias Achterberg从Cplex跳槽至Gurobi以后的事）

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

3

开源整数规划求解器

1. SCIP

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

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

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

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

当前版本：6.0

2. GLPK、LP_Solve

网址：lp_solve reference guide、GLPK（http://lpsolve.sourceforge.net/5.5/）

摘抄一段Gurobi官网对这俩个开源求解器的介绍：

http://u6.gg/ebNv8

3. COIN-OR旗下的CBC和SYMPHONY

网址：COIN-OR Branch-and-Cut MIP Solver（https://projects.coin-or.org/Cbc）、SYMPHONY（https://projects.coin-or.org/SYMPHONY）

这里还是重点介绍下COIN-OR这个组织吧

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

它的网址：The COIN-OR Foundation（https://www.coin-or.org/about-the-foundation/）

4. 华人求解器

中科院的CMIP

上海财大|杉数科技主导的Leaves优化求解器

4

求解器大PK

市面上琳琅满目的求解器，到底该用哪个好呢？

这时候就需要Public Dataset和Benchmark给你一些参考了

这里我仅贴出几个对比的案例：

http://u6.gg/ebPcn

http://u6.gg/ebPdw

5

其他优化求解器

以上重点介绍了数学规划中整数规划的求解器

熟悉运筹学的同学们知道，数学规划除了整数规划，还有凸优化、非凸优化、半正定规划、锥规划等等。

什么？对以上术语一无所知？请点击：

【学界】人工智能的“引擎”--运筹学，一门建模、优化、决策的科学（http://u6.gg/ebPht）

Again，COIN-OR（http://u6.gg/ebPj8）上面罗列着几乎所有的开源优化求解器

这里我就简单地介绍其中一个--Couenne

为啥？

因为Couenne的开发者，是笔者在Clemson读博期间的导师Pietro Belotti博士（后跳槽至FICO Xpress）。

Couenne (Convex Over and Under ENvelopes for Nonlinear Estimation) is a branch&bound algorithm to solve Mixed-Integer Nonlinear Programming (MINLP) problems of the form:

6

高级建模语言

GAMS、AMPL、JuMP、Mosel、Glop

这里仅作简述

他们又是做什么的？

作为一种高级建模语言，首先可以把一个数学规划问题更简单地编程

其次，它可以调用以上任意一种优化求解器（如果兼容，Mosel只能调用Xpress）

这样，你只需写一遍code，便可比较多种不同的求解器，然后取结果最好的那个。

P.S.：其实很多软件，例如Matlab甚至Excel都自带了优化模块，可以解线性规划和整数规划问题。

由于他们不是专门做数学规划的，因此只能说可以用，关于效率和速度，和专门做这个的求解器，是没有对比价值的。

7

展望

运筹学与国民经济、企业供应链、能源交通等优化息息相关，这些实际问题都可以被建模成为运筹学模型。

而优化求解器是数学规划建模后求解这些实际问题的核心，这个核心长期被国外软件公司所垄断（黑盒子），华人在此领域在2017年以前几乎是空白。

进入运筹学领域7年多以来，结识了全球很多华人运筹学者。一大感觉便是，研究启发式、进化算法、元启发算法的华人学者占了多数，而研发求解器所必须的精确算法华人学者却屈指可数。

CMIP和Leaves的出现打破了这一僵局。

衷心希望它们早日能与世界一流的求解器匹敌，为国筑器！

P.S.：熬夜写到凌晨俩点，总算完成了拖了一年的任务，希望这个总结对大家有帮助。

错误和疏漏在所难免，恳请大家留言指正。

文章作者：留德华叫兽