Gurobi 9.0 技术突破和新亮点 网络讲座 顾宗浩博士 2020 年 1 月 8 日
亮点汇总 性能提升 新切平面技术, 新的解改进启发式算法, 对 AVX-512 支持, 等等 主要新功能 非凸 MIQCP ( 双线性 ) 分段线性 (PWL) 约束 函数约束, 自动转换成分段线性约束 MIP 多方案分析 (what if, MIP 敏感度分析 ) 增加 Python 矩阵接口 ( 支持 SciPy 稀疏矩阵 ) 新运算服务器功能 运算服务器中的离线批量优化 其他改进 优化进程中的解文件输出 对于运算服务器架构的惰性约束回调支持 对于面向对象语言 API 接口中变量和约束的下标操作 模型属性文件 交互式界面由 Python 2.7 更新为 3.7 2 Copyright 2020, Gurobi Optimization, LLC
亮点汇总 性能提升 新切平面技术, 新的解改进启发式算法, 对 AVX-512 支持, 等等 主要新功能 非凸 MIQCP ( 双线性 ) 分段线性 (PWL) 约束 函数约束, 自动转换成分段线性约束 MIP 多方案分析 (what if, MIP 敏感度分析 ) 增加 Python 矩阵接口 ( 支持 SciPy 稀疏矩阵 ) 新运算服务器功能 运算服务器中的离线批量优化 其他改进 优化进程中的解文件输出 对于运算服务器架构的惰性约束回调支持 对于面向对象语言 API 接口中变量和约束的下标操作 模型属性文件 交互式界面由 Python 2.7 更新为 3.7 3 Copyright 2020, Gurobi Optimization, LLC
LP 性能 默认设置 : 提速 7% 4 线程并发 LP 单纯型 : 提速 5% ( 原始 ), 保持不变 ( 对偶 ) 线性系统求解的改进 (Ftran/Btran) 初始解和边角问题的数值改进 内点法 : 提速 7% 交叉 : 数值改进 支持 AVX-512, 对费时的因式分解模型提升 40% 在 AVX-512 电脑上产生整体额外 4% 性能提升 4 Copyright 2020, Gurobi Optimization, LLC
MIP 性能 MILP: 提速 18% ( 大于 100 秒模型提速 26%) 切平面 : new RLT cuts new BQP cuts new RelaxLift cuts second type of "SubMIP" cuts use LP to find another aggregation for MIR cut separator randomize aggregation order in MIR cut separator try more scaling factors in MIR cut separator more aggressive cover cut separation occasionally separate "close cuts" tuned cut loop abort criteria for main and parallel cut loops improved dual bound updates from parallel root cut loops improved cut selection improved performance of zero-half and mod-k cut separators limit effort in GUB cover and network cut separation procedures limit effort in some very expensive cut separation procedure fixed a performance issue in symmetry cuts 启发算法 : new solution improvement heuristic new "lurking bounds" heuristic extended some heuristics to work for models with SOS constraints 预优化 : implied product detection detect implicit piece-wise linear functions sparsify objective function substitute sub-expressions in presolve to sparsify constraints better work limits in constraint sparsification improved parallel column/row presolve reduction activate SOS2 to big-m translation in some cases 其他改进 : improved disconnected components extended disconnected components detection to work for models with SOS constraints reduced wait time in parallel synchronization by more flexible work load distribution propagate objective function in node probing 5 Copyright 2020, Gurobi Optimization, LLC
新的解改进启发式算法 启发式算法已经取得显著改善 仍然存在很多进一步改善的机会 特别当松弛解无法提供好的指导 更好的改进启发式 ImproveStartGap, ImproveStartNodes, ImproveStartTime 在困难模型集合中, 与旧版本对比 新的改进方案可以在 83% 的模型上找到更好结果 6 Copyright 2020, Gurobi Optimization, LLC
凸 MIQP 和 MIQCP 性能 MIQP: 提速 24% 大部分 MILP 改进方法同样适用 对于纯粹的 "box QPs 问题, 将非凸目标的变量转为 0-1 变量 MIQCP: 提速 6% 大部分 MILP 改进方法同样适用 对于二次约束, 改进预优化和节点预优化 扩充 MILP 启发式算法到 MIQCP 等等 7 Copyright 2020, Gurobi Optimization, LLC
主要新功能 8 Copyright 2020, Gurobi Optimization, LLC
亮点汇总 性能提升 新切平面技术, 新的解改进启发式算法, 对 AVX-512 支持, 等等 主要新功能 非凸 MIQCP ( 双线性 ) 分段线性 (PWL) 约束 函数约束, 自动转换成分段线性约束 MIP 多方案分析 (what if, MIP 敏感度分析 ) 增加 Python 矩阵接口 ( 支持 SciPy 稀疏矩阵 ) 新运算服务器功能 运算服务器中的离线批量优化 其他改进 优化进程中的解文件输出 对于运算服务器架构的惰性约束回调支持 对于面向对象语言 API 接口中变量和约束的下标操作 模型属性文件 交互式界面由 Python 2.7 更新为 3.7 非线性优化 9 Copyright 2020, Gurobi Optimization, LLC
非凸 QP, QCP, MIQP 和 MIQCP 很多应用 混罐问题 ( 混合问题是 LP, 混罐问题引入了中间罐 双线性 ) 石油化工行业 ( 炼油 : 罐中成分比例的约束 ) 废水处理 排放合规 农业和食品行业 ( 基于预混装产品的混合加工 ) 等等 10 Copyright 2020, Gurobi Optimization, LLC
非凸 QP, QCP, MIQP 和 MIQCP 以往 Gurobi 版本 : 预优化之后的约束和目标 Q 矩阵需要是凸的 x # Qx b convex y + x + 0 如果 Q 是半正定 (PSD) 的, 那么 x # Qx b 是凸的 Q is PSD if and only if x # Qx 0 for all x 但 x # Qx b 在其他情况下也可以是凸的, 例如二次锥 (SOCs) SOC: x. + + + x 0 + z + 0 non-convex y x + 0 x + + y + z + 0, z 0: at level z, x, y is a disc with radius z 11 Copyright 2020, Gurobi Optimization, LLC
非凸 QP, QCP, MIQP 和 MIQCP 对于非凸的二次约束和目标如何? 预优化也许可以使之凸化或者线性化 如果不成功的话 GRB_ERROR_Q_NOT_PSD or GRB_ERROR_QCP_EQUALITY_CONSTRAINT Gurobi 9.0 可以求解任何二次问题到全局最优 不再返回错误, 直接求解 ( 如果 NonConvex 参数设定为 2) 自动将任意非凸二次约束转为双线性约束 3x. + 7x. x + + 2x. x 4 x + + + 3x + x 4 5x 4 + = 12 ( 非凸 Q 约束 ) p.. x +., p.+ x. x +, p.4 x. x 4, p ++ x + + +, p +4 x + x 4, p 44 x 4 (6 双线性约束 ) 3p.. 7p.+ + 2p.4 p ++ + 3p +4 5p 44 = 12 ( 线性约束 ) 优化器可以处理双线性约束 切平面 空间分支 12 Copyright 2020, Gurobi Optimization, LLC
非凸 QP, QCP, MIQP 和 MIQCP 双线性约束的算法处理方法 广义形式 : a # z + dxy b ( 线性加单一乘积项, 不等式或等式 ) 例如平方形式 (x = y): convex z + x + 0 non-convex z x + 0 13 Copyright 2020, Gurobi Optimization, LLC
非凸 QP, QCP, MIQP 和 MIQCP 双线性约束的算法处理方法 广义形式 : a # z + dxy b ( 线性加单一乘积项, 不等式或等式 ) 例如平方形式 (x = y): convex z + x + 0 non-convex z x + 0 简单 : 加切线割平面 14 Copyright 2020, Gurobi Optimization, LLC
非凸 QP, QCP, MIQP 和 MIQCP 双线性约束的算法处理方法 广义形式 : a # z + dxy b ( 线性加单一乘积项, 不等式或等式 ) 例如平方形式 (x = y): non-convex z x + 0 15 Copyright 2020, Gurobi Optimization, LLC
非凸 QP, QCP, MIQP 和 MIQCP 双线性约束的算法处理方法 广义形式 : a # z + dxy b ( 线性加单一乘积项, 不等式或等式 ) 例如平方形式 (x = y): non-convex z x + 0 16 Copyright 2020, Gurobi Optimization, LLC
非凸 QP, QCP, MIQP 和 MIQCP 双线性约束的算法处理方法 广义形式 : a # z + dxy b ( 线性加单一乘积项, 不等式或等式 ) 例如平方形式 (x = y): non-convex z x + 0 分支 x 0 or x 0 局部更新松弛解 17 Copyright 2020, Gurobi Optimization, LLC
非凸 QP, QCP, MIQP 和 MIQCP 混合乘积形式 : z + xy = 0 McCormick 下界和上界包络 : pictures from Costa and Liberti: "Relaxations of multilinear convex envelopes: dual is better than primal" z + l > y + l? x l > l? z + u > y + u? x u > u? z + u > y + l? x u > l? z + l > y + u? x l > u? 18 Copyright 2020, Gurobi Optimization, LLC
非凸 QP, QCP, MIQP 和 MIQCP 混合乘积形式 : z + xy = 0 McCormick 下界和上界包络 : pictures from Costa and Liberti: "Relaxations of multilinear convex envelopes: dual is better than primal" z + l > y + l? x l > l? z + u > y + u? x u > u? z + u > y + l? x u > l? z + l > y + u? x l > u? 19 系数取决于局部界 Copyright 2020, Gurobi Optimization, LLC
非凸 QP, QCP, MIQP 和 MIQCP 算法构成 预优化将非凸 Q 约束转换为双线性约束 McCormick 松弛 空间分支 ( 对连续变量进行分支 ) 自适应约束 " 在局部界变化后自动更新 McCormick 松弛问题的系数 而非增加局部切平面 切平面 RLT 切平面 (RLT = Reformulation Linearization Technique) BQP 切平面 (BQP = Boolean Quadric Polytope) 即将推出 : SDP 切平面 (SDP = Semi-Definite Program)... 同样适用 MILP 识别含 0-1 变量乘积线性化的结构 性能提升 : RLT 切平面和 BQP 切平面 20 Copyright 2020, Gurobi Optimization, LLC
非凸 QP, QCP, MIQP 和 MIQCP 初步测试结果 vs. 市面上非凸 MIQCP 优化器 QPLIB 测试集合 Prof. Hans Mittelmann (Arizona State Univ.) http://plato.asu.edu/bench.html Gurobi 速度更快, 在时间限定内求解问题数量更多 但 : 其他优化器通常目的是求解广义 MINLP, 并非仅仅非凸 MIQCP Test set Mosek Knitro Bonmin CBC Couenne OcterAct Baron SCIP F-SCIP Antigone Minotaur Gurobi non-convex binary non-convex discrete non-convex continuous convex discrete ratio 64.7x 16.2x 64.8x 46.7x 63.0x 85.8x 1.0x solved (80) 17 41 19 24 23 7 80 ratio 25.5x 30.6x 11.9x 18.3x 5.1x 12.6x 28.8x 1.0x solved (88) 8 1 24 15 41 29 4 66 ratio 5.1x 4.9x 2.2x 4.2x 2.7x 1.6x 5.4x 1.0x solved (49) 8 8 22 7 14 29 6 27 ratio 7.0x 11.4x 10.8x 31.1x 7.3x 13.5x 20.3x 28.6x 17.9x 1.0x solved (31) 12 9 10 2 11 11 8 2 11 21 results from December 16, 2019 21 Copyright 2020, Gurobi Optimization, LLC
亮点汇总 性能提升 新切平面技术, 新的解改进启发式算法, 对 AVX-512 支持, 等等 主要新功能 非凸 MIQCP ( 双线性 ) 分段线性 (PWL) 约束 函数约束, 自动转换成分段线性约束 MIP 多方案分析 (what if, MIP 敏感度分析 ) 增加 Python 矩阵接口 ( 支持 SciPy 稀疏矩阵 ) 新运算服务器功能 运算服务器中的离线批量优化 其他改进 优化进程中的解文件输出 对于运算服务器架构的惰性约束回调支持 对于面向对象语言 API 接口中变量和约束的下标操作 模型属性文件 交互式界面由 Python 2.7 更新为 3.7 非线性优化 22 Copyright 2020, Gurobi Optimization, LLC
分段线性 (PWL) 约束 一种新的广义约束 用户将关键折点用一系列 (x,y) 元组表示 may have jump supporting points extended towards infinity with same slope y = PWL x; x., y.,, x 0, y 0 23 Copyright 2020, Gurobi Optimization, LLC
分段线性 (PWL) 约束 一种新的广义约束 用户将关键折点用一系列 (x,y) 元组表示 举例 y = e >, 0 x 1 用 100 个分段近似, 产生 101 个点 (xpts, ypts): Python 代码 : 0, e G, 0.01, e G.G.,, 1, e. n = 100 xpts = [1.0*k/n for k in range(n+1)] ypts = [math.exp(xpts[k]) for k in range(n+1)] model = Model("pwltest") x = model.addvar(lb=0, ub=1, name="x") y = model.addvar(name="y") gc = model.addgenconstrpwl(x, y, xpts, ypts, "gc") model.setobjective(-2*x + y) model.optimize() 24 Copyright 2020, Gurobi Optimization, LLC
分段线性 (PWL) 约束 (0.69, 1.9937) min -2x+y Optimize a model with 0 rows, 2 columns and 0 nonzeros Model fingerprint: 0xe289cdc2 Model has 1 general constraint Variable types: 2 continuous, 0 integer (0 binary)... Nodes Current Node Objective Bounds Work Expl Unexpl Obj Depth IntInf Incumbent BestBd Gap It/Node Time 0 0 cutoff 0 0.61372 0.61372 0.00% - 0s... Optimal solution found (tolerance 1.00e-04) Violations: const 0.0000e+00, bound 0.0000e+00, int 0.0000e+00, genconstr 0.0000e+00 Best objective 6.137155332431e-01, best bound 6.137155332431e-01, gap 0.0000% gurobi> print x.x 0.69 gurobi> print y.x 1.99371553324 25 Copyright 2020, Gurobi Optimization, LLC
函数约束, 自动转换成分段线性约束 y = f(x) 支持 : polynomial, log x, log U (x), e >, a >, x U, sin(x), cos x, tan(x) 另外一种新的广义约束形式 举例 y = e >, 0 x 1 Python 代码 : gc = model.addgenconstrexp(x, y, name= gc ) Gurobi 自动计算转折点和进行分段线性化转换 对于周期函数有更聪明的处理 sin(), cos(), and tan() 在预处理中采用原始函数形式 在预优化中的界压缩可能产生更有效的分段线性化转换 26 Copyright 2020, Gurobi Optimization, LLC
自动分段线性化转换的选项 选项 FuncPieces, FuncPieceLength, FuncPieceError, FuncPieceRatio 属性 : 只适用于某个函数约束 参数 : 适用于全部函数约束 速度和精度的取舍 FuncPieces, FuncPieceLength, FuncPieceError 用于设置分段 长度, 分段数量和最大允许误差 向下近似和向上近似 FuncPieceRatio 举例, y = x + 向下近似 : (P l1, P l2, P l3 ) 向上近似 : (P u1, P u2, P u3 ) 误差 : 0.25 for both pieces [0,1] and [1,2] 27 Copyright 2020, Gurobi Optimization, LLC
非线性能力 理论上 多变量多项式可以分解为双线性函数 z = x Y y + Let u = x +, v = u +, w = y + (bilinear) Then z = vw (bilinear) PWL 约束允许近似单变量非线性函数 可以将广泛的非线性问题获得全局最优 e.g., z = sin x + y ` e >a?b 现实中 误差随着分解和合并在不断放大 PWL 近似的误差可能较大 举例 : y = x 0.25, y = x + y = x 0.25 is for line (P l1, P, P l2 ) P = (x, y) = (0.5, 0.25) is feasible PWL approximation of y = x + with line segments (P u1, P u2, P u3 ) y = 0.5 at x = 0.5, Q(0.5, 0.5) is quite far from P(0.5, 0.25) Infeasible FuncPieceLength=1 is too big: largest error = 0.25 is too big to be feasible 28 Copyright 2020, Gurobi Optimization, LLC
亮点汇总 性能提升 新切平面技术, 新的解改进启发式算法, 对 AVX-512 支持, 等等 主要新功能 非凸 MIQCP ( 双线性 ) 分段线性 (PWL) 约束 函数约束, 自动转换成分段线性约束 MIP 多方案分析 (what if, MIP 敏感度分析 ) 增加 Python 矩阵接口 ( 支持 SciPy 稀疏矩阵 ) 新运算服务器功能 运算服务器中的离线批量优化 其他改进 优化进程中的解文件输出 对于运算服务器架构的惰性约束回调支持 对于面向对象语言 API 接口中变量和约束的下标操作 模型属性文件 交互式界面由 Python 2.7 更新为 3.7 处理不确定性 29 Copyright 2020, Gurobi Optimization, LLC
MIP 多方案分析 背景 数学模型通常是真实世界应用的近似 输入通常是预估的, 例如销售预测 商业环境和条件也是变化的 了解优化方案对于变化的敏感度是非常重要的 如果某种商品的需求从 10 个增加到 12 个会怎样? 错误的做法 固定整数变量, 按照连续模型来求解, 获得固定后的连续模型的对偶值和递减成本 这将导致错误结果! 从数学计算角度也不合理! 我们的做法 建立基准模型 用属性创建一组方案 每个方案定义为对于基准模型的变化 变化包括 : 目标系数, 变量上下界, 线性约束的右边项 然后计算所有方案的最优解 这样可以提供不同方案中结果是如何变化的洞察力 30 Copyright 2020, Gurobi Optimization, LLC
MIP 多方案分析 简单做法 将每个方案作为独立 MIP 求解 旧版本案例 : sensitivity.py Gurobi 9.0 的新做法 方便定义各种方案 通过属性 参考案例 sensitivity.py, 已经被重新改写 性能 更快 未来版本会在运算服务器中加入分布式计算 即便提早中断, 很多信息, 例如优化界, 每种方案的可行解等仍然可以获得 31 Copyright 2020, Gurobi Optimization, LLC
处理不确定性 MIP 多方案分析 为每个方案找到最优解 某个方案的解未必对其他方案可行 帮助分析商业模型 : 对于输入的变化, 最优解的敏感度如何? MIP 版本的 LP 敏感度分析 随机优化 Stochastic Optimization 寻找一个解, 优化所有方案的期望值 用户需要设定每个方案的概率 或者为随机变量指定分布函数 鲁棒优化 Robust Optimization 寻找一个解, 优化最差方案 模型系数不固定, 用户需要指定范围 更广泛 : 系数在指定的凸集中 32 Copyright 2020, Gurobi Optimization, LLC
亮点汇总 性能提升 新切平面技术, 新的解改进启发式算法, 对 AVX-512 支持, 等等 主要新功能 非凸 MIQCP ( 双线性 ) 分段线性 (PWL) 约束 函数约束, 自动转换成分段线性约束 MIP 多方案分析 (what if, MIP 敏感度分析 ) 增加 Python 矩阵接口 ( 支持 SciPy 稀疏矩阵 ) 新运算服务器功能 运算服务器中的离线批量优化 其他改进 优化进程中的解文件输出 对于运算服务器架构的惰性约束回调支持 对于面向对象语言 API 接口中变量和约束的下标操作 模型属性文件 交互式界面由 Python 2.7 更新为 3.7 数据科学家, 工程师 33 Copyright 2020, Gurobi Optimization, LLC
Python 矩阵接口 关于 Python 很流行的编程语言 海量库 标准库 第三方库, 容易管理 数据科学研究的顶尖语言 数据科学家和工程师习惯和矩阵打交道 大量人员使用 NumPy 和 SciPy gurobipy 接受 NumPy s ndarrays 和 scipy.sparse matrices 作为输入 如果模型本来就用矩阵表达, 则更方便 因为不用创建表达式的模型对象, 则更快速 API 提供了二种方式 ( 这里仅显示线性的 ): 直接添加矩阵约束 Model.addMConstrs(A, x, sense, b) 采用矩阵变量 x = Model.addMVar(shape), 然后添加约束 Model.addConstr(A @ x <= b) 34 Copyright 2020, Gurobi Optimization, LLC
Python 矩阵 API : 一个简单案例 mip1.py: 代数语法 import gurobipy as gp from gurobipy import GRB m = gp.model("mip1") x = m.addvar(vtype=grb.binary, name="x") y = m.addvar(vtype=grb.binary, name="y") z = m.addvar(vtype=grb.binary, name="z") m.setobjective(x + y + 2 * z, GRB.MAXIMIZE) m.addconstr(x + 2 * y + 3 * z <= 4, "c0") m.addconstr(x + y >= 1, "c1") m.optimize() matrix1.py: 矩阵表达 import numpy as np import scipy.sparse as sp import gurobipy as gp from gurobipy import GRB m = gp.model("matrix1") x = m.addmvar(shape=3, vtype=grb.binary, name="x") obj = np.array([1.0, 1.0, 2.0]) m.setobjective(obj @ x, GRB.MAXIMIZE) data = np.array([1.0, 2.0, 3.0, -1.0, -1.0]) row = np.array([0, 0, 0, 1, 1]) col = np.array([0, 1, 2, 0, 1]) A = sp.csr_matrix((data, (row, col)), shape=(2, 3)) rhs = np.array([4.0, -1.0]) m.addconstr(a @ x <= rhs, name="c") m.optimize() 35 Copyright 2020, Gurobi Optimization, LLC
亮点汇总 性能提升 新切平面技术, 新的解改进启发式算法, 对 AVX-512 支持, 等等 主要新功能 非凸 MIQCP ( 双线性 ) 分段线性 (PWL) 约束 函数约束, 自动转换成分段线性约束 MIP 多方案分析 (what if, MIP 敏感度分析 ) 增加 Python 矩阵接口 ( 支持 SciPy 稀疏矩阵 ) 新运算服务器功能 运算服务器中的离线批量优化 其他改进 优化进程中的解文件输出 对于运算服务器架构的惰性约束回调支持 对于面向对象语言 API 接口中变量和约束的下标操作 模型属性文件 交互式界面由 Python 2.7 更新为 3.7 公司 IT, 私有云, 离线优化 36 Copyright 2020, Gurobi Optimization, LLC
集群管理 管理 Gurobi 运算服务器集群 IT 部门可以控制和跟踪集群规模和负载 用户可以监控和管理优化任务 用户管理 允许为用户设定不同角色 (user, admin, cluster admin) 更高安全性和 API 密钥 本地网 页界面管理 为管理员和用户提供了用户友好的图形化管理界面 任务日志 为优化任务提供统计和日志管理 支持离线批量优化模式 为耗时 长的优化任务提供离线优化 客户端不必一直在线, 可以后期再连线获取结果 37 Copyright 2020, Gurobi Optimization, LLC
集群管理 网页界面 38 Copyright 2020, Gurobi Optimization, LLC
在集群管理中进行批量优化 背景 运算服务器允许客户端将优化任务发送到服务器上运行 MIP 问题经常会需要较 长优化时间 要求客户端一直在线等待, 往往会造成不便 用户需求 允许客户端中断和服务器的连接 后续, 客户端可以重新连接, 获得优化结果 技术问题 重连服务器会产生映射问题 客户端的变量和约束对象已经消失了 我们的解决方案 模型在客户端本地上创建 对于感兴趣的变量和约束设置标签 发送模型到运算服务器, 获得批处理 ID 并中断连接 后续通过任务 ID 查询优化状态, 并以 JSON 格式获得优化结果 39 Copyright 2020, Gurobi Optimization, LLC
亮点汇总 性能提升 新切平面技术, 新的解改进启发式算法, 对 AVX-512 支持, 等等 主要新功能 非凸 MIQCP ( 双线性 ) 分段线性 (PWL) 约束 函数约束, 自动转换成分段线性约束 MIP 多方案分析 (what if, MIP 敏感度分析 ) 增加 Python 矩阵接口 ( 支持 SciPy 稀疏矩阵 ) 新运算服务器功能 运算服务器中的离线批量优化 其他改进 优化进程中的解文件输出 对于运算服务器架构的惰性约束回调支持 对于面向对象语言 API 接口中变量和约束的下标操作 模型属性文件 交互式界面由 Python 2.7 更新为 3.7 40 Copyright 2020, Gurobi Optimization, LLC
接下来 欢迎试用 Gurobi 9.0, 中国地区联系 help@gurobi.cn 申请 30 天商业试用许可 申请免费学术许可 关于 Gurobi 商务信息, 中国地区联系 help@gurobi.cn 一二周之后, 本讲座的录像和 PPT 将会在网站上发布 接下来更多技术细节的网络讲座 1 月 14 和 15 日 : 非凸 MIQCP 2 月份 : 运算服务器和集群管理 关注通知 www.gurobi.com/events 41 Copyright 2020, Gurobi Optimization, LLC