我目前正在使用CPLEX解决巨大的优化模型（超过100k个变量），现在我想看看是否能找到一个开源替代方案。我解决混合整数问题（MILP），CPLEX效果很好，但如果我们要进行扩展，它非常昂贵，因此我真的需要找到替代方案或开始编写自己的特定优化库（这将是痛苦的）。
非常感谢任何建议/见解。
最佳开源混合整数优化求解器
61
- Siamak
2
110万个变量是一个非常大的问题！我认为你可以把更多的时间投入到改变建模上。Lpsolve和glpk无法在合理的时间内支持解决这么多整数变量的问题。 - user1833905
3一如既往，最有用的问题会被标记为技术性问题。从更大的角度来看，这个问题对知识库做出了很大的贡献。 - GavinBelson
13个回答
26
对于COIN-OR的再次认可。我们发现线性优化组件（Clp）非常强大，而混合整数组件（Cbc）可以通过一些分析进行良好的调整。我们与LP-Solve和GLPK进行了比较。
对于非常棘手的问题，商业求解器是最好的选择。
- dtw
17
尝试使用SCIP求解器。我已经用它解决了超过300K个变量的MILP问题，并获得了良好性能。它的MILP性能比GLPK要好得多。Gurobi在MILP问题上也表现出色（通常优于SCIP（2011年5月）），但如果您不是学术用户，则可能成本较高。 Gurobi将使用多核来加速求解器。
- user764309
5
10SCIP遗憾地不是开源软件。 - Falk Hüffner
3你真的有超过30万个变量吗？其中有多少个具有整数限制条件？ - ldog
@FalkHüffner：也许以前不是，但据我所知（十年后...），现在它实际上是开源的... - Moot
SCIP仍然不是开源软件，因为许可证不允许非学术机构成员使用它，即使对于学者来说，许可证也有要求，这将使其无法按照通常定义的开源方式开放。 - Falk Hüffner
1看起来SCIP现在终于是开源的了，从这个提交开始：https://github.com/scipopt/scip/commit/6f43a160aac6b4da57185c87d31a9a726f5e98a1。他们将许可证更改为Apache-2.0。 - qbt937
14
如果我是你，我会尝试使用多求解器接口，如Osi（C++）或PuLP（Python），这样您只需编写一次代码，即可使用多个求解器进行测试。
如果您要解决的整数规划问题非常大，我建议使用Python而不是C ++，因为您的代码将更加清晰，并且99％的时间都将用于求解器。 如果问题比较小，那么从Python内存复制问题到求解器的时间（来回）就不能被忽略：在这种情况下，您可以尝试使用编译语言来获得明显的性能提升。但是，如果问题非常巨大，那么编译语言将再次获胜，因为内存占用量将大致减少一半（Python中不需要复制问题）。
如果您要解决的整数规划问题非常大，我建议使用Python而不是C ++，因为您的代码将更加清晰，并且99％的时间都将用于求解器。 如果问题比较小，那么从Python内存复制问题到求解器的时间（来回）就不能被忽略：在这种情况下，您可以尝试使用编译语言来获得明显的性能提升。但是，如果问题非常巨大，那么编译语言将再次获胜，因为内存占用量将大致减少一半（Python中不需要复制问题）。
- user48678
3
1我之前使用了lp_solve，然后转而使用pulp。默认情况下，它使用COIN-OR。对于我遇到的一个有200个决策变量的MIP问题，lp_solve花费了55分钟，GLPK花费了67分钟，而Coin-or只用了0.2秒钟就解决了。 - Ant6n
抱歉打扰，但是所有求解器实现的内存占用情况都是真实的吗？（例如，即使使用像Gurobi这样的商业求解器？）这将是使用Python的一个巨大缺点。 - m4p85r
我相信是这样的。所有的Python实现都是C库的包装器。因此，对于每个变量，您都会得到一个指向C值的Python变量=所需内存的两倍。对于任何包装语言来说都是如此，因此您将在C++中遇到完全相同的问题。如果您想要最小化使用的内存，则需要使用纯C并从那里构建问题矩阵。不过，我不会太担心这个问题：使用良好的抽象所获得的生产力将使您能够测试更多的东西，并导致更好的实现。只有在没有选择时才转向纯C。 - user48678
6
虽然这可能不是你想听到的，但商业求解器CPLEX和Gurobi与开源求解器之间相差甚远。尽管你可能很幸运，你的模型可以在GLPK、Coin或类似工具中顺利运行，但总体而言，开源解决方案远远落后于商业求解器。如果情况不同，就没有人会为Gurobi许可证支付12,000美元或更多的CPLEX许可证费用了。
在过去的几年里，我见过许多许多的模型，它们对于开源求解器来说太难了。相信我...
这并不是问题的规模，而是数值难度的问题。
在过去的几年里，我见过许多许多的模型，它们对于开源求解器来说太难了。相信我...
这并不是问题的规模，而是数值难度的问题。
- Knasterbax
3
你能详细说明一下哪些类型的模型对于开源求解器来说太难了吗？ - Anne van Rossum
2我们一直在为燃气行业和燃气分配建立模型，其中有数十个模型对于开源求解器来说过于复杂。通常情况下，LP 模型并不是大问题，但当涉及到 MIP 模型时，只有商业求解器能够胜任。通常我们的模型拥有数万个变量，但这并不是那么重要。 - Knasterbax
2我并不完全反对你的评论，但在某些情况下，开源求解器与商业求解器一样有效。这就是为什么我建议使用多求解器库。这样，您将能够将求解器视为引擎，并轻松切换求解器，甚至在商业求解器之间进行比较。不要将自己锁定在某种技术中，使用通用框架！ - user48678
5
我很惊讶没有人提到MIPCL（http://www.mipcl-cpp.appspot.com/index.html）。该求解器声称是在LGPL许可下的开源软件（来源：http://www.mipcl-cpp.appspot.com/licence.html），因此也适用于非开源应用程序。但要成为真正的开源还缺少求解器本身的源代码。
此外，在选择的性能指标方面（再次使用12个线程），MIPCL比基准测试中的SCIP派生版本（FSCIPC，FSCIPS）和开源求解器CBC更快。同样，只有商业求解器CPLEX，Gurobi和XPRESS在性能方面明显优于MIPCL。
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个线程），MIPCL比基准测试中的SCIP派生版本（FSCIPC，FSCIPS）和开源求解器CBC更快。同样，只有商业求解器CPLEX，Gurobi和XPRESS在性能方面明显优于MIPCL。
- Nubok
2
1MIPCL 发生了什么？链接失效了。 - Jacko
@Jacko，我不知道MIPCL发生了什么事情，但MIPCL的作者是Nicolai Pisaruk。他的LinkedIn页面是https://by.linkedin.com/in/nicolai-pisaruk-93981916a。为什么不问问他并在这里发布他的答案：我也很好奇原因。 :-) - Nubok
2
我会在原本优秀的答案中添加以下内容。
虽然其他人已经指出商业求解器比免费的替代品快得多且更有能力，但考虑您可以接受多少最优性差距是很重要的。对于具有许多整数变量的大型问题，如果您可以接受1%甚至更大的最优性差距（默认值通常为0.01%或更低），则可能会获得更快的求解时间。
当然，如果您正在解决一个1%等于数百万美元的问题，这是不可接受的 - 因此需要顶尖求解器市场。（一些Gurobi与免费求解器的比较here）
我同意其他人的观点，使用生成求解器无关问题文件的平台（例如*.mps、*.lp文件）是值得的，因为您可以尝试其他求解器。我正在使用PuLP，并发现它和免费的COIN_CBC求解器都非常出色。虽然在具有许多整数变量的问题上受到限制。
虽然其他人已经指出商业求解器比免费的替代品快得多且更有能力，但考虑您可以接受多少最优性差距是很重要的。对于具有许多整数变量的大型问题，如果您可以接受1%甚至更大的最优性差距（默认值通常为0.01%或更低），则可能会获得更快的求解时间。
当然，如果您正在解决一个1%等于数百万美元的问题，这是不可接受的 - 因此需要顶尖求解器市场。（一些Gurobi与免费求解器的比较here）
我同意其他人的观点，使用生成求解器无关问题文件的平台（例如*.mps、*.lp文件）是值得的，因为您可以尝试其他求解器。我正在使用PuLP，并发现它和免费的COIN_CBC求解器都非常出色。虽然在具有许多整数变量的问题上受到限制。
- kabdulla
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接