目前的一个研究课题，需要求解一个大规模的线性规划问题，变量规模至少在 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 | cd Cbc-2.9 |
有了源码和依赖，我们就可以执行典型的 Linux 源码安装步骤了：
1 | mkdir build |
CBC 有一个 COIN-OR 官方开发的 Python 接口 CyLP。安装方法可以参考官方文档，不过按照教程，笔者尝试了各种方法都没有成功，这里就不详细讲解了。如果有人安装成功了，可以在评论区分享你的经验。
GLPK
GLPK (GNU Linear Programming Kit) 是 GNU 项目开发并维护的一个线性规划工具包。在 Ubuntu 和 MacOS 下安装 GLPK 非常简单，用它们相应的安装工具就好了：
1 | sudo apt-get install glpk // Ubuntu |
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 | cd cplex_home_path/python |
直接运行 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 | conda config --add channels http://conda.anaconda.org/gurobi |
具体编程方法可以参看 [13]。
Python 第三方接口安装与使用
CVXOPT
CVXOPT 的安装非常简单，直接用 conda 安装就行：
1 | conda install cvxopt |
CVXOPT 实际上是一个凸优化工具包，并自带有线性规划求解器，但效率不是很高。但它可以调用外部求解器 [8]，包括 GLPK, MOSEK 和 DSDP。
CVXOPT 的使用方法可以参考它的官方文档 [9]。
CVXPY
CVXPY 是 Stanford 的 Steven Boyd 课题组开发的，做凸优化的同学肯定看过他的《Convex Optimization》这本书。CVXPY 也可以用 conda 进行安装：
1 | conda install -c conda-forge lapack |
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