添加许多约束时,PuLP非常慢

Question

我正在尝试使用PuLP,但是需要50秒才能添加4000个约束(67个变量).解决问题只需要几分之一秒.

我们希望使用PuLP轻松测试一大堆问题上的几个求解器.

它应该花这么长时间服用PuLP吗？直接使用PyGLPK只需要一小部分时间,包括设置和求解,所以我希望不会.我该怎么做才能提高PuLP中这一步骤的效率？

---

更新

我的约束矩阵非常稀疏,并且通过仅包括非零系数,我能够将该特定问题的建立时间减少到4或5秒.我仍然能够编写自己的.lp或.mps格式的文件,用cbc或glpsol子进程解决问题,并且比PuLP更有效地解析解决方案,因为我可以在几毫秒内编写输入文件PuLP需要几秒钟.我仍然不确定为什么会这样.

Answer 1

我没有足够的代表发表评论.

但是你看过这个:

https://groups.google.com/forum/#!topic/pulp-or-discuss/p1N2fkVtYyM

问的问题是:

"The problem is solved in less than 0.5 second.
However setting it up with PULP takes more than 10 seconds. "

这似乎也是你报告的内容.解决方案是不使用+ =或sum(...)运算符,而是如链接中所解释的那样:

yeah using the += operator with pulp is really slow, as is using sum() 
instead of lpSum()

那么也许你是一次向PuLP添加约束1而不是先构建约束列表然后在最后将约束添加到PuLP中？

Answer 2

我遇到了类似的问题，我的目标函数使用了一个包含 > 10,000 个变量的表达式。根本原因与原始发布者所看到的相同。与 相比，sum在 数组上使用确实很慢。根据已接受答案中的 Google 群组讨论，我能够使我的代码运行得更快。我知道这是一个老问题，但会为不耐烦的人提供一些抽象代码。pulp.LpVariablepulp.LpAffineExpression

最初的目标是这样的：

sum([x * k for x in xs] + ys)

其中xs是 的列表pulp.LpVariable，k是浮点常量，ys是 的另一个列表pulp.LpVariable。

一个更快的版本是：

pulp.LpAffineExpression([(x, k) for x in xs] + [(y, 1.0) for y in ys])

我没有精确计算这两个版本的时间。为了了解时间差异，在运行慢速版本时，我能够在互联网上搜索为什么纸浆可能如此慢，找到这个 StackOverflow 问题，阅读链接的讨论，并在表达式完成评估之前更新我的代码。第二个版本需要几秒钟。