线性规划求解器总结与比较

目前的一个研究课题,需要求解一个大规模的线性规划问题,变量规模至少在 10 万的水平,需要找到找到一个高效的求解器。为此,专门花时间对比了 CBC, GLPK 等开源求解器和 CPLEX, GUROBI 等商用求解器,并对比了求解器官方 Python 接口及 CVXOPT, CVXPY, PuLP 等第三方 python 接口的求解效率。

求解器及官方 Python 接口安装与使用

这篇教程主要介绍类 UNIX 系统(包括 Linux, Mac OS, AIX, Cygwin 和 MSys 等)下的安装与使用,window 下的安装由于笔者并没有亲自试验过,就不详细讲解了。如果有需要,大家可以自行在网上查找资料。

CBC

CBC 是开源基金会 COIN-OR (Computational Infrastructure for Operations Research) 开发的线性规划求解器。该基金会开发了大量的运筹学工具,截止 2011 年,已经开发并维护了 48 个项目。

CBC 有很多安装方案,这里仅介绍笔者实验成功过的 Git 源码安装的方式,其他方式可以参考官方文档

假设我们想要安装稳定的 2.9 版本,cd 到我们想要安装 CBC 的目录,然后执行:

1
git clone --branch=stable/2.9 https://github.com/coin-or/Cbc Cbc-2.9

下载完 CBC 源码后还要下载相应的依赖,否则会报错:

1
2
3
cd Cbc-2.9
git clone --branch=stable/0.8 https://github.com/coin-or-tools/BuildTools
./BuildTools/get.dependencies.sh fetch

有了源码和依赖,我们就可以执行典型的 Linux 源码安装步骤了:

1
2
3
4
5
mkdir build
cd build
../configure
make
make install

CBC 有一个 COIN-OR 官方开发的 Python 接口 CyLP。安装方法可以参考官方文档,不过按照教程,笔者尝试了各种方法都没有成功,这里就不详细讲解了。如果有人安装成功了,可以在评论区分享你的经验。

GLPK

GLPK (GNU Linear Programming Kit) 是 GNU 项目开发并维护的一个线性规划工具包。在 Ubuntu 和 MacOS 下安装 GLPK 非常简单,用它们相应的安装工具就好了:

1
2
sudo apt-get install glpk // Ubuntu
sudo brew install glpk // MacOS

GLPK 好像没有官方 Python 接口,不过可以很容易得被后面讲到的 CVXOPT, PuLP 和 CVXPY 等第三方接口调用。

CPLEX

CPLEX 是 IBM 开发的一个商用线性规划求解器。社区版只能解决变量数量低于 1000 以及约束数量低于 1000 的问题。好在 IBM 提供了供高校学生和老师使用的完整版本,通过教育邮箱注册即可获得。首先前往购买学生版链接,点击 add to cart,会跳转到登录和注册页面,此时可以用自己的教育邮箱注册一个账号,然后就可以免费获得 CPLEX 了。CPLEX 在 MacOS 上的安装非常简单,在自己的账户下载安装包,双击安装包,按提示一步步安装好就行。

CPLEX 提供了官方 python 接口,需要通过安装文件里的 setup.py 文件进行安装,具体方法为 cd 到 CPLEX 的安装目录,然后运行 setup.py 进行安装:

1
2
cd cplex_home_path/python
python setup.py install

直接运行 setup.py 将把 python 接口安装到默认位置,如果想要指定安装目录,可以指定 –home 参数:

1
python setup.py install --home python_package_home/cplex

我一直使用 pyenv 来管理 python 环境(使用方法可以参考我之前的博客),所以在我的电脑上,python_package_home 一般在 ~/.pyenv/versions/anaconda/lib/python/site-packages/cplex。使用这种方法,python 文件放在 CPLEX python 目录下的 cplex/bin/python/cplex 里面,在程序里面直接 import cplex 无法识别,需要把里层 cplex 目录里面的文件复制到外层 cplex 目录:

1
cp -ri path_to_site-packages/cplex/bin/python/cplex/* path_to_site-packages/cplex/

这样就可以正常 import cplex 了,具体的编程方法可以参考 [5]

GUROBI

GUROBI 也是一个商用求解器,实测其性能比 CPLEX 可能要稍微好一点。一点点八卦,GUROBI 是 CPLEX 的三个创始人离职后开发的一个求解器,名字是三个创始人姓氏的前两个字母组合(Zonghao GU + Edward ROthberg + Robert BIxby)。

安装方法也很简单,前往官网下载相应版本,然后根据readme的步骤安装。在 MacOS 下直接双击安装包就行。GUROBI 也提供了教育版 license [7],利用教育邮箱就能申请到一个有效的 license,然后根据官方教程安装即可使用。

GUROBI 的 python 接口可以直接使用 conda 来安装:

1
2
conda config --add channels http://conda.anaconda.org/gurobi
conda install gurobi

具体编程方法可以参看 [13]

Python 第三方接口安装与使用

CVXOPT

CVXOPT 的安装非常简单,直接用 conda 安装就行:

1
conda install cvxopt

CVXOPT 实际上是一个凸优化工具包,并自带有线性规划求解器,但效率不是很高。但它可以调用外部求解器 [8],包括 GLPK, MOSEKDSDP

CVXOPT 的使用方法可以参考它的官方文档 [9]

CVXPY

CVXPY 是 Stanford 的 Steven Boyd 课题组开发的,做凸优化的同学肯定看过他的《Convex Optimization》这本书。CVXPY 也可以用 conda 进行安装:

1
2
conda install -c conda-forge lapack
conda install -c cvxgrp cvxpy

CVXPY 是一个纯粹的 python 优化工具接口,它本身并没有实现任何求解器,都是根据问题类型调用相应的外部求解器 [10],然后解析结果。对于线性规划问题,可以调用外部的 CBC, GLPK, CPLEX, GUROBI, MOSEK 等。需要注意的是,当需要调用 CBC 时,必须先安装其官方 python 接口 CyLP;当需要调用 CPLEX 时也需要先安装其官方 python 接口。

CVXPY 的建模过程非常直观,可以使用 numpy 的 ndarray。具体使用方法可以参考它的官方文档 [11]

PuLP

PuLP 可以使用 pip 进行安装:

1
pip install pulp

PulP 也可以调用 CBC, GLPK, CPLEX, GUROBI 等外部线性规划求解器。具体使用方法可以参考它的官方文档 [12]

求解器及其 python 接口的性能比较

下面列出的结果仅仅基于我目前一个关于最小流的研究课题,更全面的分析与比较可以参考文档[1]

  • GLPK 对于变量规模很大的线性规划问题求解速度非常慢。
  • CPLEX 求解大规模线性规划问题非常快,但是使用官方提供的方法建模时间非常长。实际测试,在变量规模为 65536 时,建模花费 20s 左右,求解花费不到 1s。当使用 CVXPY 调用 CPLEX 时,同样规模一共花费 5s 左右,推测主要时间也是花费在建模上面。
  • 比较 CVXPY 调用默认求解器,CPLEX, GUROBI,发现速度差距不大,相对来说 GUROBI 可能会稍微好一点。

有用链接

[1] Comparison of Open-Source Linear Programming Solvers
[2] CBC install
[3] Linear Programming in Python with CVXOPT
[4] CLPEX for student
[5] Using the python API
[6] Installation tutorial
[7] Gurobi For Universities
[8] Linear programming for cvxopt
[9] CVXOPT tutorial
[10] Choosing a solver for CVXPY
[11] CVXPY tutorial
[12] PuLP tutorial
[13] GUROBI python interface

Contents
  1. 1. 求解器及官方 Python 接口安装与使用
    1. 1.1. CBC
    2. 1.2. GLPK
    3. 1.3. CPLEX
    4. 1.4. GUROBI
  2. 2. Python 第三方接口安装与使用
    1. 2.1. CVXOPT
    2. 2.2. CVXPY
    3. 2.3. PuLP
  3. 3. 求解器及其 python 接口的性能比较
  4. 4. 有用链接
|