Gurobi 10.0 新亮点

Gurobi 10.0性能提升汇总

LP 性能

 新增⽹络单纯形算法 New network simplex algorithm

• LP 并发算法改进: 仅对预优化之后的最终模型进⾏并⾏计算

• Crossover 改进

• 并⾏原始单纯形外推 Parallel primal pushes

• 外推前内点法解调整 Barrier solution adjustment before pushes

• 新增和改进模型精简算法，提供更多选项

• 把⼀些 MIP精简算法应⽤到 LP, 例如 PreSparsify

• 处理对偶和基的反压缩 Handle dual and basis uncrush

• Aggregate 合并参数新增数值 2

⽹络单纯形算法 (Network Simplex Algorithm)

• 针对问题

• 最⼩成本流 Minimum cost flow

• 可以建模为常规 LP 模型，⽤常规LP 求解器

• 开发动⼒

• 众所周知: 经常在 OR, CS 和 Math 课程上讲到

• 研究较多: 许多不同算法

• 连续最短路径算法 Successive shortest path algorithm

• 缩放算法，多项式运⾏时间 Scaling algorithms, polynomial

• Cost scaling, capacity scaling, double scaling, etc.

• ⽹络单纯形算法 Network simplex algorithms

• Primal and dual network simplex

• Reference: Network Flows, R. Ahuja, T. Magnanti and J. Orlin

• Gurobi ⽹络单纯形算法

• 只实现原始单纯形

• 最主要的挑战部分

• ⽣成树(spanning tree, i.e., basis)的数据结构

• 维护/更新⽣成树

• 原始单纯形⽹络算法相比常规 LP 原始单纯形算法优势在于

• 可以利⽤特殊结构加快速度: ⼤概在五倍速

• 强可⾏⽣成树: 保证没有循环(cycling)

• 较容易构造特殊算法，产⽣较好的初始⽣成树(basis crash)等

• 在我们⽹络数据集的性能

• Vs. ⼴义原始单纯形: 36X, ⼤约减少 50% 迭代

• Vs. ⼴义对偶单纯形: 3.9X, ⼤约增加10X 迭代

• 对偶⽹络单纯形

• 还未开发: 类似的挑战，也许更难⼀些

• 还不清楚简单好⽤的⽅法来保证没有循环

• 预期比原始⽹络单纯形算法要快

并发LP算法(Concurrent LP Algorithms)

 Gurobi LP 算法求解过程 (单纯形和内点法)

• 决定求解原始还是对偶形式

• 结论经常对于单纯形法或内点法⽽不同

• 应⽤ LP 精简算法产⽣预优化模型

• 对于原始和对偶单纯形相同，对于内点法稍有不同

• 折叠(Fold)预优化模型，如果存在弱对称性

• 再次应⽤ LP 精简算法产⽣更⼩的预优化模型

• ⽤单纯形或者内点法求解最终的预优化模型

• 反压缩(Uncrush) 折叠的预优化模型，应⽤单纯形法在折叠的模型上

• 反折叠(Unfold) 并采⽤交叉转换(Crossover) 得到基解

• 反压缩(Uncrush) 并采⽤单纯形法在初始模型上直到结束

• 开发动⼒

• 计算机核数持续增加

• 越来越多⽤户使⽤并发LP求解器

• 并发LP 求解器通常使⽤更多的内存；⼀些⽤户建议设置软性内存限制参数，以便限制内

点法内存占⽤

V9.5 及以前版本的并发LP算法

• 每个并发任务都会保留⼀个模型拷⻉

• 通常占⽤很⼤内存

• 每个任务，不论原始单纯形，对偶单纯形还是内点法独立运算所有步骤

• 每个步骤都由并发任务各⾃独立并发完成

• 并发运⾏的任务可能会让计算速度显著降低

• 取决于机器和模型规模，速度可能会降低 30% - 60% 

• 新并发LP算法

• 只在最终预优化模型上应⽤并发算法

• 其他步骤顺序执⾏

• 挑战在于

• 决定求解形式是原始形式还是对偶形式

• 管理单纯形和内点法的预优化差异

• 对于规模较⼤模型的提速经常远超 10%

• 如今使⽤更少的内存

• 取决于预优化模型规模，⽽不是初始模型规模。

MIP 性能

各种增强分⽀(Strong branching)⽅法的改进

• 多种对称性改进

• 深度搜索时(diving), 关闭非有效切平⾯以便更好求解松弛问题

• 求解⼦MIP问题时, ⽤⼒度更⼤的设置

• 新预优化简化算法和改进

• 对于松弛问题的并发LP算法改进和调优

• ⼒度更⼤地融和聚类(cliques) 和VUB

• 基于优化的边界紧缩算法 Optimization-based bound tightening (OBBT)

• 对 MIQP/MIQCP/MINLP 有帮助，后续还会介绍

• 对于机器学习模型的多种改进

• 将在后续开源 Github 应⽤库中介绍。

增强分⽀⽅法的改进

 增强分⽀(Strong branching)

• 选择取分数值的0-1变量/整数变量的集合

• 对于每个变量，执⾏向上和向下分⽀的⼀定数量的对偶迭代

• 利⽤⽬标值在⼆个分⽀上的变化来选择分⽀变量

• 尝试各种⽅法

• 增强分⽀通常代价较⾼，需要事半功倍

• 具有前瞻性, 定义终⽌数值

• 利⽤对称性节省步骤

• 利⽤从向上和向下分⽀获得的引导

• 传播引申的边界值

• 传播聚类(cliques)

• 传播 SOS 约束

• 应⽤增强分⽀的频率

• 各种其他考虑

MIQP/MIQCP 性能

新 QUBO 启发算法

• 远景强化 Perspective strengthening

• 把⽬标中的Q 项移到约束中

• 对于 QC 固定启发算法的⼯作限度(work limit)调整

• 加强⼆次约束中0-1变量的系数

• 在启发算法中以⼀定次序固定0-1变量

• 求解集覆盖问题来选择线性化⽅式

• 移除共同变量

• 基于优化的边界紧缩算法 OBBT

• 其他 MIP 改进同样适⽤

新 QUBO 启发算法

• ⼆种类型的启发算法

• 构造: 发现新的可⾏解

• 改进: 提升已有可⾏解

• 9.5 版本中的QUBO 算法

• 禁忌搜索(Tabu search) – 改进算法

• 从⼀个随机起点出发

• 局部改进对于 QUBO 相对容易

• 没有约束

• 10.0版本中的新 QUBO 算法

• Rank-2 松弛启发算法 – 构造算法

• Burer, Monteiro, and Zhang, Rank-Two Relaxation Heuristics for MAX-Cut and Other Binary 

Quadratic Programs

• ⾏和列映射到圆上的点

• 考虑所有可能切分圆的弦。

我们计算结果显⽰

• 对于 QUBO 问题可以快速找到好的解

• 并且可以显著缩短优化的时间，对于启发算法来说很少⻅

非凸 MIQCP 性能

• 基于优化的边界紧缩算法 OBBT

• 在乘积项覆盖中显性处理⼆分图 (Dealing explicitly with bipartite graphs in the 

product term covering) 

• NLP 启发算法终⽌条件的改进

• NLP 启发算法的多次启动

• 其他 MIP 和 凸 MIQCP 改进同样适⽤

基于优化的边界紧缩算法

Optimization Based Bound Tightening

• 对于 MINLP 求解器的通常技术

• 给定⼀个（非凸）MINLP 的LP松弛模型

• 对于任何⼀个变量 

• 最⼩化/最⼤化  松弛数值

• ⽤最优值当作  的下界/上界

• ⽤新的上下界紧缩松弛系数

• OBBT 改进 (Gleixner et al. 2017)

• 筛选变量

• 利⽤热启动

• 利⽤ OBBT LP的对偶解紧缩分⽀树的边界

对于 MINLP 求解器的通常技术

• 给定⼀个（非凸）MINLP 的LP松弛模型

• 对于任何⼀个变量 

• 最⼩化/最⼤化 松弛数值

• ⽤最优值当作  的下界/上界

• ⽤新的上下界紧缩松弛系数

• OBBT 改进 (Gleixner et al. 2017)

• 筛选变量

• 利⽤热启动

• 利⽤ OBBT LP的对偶解紧缩分⽀树的边界

对于 MINLP 求解器的通常技术

• 给定⼀个（非凸）MINLP 的LP松弛模型

• 对于任何⼀个变量 

• 最⼩化/最⼤化 松弛数值

• ⽤最优值当作 的下界/上界

• ⽤新的上下界紧缩松弛系数

• OBBT 改进 (Gleixner et al. 2017)

• 筛选变量

• 利⽤热启动

• 利⽤ OBBT LP的对偶解紧缩分⽀树的边界

上一条：understand工具

下一条：Gurobi 10.0 优化引擎