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

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

相关文章

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. 诊断黄金三件套三、六大核心优化方案方案

Redis中高并发读写性能的深度解析与优化

《Redis中高并发读写性能的深度解析与优化》Redis作为一款高性能的内存数据库,广泛应用于缓存、消息队列、实时统计等场景,本文将深入探讨Redis的读写并发能力,感兴趣的小伙伴可以了解下... 目录引言一、Redis 并发能力概述1.1 Redis 的读写性能1.2 影响 Redis 并发能力的因素二、

使用国内镜像源优化pip install下载的方法步骤

《使用国内镜像源优化pipinstall下载的方法步骤》在Python开发中,pip是一个不可或缺的工具,用于安装和管理Python包,然而,由于默认的PyPI服务器位于国外,国内用户在安装依赖时可... 目录引言1. 为什么需要国内镜像源?2. 常用的国内镜像源3. 临时使用国内镜像源4. 永久配置国内镜

C#原型模式之如何通过克隆对象来优化创建过程

《C#原型模式之如何通过克隆对象来优化创建过程》原型模式是一种创建型设计模式,通过克隆现有对象来创建新对象,避免重复的创建成本和复杂的初始化过程,它适用于对象创建过程复杂、需要大量相似对象或避免重复初... 目录什么是原型模式?原型模式的工作原理C#中如何实现原型模式?1. 定义原型接口2. 实现原型接口3

Java嵌套for循环优化方案分享

《Java嵌套for循环优化方案分享》介绍了Java中嵌套for循环的优化方法,包括减少循环次数、合并循环、使用更高效的数据结构、并行处理、预处理和缓存、算法优化、尽量减少对象创建以及本地变量优化,通... 目录Java 嵌套 for 循环优化方案1. 减少循环次数2. 合并循环3. 使用更高效的数据结构4

基于Python实现多语言朗读与单词选择测验

《基于Python实现多语言朗读与单词选择测验》在数字化教育日益普及的今天,开发一款能够支持多语言朗读和单词选择测验的程序,对于语言学习者来说无疑是一个巨大的福音,下面我们就来用Python实现一个这... 目录一、项目概述二、环境准备三、实现朗读功能四、实现单词选择测验五、创建图形用户界面六、运行程序七、

前端知识点之Javascript选择输入框confirm用法

《前端知识点之Javascript选择输入框confirm用法》:本文主要介绍JavaScript中的confirm方法的基本用法、功能特点、注意事项及常见用途,文中通过代码介绍的非常详细,对大家... 目录1. 基本用法2. 功能特点①阻塞行为:confirm 对话框会阻塞脚本的执行,直到用户作出选择。②