枣庄市建设项目环评备案网站,使用c#语言建设网站优点,推广任务平台,做网站找个人还是公司文章目录 前言求解器对比问题延伸#xff1a;商用求解器和开源求解器的差别是什么#xff1f; 求解器PK总结参考资料 前言
求解器对于运筹算法工程师而言#xff0c;常常像一个黑盒#xff0c;我们扔进去输入数据和数学模型#xff0c;求解器给我们吐出一个解出来。这种状… 文章目录 前言求解器对比问题延伸商用求解器和开源求解器的差别是什么 求解器PK总结参考资料 前言
求解器对于运筹算法工程师而言常常像一个黑盒我们扔进去输入数据和数学模型求解器给我们吐出一个解出来。这种状态在面临规模小、形式简单的数学模型是还可以应付的但一旦问题难度上来原本用着舒服的求解器可能求解你的问题太慢了又或者根本无法给到符合预期的解这时就会面临到底选择哪个求解器更合适的问题
这里的合适代表既准又快需要综合考虑
自己的问题类型是什么线性规划整数规划二次规划这里可以参考我的文章运筹学算法分类快速判断不同求解器适用的问题类型开源还是商用
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的最快的非商业求解器之一、支持BranchPrice、支持 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调用IPOPT0-1变量给出小数解血泪教训
2快速实验找一个支持的求解器在小规模case上测试下 如果你的问题规模本身就很小而且在这一步的求解质量和速度都已经满足要求了那么恭喜你不用再继续往下看了多测试一些case保证模型的鲁棒性即可。如果你不幸的发现小规模测试OK但测试案例规模放大模型求解很久仍然没有给到解无法支持上线实时计算的规模和时间要求和现在的我一样那么就进入下一步的打怪中。
3优化大规模问题的求解速度 这里持续更新中我还在调研…
参考资料
Evaluating Operational Research Solvers整数规划求解器介绍The advantages of commercial solversWhat does CPLEX solve ?Python运筹学求解器市面上的数学规划求解器有哪些COIN-OR H. Mittelmann 教授的评测网站Visualizations of Mittelmann benchmarks
