离散优化求解器大搜罗

『运筹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.:熬夜写到凌晨俩点,总算完成了拖了一年的任务,希望这个总结对大家有帮助。

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

文章作者:留德华叫兽

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180806A1P9EW00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券