最佳开源混合整数优化求解器

Question

我正在使用CPLEX来解决巨大的优化模型(超过100k变量)现在我想看看我是否能找到一个开源替代品,我解决了混合整数问题(MILP)和CPLEX工作得很好但是如果我们这样做很贵想要扩展所以我真的需要找到一个替代方案或开始编写我们自己的ad-hoc优化库(这将是痛苦的)

任何建议/见解将不胜感激

Answer 1

我个人发现GLPK比LP_SOLVE更好(即更快).它支持各种文件格式,另一个优点是它的库接口,可以与您的应用程序平滑集成.

Answer 2

另外对COIN-OR的认可.我们发现线性优化器组件(Clp)非常强,并且通过一些分析可以很好地调整混合整数组件(Cbc).我们与LP-Solve和GLPK进行了比较.

对于非常棘手的问题,商业解决方案是可行的方法.

Answer 3

试试SCIP求解器.我已将它用于MILP问题,具有超过300K变量且性能良好.其MILP性能远优于GLPK.Gurobi在MILP问题上的表现也非常出色(通常比SCIP(2011年5月)更好),但如果您不是学术用户,它可能会很昂贵.Gurobi将使用多核来加速求解器.

Answer 4

你试过lp_solve吗？对于Java,在以下问题中还有一些其他建议:

• Java的数学优化库 - 免费或开源推荐？
• 用于Java的线性编程工具/库

Answer 5

我建议查看COIN项目. 硬币或

这里有许多优秀的求解器,包括非线性问题的ipOPT和一对混合整数求解器.

Answer 6

如果我是你,我会尝试使用诸如Osi(C++)或PuLP(python)之类的多解算器接口,以便您可以编写一次代码,并使用许多求解器进行测试.

如果您要解决的整数程序很大,我建议使用python而不是C++,因为您的代码看起来更干净,并且99%的时间将花费在求解器中.

• https://projects.coin-or.org/Osi
• http://code.google.com/p/pulp-or/

相反,如果问题很小,那么将问题从python内存复制到解算器(来回)的时间不能再被忽略了:在这种情况下,你可以使用编译语言尝试一些明显的性能改进.

但是如果问题非常庞大,那么编译语言将再次获胜,因为内存占用量将大致除以2(在python中没有问题的副本).

Answer 7

Scip也不错!

Answer 8

虽然这可能不是你想听到的,但是商业解决方案CPLEX和Gurobi与另一方面开源求解器之间存在光年.

尽管如此,你可以很幸运,你的模型可以与GLPK,Coin等一起使用,但总的来说,开源解决方案远远落后于商业解决方案.如果不同,没有人会为Gurobi许可证支付12.000美元,而对于CPLEX许可证则更多.

在过去的几年里,我看到很多很多模型对开源求解器来说都很困难.相信我...

这不是一个大小问题,而是数字难题.

Answer 9

我很惊讶没有人提到 MIPCL ( http://www.mipcl-cpp.appspot.com/index.html )。该求解器声称在 LGPL 许可下开源（来源：http ://www.mipcl-cpp.appspot.com/licence.html ://www.mipcl-cpp.appspot.com/licence.html ），因此它也适合在非开源应用程序中使用。但真正开源所缺少的是求解器本身的源代码。

Hans Mittelmann 最近（2017 年 9 月 10 日）做了混合整数线性规划基准：http://plato.asu.edu/ftp/milpc.html（您可能还有兴趣查看概述页面http://plato.asu .edu/bench.html或他演讲的幻灯片：http://plato.asu.edu/talks/informs2017.pdf）。

在具有 12 个线程和 2 小时时间限制的混合整数线性编程基准中，MIPCL 成功解决了 79 个实例。只有商业求解器 CPLEX、Gurobi 和 XPRESS 在给定约束下能够求解更多问题（分别为 86 或 87 个实例）。

此外，就所选性能指标（再次使用 12 个线程）而言，MIPCL 比基准 SCIP 衍生产品（FSCIPC、FSCIPS）和开源求解器 CBC 更快。同样，只有商业求解器 CPLEX、Gurobi 和 XPRESS 在性能方面显着优于 MIPCL。