线性规划求解器总结与比较 | Blog of Zhikun Zhang

link管理

链接快照平台

输入网页链接，自动生成快照
标签化管理网页链接

求解器及官方 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 源码安装步骤了：

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 , MOSEK 和 DSDP 。

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]