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

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

相关文章

Vue3 的 shallowRef 和 shallowReactive:优化性能

大家对 Vue3 的 ref 和 reactive 都很熟悉,那么对 shallowRef 和 shallowReactive 是否了解呢? 在编程和数据结构中,“shallow”(浅层)通常指对数据结构的最外层进行操作,而不递归地处理其内部或嵌套的数据。这种处理方式关注的是数据结构的第一层属性或元素,而忽略更深层次的嵌套内容。 1. 浅层与深层的对比 1.1 浅层(Shallow) 定义

如何选择适合孤独症兄妹的学校?

在探索适合孤独症儿童教育的道路上,每一位家长都面临着前所未有的挑战与抉择。当这份责任落在拥有孤独症兄妹的家庭肩上时,选择一所能够同时满足两个孩子特殊需求的学校,更显得尤为关键。本文将探讨如何为这样的家庭做出明智的选择,并介绍星贝育园自闭症儿童寄宿制学校作为一个值得考虑的选项。 理解孤独症儿童的独特性 孤独症,这一复杂的神经发育障碍,影响着儿童的社交互动、沟通能力以及行为模式。对于拥有孤独症兄

HDFS—存储优化(纠删码)

纠删码原理 HDFS 默认情况下,一个文件有3个副本,这样提高了数据的可靠性,但也带来了2倍的冗余开销。 Hadoop3.x 引入了纠删码,采用计算的方式,可以节省约50%左右的存储空间。 此种方式节约了空间,但是会增加 cpu 的计算。 纠删码策略是给具体一个路径设置。所有往此路径下存储的文件,都会执行此策略。 默认只开启对 RS-6-3-1024k

使用opencv优化图片(画面变清晰)

文章目录 需求影响照片清晰度的因素 实现降噪测试代码 锐化空间锐化Unsharp Masking频率域锐化对比测试 对比度增强常用算法对比测试 需求 对图像进行优化,使其看起来更清晰,同时保持尺寸不变,通常涉及到图像处理技术如锐化、降噪、对比度增强等 影响照片清晰度的因素 影响照片清晰度的因素有很多,主要可以从以下几个方面来分析 1. 拍摄设备 相机传感器:相机传

C#实战|大乐透选号器[6]:实现实时显示已选择的红蓝球数量

哈喽,你好啊,我是雷工。 关于大乐透选号器在前面已经记录了5篇笔记,这是第6篇; 接下来实现实时显示当前选中红球数量,蓝球数量; 以下为练习笔记。 01 效果演示 当选择和取消选择红球或蓝球时,在对应的位置显示实时已选择的红球、蓝球的数量; 02 标签名称 分别设置Label标签名称为:lblRedCount、lblBlueCount

MySQL高性能优化规范

前言:      笔者最近上班途中突然想丰富下自己的数据库优化技能。于是在查阅了多篇文章后,总结出了这篇! 数据库命令规范 所有数据库对象名称必须使用小写字母并用下划线分割 所有数据库对象名称禁止使用mysql保留关键字(如果表名中包含关键字查询时,需要将其用单引号括起来) 数据库对象的命名要能做到见名识意,并且最后不要超过32个字符 临时库表必须以tmp_为前缀并以日期为后缀,备份

透彻!驯服大型语言模型(LLMs)的五种方法,及具体方法选择思路

引言 随着时间的发展,大型语言模型不再停留在演示阶段而是逐步面向生产系统的应用,随着人们期望的不断增加,目标也发生了巨大的变化。在短短的几个月的时间里,人们对大模型的认识已经从对其zero-shot能力感到惊讶,转变为考虑改进模型质量、提高模型可用性。 「大语言模型(LLMs)其实就是利用高容量的模型架构(例如Transformer)对海量的、多种多样的数据分布进行建模得到,它包含了大量的先验

SWAP作物生长模型安装教程、数据制备、敏感性分析、气候变化影响、R模型敏感性分析与贝叶斯优化、Fortran源代码分析、气候数据降尺度与变化影响分析

查看原文>>>全流程SWAP农业模型数据制备、敏感性分析及气候变化影响实践技术应用 SWAP模型是由荷兰瓦赫宁根大学开发的先进农作物模型,它综合考虑了土壤-水分-大气以及植被间的相互作用;是一种描述作物生长过程的一种机理性作物生长模型。它不但运用Richard方程,使其能够精确的模拟土壤中水分的运动,而且耦合了WOFOST作物模型使作物的生长描述更为科学。 本文让更多的科研人员和农业工作者

cross-plateform 跨平台应用程序-03-如果只选择一个框架,应该选择哪一个?

跨平台系列 cross-plateform 跨平台应用程序-01-概览 cross-plateform 跨平台应用程序-02-有哪些主流技术栈? cross-plateform 跨平台应用程序-03-如果只选择一个框架,应该选择哪一个? cross-plateform 跨平台应用程序-04-React Native 介绍 cross-plateform 跨平台应用程序-05-Flutte

如何选择SDR无线图传方案

在开源软件定义无线电(SDR)领域,有几个项目提供了无线图传的解决方案。以下是一些开源SDR无线图传方案: 1. **OpenHD**:这是一个远程高清数字图像传输的开源解决方案,它使用SDR技术来实现高清视频的无线传输。OpenHD项目提供了一个完整的工具链,包括发射器和接收器的硬件设计以及相应的软件。 2. **USRP(Universal Software Radio Periphera