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

文章目录

  • 前言
  • 求解器对比
    • 问题延伸:商用求解器和开源求解器的差别是什么?
  • 求解器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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/228762.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

2023年山东省职业院校技能大赛信息安全管理与评估二三阶段样题

2023年山东省职业院校技能大赛信息安全管理与评估二三阶段 样题 第二阶段 模块二 网络安全事件响应、数字取证调查、应用程序安全 一、竞赛内容 Geek极安云科专注技能竞赛技术提升,基于各大赛项提供全面的系统性培训,拥有完整的培训体系。团队拥有曾…

Ignis - Interactive Fire System

Ignis - 点火、蔓延、熄灭、定制! 全方位火焰系统。 这个插件在21年的项目中使用过很好用值使用概述 想玩火吗?如果想的话,那么Ignis就是你的最佳工具。有了Ignis,你可以把任何物体、植被或带皮带骨的网状物转换为可燃物体,它就会自动着火。然后,火焰可以蔓延,点燃其他物…

如何在Android平板上远程连接Ubuntu服务器使用code-server代码开发

目录 1.ubuntu本地安装code-server 2. 安装cpolar内网穿透 3. 创建隧道映射本地端口 4. 安卓平板测试访问 5.固定域名公网地址 6.结语 1.ubuntu本地安装code-server 准备一台虚拟机,Ubuntu或者centos都可以,这里以VMwhere ubuntu系统为例 下载code server服务…

怎么将用户引流到你的私域中?

微信私域运营是一种利用微信平台建立与用户深度联系的营销方式,可在私域中触达并服务用户。 那么如何将在将用户引流至你的私域中呢? 可以从以下几个小方法入手。 ①打造一个吸引人的个人品牌形象非常重要。在社交媒体上展示真实、独特、专业的一面&a…

C/C++端口复用SO_REUSEADDR(setsockopt参数),test ok

端口复用最常用的用途应该是防止服务器重启时之前绑定的端口还未释放或者程序突然退出而系统没有释放端口。这种情况下如果设定了端口复用,则新启动的服务器进程可以直接绑定端口。如果没有设定端口复用,绑定会失败,提示ADDR已经在使用中——…

C# 语法笔记

1.ref、out:参数传递的两种方式 ref:引用传递 using System; namespace CalculatorApplication {class NumberManipulator{public void swap(ref int x, ref int y){int temp;temp x; /* 保存 x 的值 */x y; /* 把 y 赋值给 x */y temp; /* 把 t…

巧用静默,原来真的可以告警零误报!

前言 在当今的信息技术环境中,系统的稳定性和安全性至关重要。然而,在进行计划内的升级维护时,监控系统往往会产生大量的误报警告,给运维人员带来不必要的困扰。为了解决这一问题,组织可以通过合理设置静默规则&#…

如何选择 Facebook 代理?

Facebook上从事业务推广、广告或资料推广以及群组的用户需要高质量且可靠的代理。使用代理,用户可以在账号被封锁的情况下访问自己的资料,同时与多人进行即时通信,并能够: 自动发送邀请参加各种活动; 通过特殊的机器人…

中国开源大模型登顶HuggingFace排行榜

12月8日消息,全球最大的开源大模型社区HuggingFace日前公布了最新的开源大模型排行榜,阿里云通义千问力压Llama2等国内外开源大模型登顶榜首。 HuggingFace的开源大模型排行榜(Open LLM Leaderboard)是目前大模型领域最具权威性的…

SpringAMQP 快速入门

SpringAMQP 快速入门 1. 创建项目2. 快速入门2.2.1 消息发送2.2.2 消息接收 3. 交换机3.1 Fanout Exchange(扇出交换机)3.1.1 创建队列与交换机3.1.2 消息接收3.1.3 消息发送 3.2 Direct Exchange(直连交换机)3.2.1 创建交换机与队…

❤ Mac IDEA使用并运行项目

❤ IDEA导入项目并运行 Mac IDEA使用 (1) 仓库导入 通过获取giett仓库包的url,在idea中导入项目 在gitee里获取项目的ur打开idea,点击 File->new->Project from Version Control (2) 创建数据库ry并导入数据脚本 (3)修改配…

JOSEF 单稳态中间继电器 UEG/A-4H-L DC110V 导轨安装

系列型号 UEG/A-2H2D中间继电器UEG/A-4H4D中间继电器UEG/A-2D中间继电器 UEG/A-2H中间继电器UEG/A-4H中间继电器UEG/A-4D中间继电器 UEG/A-6H中间继电器UEG/A-6D中间继电器UEG/A-8H中间继电器 UEG/A-10D中间继电器UEG/A-10H中间继电器UEG/A-2DPDT中间继电器 UEG/A-4DPDT中…

用网安技术去合法挖漏洞,一个月能拿多少钱?想不到吧!

学会网安技术后去挖漏洞一个月能搞多少外快? 现在很多白帽子都是白天上班晚上挖洞,甚至有的人连班都不想上,纯靠挖漏洞来收入,比如说补天上面的这些人,每个月收入较高的都是他们,八成都是在家全职挖洞了。…

echarts绘制一个环形图2

其他echarts&#xff1a; echarts绘制一个环形图 echarts绘制一个柱状图&#xff0c;柱状折线图 echarts绘制一个饼图 效果&#xff1a; 组件代码&#xff1a; <template><div class"wrapper"><div ref"doughnutChart2" id"dough…

脉冲压缩及MATLAB仿真

文章目录 前言一、脉冲压缩二、MATLAB 仿真1、LFM 脉冲压缩匹配滤波实现测距①、MATLAB 源码②、仿真结果1) LFM 时域波形2) LFM 频域波形3) 两个未分辨目标的合成回波信号4) 脉冲压缩检测距离 2、去协处理仿真①、MATLAB 源码②、仿真结果1) 未压缩回波信号&#xff0c;3个目标…

C语言——2048完整版

2048是一个简单又有趣的小游戏&#xff0c;相信大家都接触并了解过&#xff0c;那如何通过代码来实现他呢&#xff1f;下面就让我们来一起看看。 目录 1、头文件 2、主函数 3、 StarGame 4、GetNum 5、Show 6、Picture 7、GetButton 8、MergeLeft 9、MergeUp 10、MergeR…

python圣诞树代码编程

以下是一个简单的Python圣诞树代码&#xff1a; def draw_tree(height): for i in range(height): print( * (height - i - 1) * * (2 * i 1)) print( * (height - 1) |)draw_tree(10) 这个函数会绘制一个等腰三角形&#xff0c;其中每一行的星号数量从1开…

改造后的LED电子大屏幕:环保与节能的新选择

随着人们生活水平和文明程度的提高&#xff0c;对于环保的意识也日益增强。这在支付宝几亿用户参与蚂蚁森林环保项目中体现得淋漓尽致&#xff0c;为环保事业贡献一份力量。为迎合这一时代发展的要求&#xff0c;LED显示屏厂家早已推出了亮度可调的LED节能屏。如今&#xff0c;…

linux高级篇基础理论七(Tomcat)

♥️作者&#xff1a;小刘在C站 ♥️个人主页&#xff1a; 小刘主页 ♥️不能因为人生的道路坎坷,就使自己的身躯变得弯曲;不能因为生活的历程漫长,就使求索的 脚步迟缓。 ♥️学习两年总结出的运维经验&#xff0c;以及思科模拟器全套网络实验教程。专栏&#xff1a;云计算技…

html、css类名命名思路整理

开发页面时&#xff0c;老是遇到起名问题&#xff0c;越想越头疼&#xff0c;严重影响开发进度&#xff0c;都是在想名字&#xff0c;现在做一下梳理&#xff0c;统一一下思想&#xff0c;希望以后能减少这块的痛苦。 命名规则 [功能名称]__[组成部分名称]--[样式名称] 思路…