- 标签
- 热门文章
gurobi是干什么的
Gurobi是一个用于数学优化的高性能求解器，广泛应用于供应链管理、资源分配、生产调度等领域。
它提供了Python接口，使得使用Python语言能够方便地构建和求解优化模型。本文介绍Python中Gurobi的用法及案例。
求解器：助力智能决策的利器
在工业化发展进程中，底层基础技术和软件的发展非常重要，这其中有一项技术被认为是运筹优化领域的“皇冠”——求解器。
求解器技术属于典型的底层技术领域，技术门槛高、研发难度大、投入时间长且风险较高，尤其需要对优化理论有深入研究、对大规模计算机系统工程开发非常精通的科技人才。种种条件制约下，从1957年纽厄尔和西蒙（两人为1975年图灵奖获得者）等人开始研究一种不依赖于具体领域的“通用问题求解器（General Problem Solver,GPS）”到现在，60余年发展，全球主流求解器市场仍被来自GUROBI、IBM、FICO三家美国公司的产品所垄断，并且构筑了极高的市场竞争门槛。
由于求解器在工业场景中的重要作用，近几年国产求解器研发领域也在蓬勃发展，除了中科院的开源求解器CMIP外，国内一些新兴科技公司和大厂也开始投身于商用求解器研发。在ASU教授Hans Mittelmann维护的国际权威第三方求解器评测榜单中(http://plato.asu.edu/bench.html)，国产求解器在线性规划LP求解速度方面已处于全球商用求解器中的领先地位，但在其他数学规划领域，比如混合整数规划、非凸的非线性规划等方面，在求解速度、可求解模型数量上还依然落后。
那今天我们就带大家了解下求解器是什么，又能做什么？
一、求解器是何方“神器”
在介绍求解器之前，我们先从基础理论和方法出发，简单了解一下数学规划。
数学规划是运筹学的一个分支，其用来研究在给定条件下（约束条件），如何按照某一衡量指标（目标函数）来寻求工作中的最优方案。根据问题的性质和处理方法的差异，数学规划又可分成许多不同的分支，如线性规划、非线性规划、整数规划、混合整数规划、动态规划等等。
常见的数学规划问题分类
数学规划在国防、工业制造、交通物流、资源管理、金融、集成电路设计、电力管理等生产生活各个领域都有着十分广泛的应用，是在实际应用中创造价值最巨大的优化方法。我们在现实中遇到的各种类型优化问题，小到快递员路线选择、商铺选址，大到工厂生产排程、物流路径规划和金融风控等，都可以抽象成一个数学规划问题，采用数学定义的方式，定义出优化问题三要素：即决策变量、优化目标以及约束条件，进而建立不同的数学模型。
数学规划是优化问题建模的第一步，也是最为重要的一步，它界定了问题的类型和求解难度。有了数学模型，求解器就可以帮助我们求解这个问题并寻找问题的最优解。
简而言之，求解器就是用来求解数学规划问题的一类软件，在现实生产生活中具有重要价值和意义。在世界一流的企业供应链管理（SCM）软件，包括结合了运筹优化技术的生产计划与排程系统（APS）、运输管理系统（TMS）等企业决策软件中，都能见到求解器的身影。
二、主流求解器一览
目前主流求解器市场主要分为商用求解器、开源求解器两类，全球知名的商用求解器主要有Gurobi、IBM Cplex、FICO Xpress，开源求解器主要有SCIP。这两类求解器相比，商用求解器求解效率优势明显，以制造业中的生产排程为例，在保证数据准确性的前提下，采用商用求解器计算的排产指标可缩短至分钟级。此外还有一些拥有强大计算能力的商业计算软件，比如Matlab等也都自带有求解器模块，可以求解部分数学规划问题，不过求解效率和商用求解器相比还是有一定差距。
那么面向不同的数学规划问题我们应该如何选择求解器？目前市面上又有哪些通用求解器可以选择呢？接下来我们对市面上常见的通用数学规划求解器进行一下梳理！
（下方表格可左右滑动查看）
PART1 商用求解器
求解器 所属机构 可求解的问题 优势特点
GUROBI 美国/Gurobi Optimization 多种类型 性能卓越，各项求解指标领先，全球用户范围广
CPLEX 美国/IBM 大规模线性规划、混合整数规划、二次规划和二次约束规划 包含数学规划求解器CPLEX Optimizer和约束规划求解器CP Optimizer
Xpress 美国/FICO 多种类型 包括通用非线性求解器 Xpress NonLinear，能快速准确解决复杂一般非线性问题
MOSEK 丹麦/MOSEK ApS 侧重二次规划、半定规划和二阶锥规划 公认的求解二次规划、二阶锥规划和半正定规划问题最快的求解器之一
BARON 美国/The Optimization Firm 非线性规划为主 能够将非凸优化问题求解到全局最优
Lingo 美国/LINDO 线性、非线性（凸和非凸/全局）、二次、二次约束、二阶锥、半定、随机和整数规划 内置建模语言，提供许多常用函数方便使用者建立优化模型时调用
杉数COPT 中国/杉数科技 线性规划、混合整数规划、二阶锥规划、半定规划、凸二次（约束）规划 综合性数学规划求解器，线性规划排名世界前列，已应用于多个国内项目，提供定制化服务
阿里云MindOPT 中国/阿里云 线性规划 线性单纯形法目前排第一，已应用于云计算等多项阿里业务
华为OPTV 中国/华为 线性规划、整数规划 融合前沿AI能力，可根据问题特征自适应进行参数调优和求解策略选取
PART2 开源求解器
求解器 所属机构 可求解的问题 优势特点
SCIP 德国/ZIB研究所 混合整数（非线性）规划 目前混合整数规划和混合整数非线性规划最快的非商业求解器之一
Coin-OR旗下开源求解器 开源社区/全球多个组织和个人 多种类型 COIN-OR维护着市面上几乎所有的开源优化求解器，包括CLP/CBC/CGL/SYMPHONY/ipopt/pyomo等数十种求解器和建模语言
LP_solve 开源社区/sourceforge 纯线性、（混合）整数/二进制、半连续和特殊有序集（SOS）模型 基于修正单纯形法和分支定界法的免费线性（整数）规划求解器
GLPK 俄罗斯/GNU 线性规划、混合整数规划 开源，使用方便，可求解一定规模的线性规划问题，支持直接调用，也能提供C、julia等编程语言的库或package
OR-Tools 美国/谷歌 线性规划、整数规划 集合了面向不同问题的优化工具套件，可免费使用且公开源代码，支持CPLEX、SCIP等第三方求解器
CMIP 中国/中科院 整数规划 采用一种广义系数缩紧割平面(GCSC)技术，对于一般整数规划问题具有一定改善效果，网络设计问题效果显著
Leaves优化求解器 中国/上海财大-杉数 线性规划 由上海财经大学的并行优化国际实验室与杉数科技共同牵头建设，主要聚焦于一些最新大规模一阶和二阶算法的探讨
PART3 其他软件集成
求解器 所属机构 可求解的问题 优势特点
MATLAB 美国/MathWorks 多种类型 MATLAB是一个包含大量数学函数库的应用程序，提供了多种面向不同问题的数学规划求解器，适用问题规模较小
SAS 美国/SAS Institute 多种类型 SAS是专业的统计分析软件，包含通用的线性规划、混合整数规划和非线性规划的求解模块
SCIPy 开源工具 多种类型 scipy是python科学计算生态栈中的顶级开源库，提供了大量的数值优化求解器，并且提供了统一的数值优化求解器接口
三、求解器是如何求解的
求解器通常集成了包含多种优化算法的算法框架，比如分支定界法(Branch and Bound Algorithm, B&B)、割平面法（Cutting Planes Method）以及其他启发式算法。在这其中，分支定界法是求解器精确算法框架中最重要的核心算法之一，也是最常用的优化算法，可以用来求解纯整数规划、混合整数规划等问题，以解决现实生产生活中的物流配送、路径规划、航班调度等问题。目前市面上主流的GUROBI、CPLEX等商用求解器都是以分支定界法+割平面法作为算法框架的。
下面我们以一个整数规划问题为例，介绍一下求解器中的分支定界法是如何求解的。
假如我们要求解这样一个问题：
那么采用分支定界法来求解这一问题的过程如下：
首先，我们选择进行分支，将整个问题变成两个子问题，如上图所示即当以及的时候对应的两个问题，然后通过线性松弛（在不考虑整数变量限制的情况下，通过线性规划求解器求解一个线性的松弛解）求得两个问题的上界分别是, ，因为两个分支的都大于负无穷，故这两个分支都可以继续往下进行。
然后，我们会发现当,的这个分支会导致问题的约束被打破，即不可行解，,的分支可以解到线性松弛解，即一个可行解，,的分支可以解到线性松弛解，该松弛解大于已知的最优，证明该分支有进一步提升的可能，,的分支可以解到线性松弛解比最优的要好一些，故目前的最优解为。
最后，我们对,进一步的分支，分支之后我们发现,,的分支为不可行解，,,分支对应的线性松弛解，综上所述，我们通过分支定界算法最终求得该问题的最优解为,,，最优解的值为10。
四、如何利用求解器解决现实决策问题
尽管不同求解器求解的问题和方法各有不同，但万变不离其宗，对于现实中的各种业务决策问题，我们都需要首先把业务问题建成数学规划模型，进而选择合适的求解器寻求最优解或者可行解，从而协助我们做出更理想的决策。通常的求解思路是：1、明确业务问题；2、定义优化问题三要素；3、建立数学规划模型；4、将该模型导入到求解器中去求解。
以一个常见的组合优化问题——旅行商问题（Traveling Salesman Problem,TSP）为例：
1. 明确业务问题：
“销售员需要访问个城市中的每一个，城市索引号记为，销售员从一个基准城市出发，索引号记为。旅行中访问其他城市1次，然后返回城市；旅行中必须返回城市 次，包括最后一次返回，并且在一次旅行中访问不超过个城市。一个成功的旅行意味着连续访问城市而不停留在城市，要求找到这样的行程使得总路程最小化。”
2. 定义优化问题三要素：
其中为非负整数，代表是从到这条路径是否存在，代表从到这条路径的距离，代表在一次旅行中城市是被第几个访问的，约束条件中表明每个城市只能被访问一次，并且一次旅行中访问不超过个城市。
3. 建立数学规划模型：
接下来我们需要正确建立优化问题的数学规划模型。上述旅行商问题可以建模成一个整数规划模型，如下所示：
# 定义变量
x = model.addMVar((data_num, data_num), lb=0, ub=1, vtype=GRB.BINARY)
u = model.addMVar((data_num), vtype=GRB.CONTINUOUS)
# 构造目标函数
objsum = []
for i in range(0, data_num):
for j in range(0, data_num):
objsum = objsum + x[i][j] * distance_juzheng[i][j]
model.setObjective(objsum, GRB.MINIMIZE)
# 构造约束条件
for i in range(0, data_num):
constrsum = sum(x[i, :])
model.addConstr(constrsum == 1)
for j in range(0, data_num):
constrsum1 = sum(x[:, j])
model.addConstr(constrsum1 == 1)
for i in range(1, data_num):
for j in range(1, data_num):
if (i != j):
model.addConstr((u[i] - u[j] + data_num * x[i][j]) <= data_num - 1)
model.optimize() # 求解模型
4. 将该模型导入到求解器中去求解：
此时求解器就可以对该问题进行求解，下图所示为GUROBI求解器给出的p=15个城市的求解结果。
五、求解器路在何方
精益化管理时代，内部的计划运营能力对企业来说尤为重要。如何盘活沉淀的数据资产，结合外部数据洞察分析，帮助企业做出科学的决策是企业一直在努力的课题，这使得企业对求解器的需求也日趋强烈。但与此同时更加规模化、复杂化的业务问题也给当下求解器的求解性能提出了更高的要求。
目前主流求解器中都存在大量的启发式算法，这些基于专家经验的启发式规则在大多数情况下只能找到局部最优的策略，此外，由于专家经验一般是从某些特定问题中总结的，导致其无法同时覆盖不同类型的问题。好在近年来不断发展的人工智能技术给求解器的性能优化提供了更多可能。
从当下的行业实践来看，国内已有少数企业开始尝试现有求解器中启发式规则的优化，比如联想将深度神经网络与求解器技术结合打造的自适应神经网络求解器，就能够根据问题类型和规模的不同自主学习并得到更优的求解策略，进而实现求解效率和质量的提升。科技永远向前，用更加前沿的科学技术不断推动求解器技术的发展，求解器才能更好地成为实现智能决策的终极“利器”。
沪公网安备31011302006932号