【整数规划(十一)】整数规划求解器简介

kyuskoj · 发表于 2022-5-1 16:04

在上一节笔记中我们讲解了二次整数规划问题，上一节笔记内容如下所示：
1 主流的整数规划求解器介绍

在企业中面对实际的整数规划问题，我们一般是采用两步走的思路：1把实际业务转化为优化模型；2把这个优化模型导入到求解器中去求解。当我们针对实际业务建立了优化模型之后，便可以将建立好的模型直接导入到求解器中，这时候，求解器会智能地选择最适合该模型的算法，给出最优解或可行解。如下图所示：

求解器通常集成了大多数目前最顶级的算法包，并建立了API，可以让运筹学者或算法工程师非常方便的调用。求解器是经过长期打磨的软件产品，其内部有很多加速求解的小技巧，对于一般的整数规划问题而言往往有着不错的效果。这样，我们就可以将更多的精力放在数学建模上，而不用操心求解器内部具体算法的实现，我们也可以把求解器看作是一个有神奇魔法的“黑匣子”。
前面我们在学习整数规划的过程中，手动撸了很多算法，我们自己手撸的算法一般是很难超过求解器的，所以实际上我们是很少使用自己手写的算法来求解整数规划问题的。那么有三种情况需要我们自己手动写算法：

我们是为了理解算法流程，学习整数规划的知识，自己手动撸一遍算法是非常有助于学习和理解算法过程的，而在了解透彻算法流程之后真正使用的时候就可以直接调用求解器了，这时候你对求解器的机制和参数设置等问题会理解的更加充分；
你的问题具备一些特殊性质，而这些特殊的性质可以被用来设计针对性的算法，而这些是求解器所不知道的，因为求解器是针对一般的整数规划问题而设计的，这个时候你自己手动设计的算法就有可能打败求解器了；
你的问题过于复杂了求解器目前还不能求解你的问题所以你只好自己写算法了。

2 求解器评测网站介绍

那么紧接着的一个问题就是整数规划求解器目前都有哪些？如果要选择求解器的话该如何选择呢？
关于求解器的评测目前公认的是 H. Mittelmann 教授的评测网站（Benchmarks for optimization software）：http://plato.asu.edu/bench.html，由于该网站在直观性上稍微差一点，在GitHub上又有一个 Visualizations of Mittelmann benchmarks，链接如下所示 https://mattmilten.github.io/mittelmann-plots/
线性整数规划问题的各种求解器的评测结果如下所示：

图中最左边一列是各种参与测试的求解器。可以看到第一行的求解器是 Gurobi 9.5.0 版本，它排名所有求解器中第一名。第二行的求解器是 COPT 4.0.0 版本，它排名所有求解器中第二名，以此类推。中间一列是各种求解器的求解速度，以求解速度第一名的 Gurobi 9.5.0 为单位。第二名的 COPT 4.0.0 求解时间是第一名的4.19倍。（以上排名仅针对线性整数规划问题，其它规划问题也可以在上述评测网站上查阅到）。
需要注意的是上述排名中的求解器分为商业求解器（商用需要付费）和开源求解器（商用无需付费）两大类：
商业求解器：Gurobi, COPT, SCIP/spx, Matlab
开源求解器：CBC, GLPK, LP_SOLVE

商业求解器 Gurobi, COPT, SCIP/spx 都可以非常方便的申请学术版授权，如果仅仅是做学术研究的话，学术版授权完全就足够了。当然学术版授权只能用于非商业目的的学术研究，如想以商业为目的话，要么购买商业版授权，要么采用开源求解器。
商业求解器的效果远远好于开源求解器，开源求解器中最好的是CBC，它的求解时间也要比商业求解器中最好的Gurobi要慢8.59倍。
商业求解器的价格大致在5-200瓶茅台的价格之间，一般来说排名越靠前的求解器价格越高。以上价格仅供参考，具体价格还要结合授权类型，授权年限，多核心支持，多用户支持等服务内容。

大家可以根据自己的需求，结合上面的排行榜选择出合适的求解器。
3 如何安装 Gurobi

3.1 下载 Gurobi 安装包

欲下载安装包，需要在如下链接注册 Gurobi 的账号：https://www.gurobi.com/downloads/gurobi-software/ 注册完成后跳转至登录界面输入账户名和密码完成登录：https://www.gurobi.com/login/
3.2 Gurobi 免IP验证学术许可申请方法

Gurobi 免IP验证学术许可申请方法比通过IP地址验证的方法要不容易出错。Gurobi 免IP验证学术许可申请方法步骤如下图所示：

在接收到 Gurobi 的学术许可申请邮件，在该邮件中有一个激活码。将该激活码如下图所示：

然后打开CMD输入上述激活码，如下图所示：

在CMD中可以生成gurobi.lic文件，这就是我们要的许可文件，一般情况下它默认保存的路径是 C:\Users\你的用户名\gurobi.lic 在该路径下面确认一下确实是有gurobi.lic许可文件，至此表明我们生成成功。
3.3 安装 Gurobi 并配置环境变量

运行之前下载好的 Gurobi 安装包，如下图所示：

选择安装路径：

安装完成：

Gurobi安装完成之后会要求重启，如下图所示，这里先选择否：

我们打开环境变量的设置界面，如下图所示：

我们发现 gurobi 会自动添加环境变量，如下图所示。如果你发现没有自动添加上这些环境变量请自己手动添加如下环境变量：
添加用户变量，变量名： GUROBI_HOME，变量值：你的gurobi安装路径，本例中为&#34;C:\Users\WangYuan\gurobi951\win64&#34;
添加用系统变量，变量名： GUROBI_HOME，变量值：你的gurobi安装路径，本例中为&#34;C:\Users\WangYuan\gurobi951\win64&#34;
添加系统变量，变量名：Path，变量值：你的gurobi安装路径\bin，本例中为&#34;C:\Users\WangYuan\gurobi951\win64\bin&#34;

接下来我们需要添加一个对于许可文件的系统变量，变量名：GRB_LICENSE_FILE，其路径为存储 gurobi.lic 文件的地址，在本例中为 &#34;C:\Users\WangYuan\gurobi951\gurobi.lic&#34;。这样就可以让gurobi知道许可文件的位置。

最终完成所有环境变量添加后如下图所示，点击确定退出：

此时虽然我们已经完成了环境变量的修改，但是上面的设定需要重启后才能生效，因此请重启电脑后再进行下面的操作。
3.4 安装 Python 环境下的 API

前面的步骤完成之后，仅仅是完成了对于 Gurobi 的安装。大多数时候我们都是在别的编程语言(C++,Java,python,C#等)中调用 gurobi，因此我们还需要对应安装相应编程语言的 gurobi API 才能在该编程语言中调用 gurobi。接下来我们以 python 为例，演示如何在python中安装 gurobi API
首先打开 Anaconda 的命令行，如下图所示：

用cd命令进入到 Gurobi 安装目录中（本例中的安装路径为C:\Users\WangYuan\gurobi951\win64)。因此在命令行中输入 &#34;cd C:\Users\WangYuan\gurobi951\win64&#34;。进入安装路径后再运行 &#34;python setup.py install&#34; 即可完成 Gurobi 在 python 中的API安装。以上过程如下图所示：

安装完成后可以采用 conda list 命令来验证是否按照成功，这里就不再赘述了。
3.5 卸载与版本更新

右键选择 Gurobi 的安装文件，选择卸载即可。

若需要更新版本，可以按照如下两步来操作：

按照上文所述卸载原来的老版本的 Gurobi
按照本文3.3节所示安装新版本的 Gurobi 即可。

由于新老版本的学术许可是通用的，因此以往老版本的学术许可依然可以在新版本中使用，因此无需按照3.2节所述重新生成许可。所以切记切记在更新的时候不要删除原来的许可文件 gurobi.lic，如果不小心误删的话则需要向 gurobi 官方说明情况重新申请一个许可文件。
同理，在完成新版本 gurobi 安装后，对应的编程语言中的 API也需要卸载后重新安装，其流程与3.4节中是完全一样的。
4 以一个简单例子说明如何调用 Gurobi 求解整数规划问题

以美团骑手派送订单为例，假设有 $n$ 个外卖订单需要配送，有 $m$ 个骑手可以接单，骑手 $j$ 配送订单 $i$ 所需时间为 $c_{ij}$ ，决策变量为：

$x_{ij}=\left\{ \begin{array}{l} 1,\ \text{骑手}j\text{配送订单}i\\ 0,\ otherwise\\ \end{array} \right. \\$
约束1(每个订单有且仅有一个骑手配送)：

$\sum_{j=1}^m{x_{ij}}=1,\ \forall i=1,2,...,n \\$
约束2(每个骑手总接单量受到一个上限约束)：

$\sum_{i=1}^n{x_{ij}}\le D,\ \forall j=1,2,...,m \\$
上述优化问题，我们在python中采用 gurobi建模和求解，示例代码如下所示：
import gurobipy as gp # 导入 gurobi 包
from gurobipy import GRB # 导入 gurobi 包
import numpy as np

n, m = 8, 5
c = np.random.rand(n,m) # 随机生成配送时间
D = 2 # 骑手总接单量上限

model = gp.Model(&#34;food&#34;) # 建立优化模型
x = model.addVars(n, m, name = &#39;x&#39;, vtype = GRB.BINARY) # 定义决策变量 x 为 n*m 维的{0,1}变量

model.addConstrs((gp.quicksum(x[i,j] for j in range(m)) == 1 for i in range(n)), name = &#39;c1&#39;) # 约束1
model.addConstrs((gp.quicksum(x[i,j] for i in range(n)) <= D for j in range(m)), name = &#39;c2&#39;) # 约束2

model.setObjective(gp.quicksum(c[i,j]*x[i,j] for i in range(n) for j in range(m))) # 目标函数

model.optimize() # 求解
从上面例子中也可以看出，在 gurobi 中完成建模的过程是非常直观和自然的，求解的过程由求解器自行调用算法也是非常的方便。

redhat9i · 发表于 2022-5-1 16:08

大佬这个方向对计算资源要求高吗？类比于深度学习训练大模型

HuldaGnodim · 发表于 2022-5-1 16:14

要求高啊

Zephus · 发表于 2022-5-1 16:22

AMPL选择gurobi求解需要怎么安装

		自动登录	找回密码
密码			立即注册

【整数规划(十一)】整数规划求解器简介

本帖子中包含更多资源