如何选择合适的运筹优化求解器?

2023-12-08 18:44

本文主要是介绍如何选择合适的运筹优化求解器?,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 前言
  • 求解器对比
    • 问题延伸:商用求解器和开源求解器的差别是什么?
  • 求解器PK
  • 总结
  • 参考资料

前言

求解器对于运筹算法工程师而言,常常像一个黑盒,我们扔进去输入数据和数学模型,求解器给我们吐出一个解出来。这种状态在面临规模小、形式简单的数学模型是还可以应付的,但一旦问题难度上来,原本用着舒服的求解器可能求解你的问题太慢了,又或者根本无法给到符合预期的解,这时就会面临到底选择哪个求解器更合适的问题?
在这里插入图片描述

这里的合适代表既准又快,需要综合考虑:

  1. 自己的问题类型是什么?线性规划?整数规划?二次规划?这里可以参考我的文章运筹学算法分类快速判断;
  2. 不同求解器适用的问题类型;
  3. 开源还是商用?

2和3都会在接下来的梳理中体现。

求解器对比

求解器 国家 类型 支持的数学问题 优点 缺点 Python API
Gurobi美国商用 擅长:LP、MIP、凸和非凸的二次混合整数规划;
支持:(1) 线性约束和目标模型(连续变量、混合整数);(2)二阶锥模型(连续变量、混合整数);(3)二次凸约束和目标模型(连续变量、混合整数);(4)二次非凸(双线性、二次等式约束)约束和目标模型(连续变量、混合整数);(5)非线性模型(除式、高阶多项式、指数、对数、三角函数、范数等)(连续变量、混合整数)
可以叠加许多功能:(1)约束和目标中带有最大、最小、绝对值等数学函数,或者带有AND、OR、INDICATOR逻辑条件的模型;(2)多目标优化;(3)需要获得部分或者全部可行解或者最优解的模型;(4)不可行或者无解分析;(5)优化参数自动调优功能;(6)分布式计算或者多线程计算支持
Cplex美国商用LP、QP、QCQP、二阶锥规划(SOCP)、MIP支持
Xpress美国商用LP、MILP、QP、QCQP、SOCP、NLP、CP支持
COPT中国商用LP、MIP、二阶锥规划、半定规划、凸二次(约束)规划支持
SCIP德国开源MIP、MINLP、非凸优化问题用于MIP的最快的非商业求解器之一、支持Branch&Price、支持 McCormick relaxation 和 convex envelope relaxation 这两种非凸问题处理方法支持
OR-TOOLs美国开源LP、IP、约束规划、MIP跨平台性不支持非线性规划支持
IPOPT美国开源非线性规划问题(凸和非凸均可)对初始值敏感(影响算法收敛和迭代次数)、对于非凸问题可能陷入局部最优支持
GLPK美国开源大规模线性规划、MIP不支持非线性规划支持
CBC美国开源LP、MIP不支持非线性问题支持

梳理的过程中发现了一个wikipedia提供的表格:
在这里插入图片描述

问题延伸:商用求解器和开源求解器的差别是什么?

不同求解器底层的差异是它们是否能够正确的识别并利用模型的结构,而这直接决定了求解器的表现(求解速度、支持准确求解的问题类型、支持的问题规模、解的质量)。有些问题开源求解器无法支持,只有一些商业求解器才能求解,还有的问题,商业求解器的求解速度更佳。
在这里插入图片描述

导致这一差距的原因也很好理解——“Commercial vendors with their teams of full-time developers and their large customer base who provide models from a diverse set of applications are just in a much better position to develop, implement, and tune algorithms to cover all these different aspects and structures that appear in real-world models.”

求解器PK

目前主要是参考 H. Mittelmann 教授的评测网站,会从很多维度对各个求解器进行测试,最终从解决的问题数和耗时两个方面评分。
比如对于MIP问题,最新的测评结果是:

在这里插入图片描述

在这里插入图片描述

总结

回到我们文章标题的问题,拿到实际问题后怎么选择合适的求解器呢,我总结了3个步骤:
(1)判断数学问题类型,看看手头已有的求解器是否就能支持(判断方法可以查阅上面的表格);
啰嗦一句:排除不支持你这类问题的求解器,为什么单独强调这么一句呢?举个例子,你建模的问题是个整数规划问题,而IPOPT主要是用于求解非线性规划的,就不太适用于你这个问题。那问题来了,我就是把这个整数规划问题丢给IPOPT求解会怎么样呢?我亲自踩过这样的坑Pyomo调用IPOPT:0-1变量给出小数解,血泪教训!

(2)快速实验,找一个支持的求解器在小规模case上测试下;
如果你的问题规模本身就很小,而且在这一步的求解质量和速度都已经满足要求了,那么恭喜你,不用再继续往下看了!多测试一些case保证模型的鲁棒性即可。如果你不幸的发现,小规模测试OK,但测试案例规模放大,模型求解很久仍然没有给到解,无法支持上线实时计算的规模和时间要求(和现在的我一样),那么就进入下一步的打怪中。

(3)优化大规模问题的求解速度
这里持续更新中,我还在调研…

参考资料

  1. Evaluating Operational Research Solvers
  2. 整数规划求解器介绍
  3. The advantages of commercial solvers
  4. What does CPLEX solve ?
  5. Python运筹学求解器
  6. 市面上的数学规划求解器有哪些?
  7. COIN-OR
  8. H. Mittelmann 教授的评测网站
  9. Visualizations of Mittelmann benchmarks

这篇关于如何选择合适的运筹优化求解器?的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/470951

相关文章

MySQL索引的优化之LIKE模糊查询功能实现

《MySQL索引的优化之LIKE模糊查询功能实现》:本文主要介绍MySQL索引的优化之LIKE模糊查询功能实现,本文通过示例代码给大家介绍的非常详细,感兴趣的朋友一起看看吧... 目录一、前缀匹配优化二、后缀匹配优化三、中间匹配优化四、覆盖索引优化五、减少查询范围六、避免通配符开头七、使用外部搜索引擎八、分

Python通过模块化开发优化代码的技巧分享

《Python通过模块化开发优化代码的技巧分享》模块化开发就是把代码拆成一个个“零件”,该封装封装,该拆分拆分,下面小编就来和大家简单聊聊python如何用模块化开发进行代码优化吧... 目录什么是模块化开发如何拆分代码改进版:拆分成模块让模块更强大:使用 __init__.py你一定会遇到的问题模www.

SpringBoot首笔交易慢问题排查与优化方案

《SpringBoot首笔交易慢问题排查与优化方案》在我们的微服务项目中,遇到这样的问题:应用启动后,第一笔交易响应耗时高达4、5秒,而后续请求均能在毫秒级完成,这不仅触发监控告警,也极大影响了用户体... 目录问题背景排查步骤1. 日志分析2. 性能工具定位优化方案:提前预热各种资源1. Flowable

SpringBoot3实现Gzip压缩优化的技术指南

《SpringBoot3实现Gzip压缩优化的技术指南》随着Web应用的用户量和数据量增加,网络带宽和页面加载速度逐渐成为瓶颈,为了减少数据传输量,提高用户体验,我们可以使用Gzip压缩HTTP响应,... 目录1、简述2、配置2.1 添加依赖2.2 配置 Gzip 压缩3、服务端应用4、前端应用4.1 N

Spring Boot + MyBatis Plus 高效开发实战从入门到进阶优化(推荐)

《SpringBoot+MyBatisPlus高效开发实战从入门到进阶优化(推荐)》本文将详细介绍SpringBoot+MyBatisPlus的完整开发流程,并深入剖析分页查询、批量操作、动... 目录Spring Boot + MyBATis Plus 高效开发实战:从入门到进阶优化1. MyBatis

MyBatis 动态 SQL 优化之标签的实战与技巧(常见用法)

《MyBatis动态SQL优化之标签的实战与技巧(常见用法)》本文通过详细的示例和实际应用场景,介绍了如何有效利用这些标签来优化MyBatis配置,提升开发效率,确保SQL的高效执行和安全性,感... 目录动态SQL详解一、动态SQL的核心概念1.1 什么是动态SQL?1.2 动态SQL的优点1.3 动态S

Python如何使用__slots__实现节省内存和性能优化

《Python如何使用__slots__实现节省内存和性能优化》你有想过,一个小小的__slots__能让你的Python类内存消耗直接减半吗,没错,今天咱们要聊的就是这个让人眼前一亮的技巧,感兴趣的... 目录背景:内存吃得满满的类__slots__:你的内存管理小助手举个大概的例子:看看效果如何?1.

一文详解SpringBoot响应压缩功能的配置与优化

《一文详解SpringBoot响应压缩功能的配置与优化》SpringBoot的响应压缩功能基于智能协商机制,需同时满足很多条件,本文主要为大家详细介绍了SpringBoot响应压缩功能的配置与优化,需... 目录一、核心工作机制1.1 自动协商触发条件1.2 压缩处理流程二、配置方案详解2.1 基础YAML

MySQL中慢SQL优化的不同方式介绍

《MySQL中慢SQL优化的不同方式介绍》慢SQL的优化,主要从两个方面考虑,SQL语句本身的优化,以及数据库设计的优化,下面小编就来给大家介绍一下有哪些方式可以优化慢SQL吧... 目录避免不必要的列分页优化索引优化JOIN 的优化排序优化UNION 优化慢 SQL 的优化,主要从两个方面考虑,SQL 语

MySQL中慢SQL优化方法的完整指南

《MySQL中慢SQL优化方法的完整指南》当数据库响应时间超过500ms时,系统将面临三大灾难链式反应,所以本文将为大家介绍一下MySQL中慢SQL优化的常用方法,有需要的小伙伴可以了解下... 目录一、慢SQL的致命影响二、精准定位问题SQL1. 启用慢查询日志2. 诊断黄金三件套三、六大核心优化方案方案