PuLP在添加大量约束条件时运行速度非常缓慢

Question

我正在尝试使用PuLP，但添加4000个约束（67个变量）需要50秒。解决问题仅需几分之一秒。我们想使用PuLP轻松测试大量问题的几个求解器。PuLP是否应该花费这么长时间？直接使用PyGLPK只需不到一秒钟，包括设置和求解。我希望不是这样。如何提高PuLP中此步骤的效率？

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

- jmilloy

---

你能分享一下PuLP代码片段，其中添加了4000个约束条件到LP中吗？ - Ram Narasimhan

你能否在这个问题上进行评论：https://datascience.stackexchange.com/questions/49792/adding-constraints-in-pulp-optimization-problems-in-python - KHAN irfan

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添加限制条件，而不是首先构建限制条件列表，然后在最后将这些限制条件添加到PuLP中？

- Jesper - jtk.eth

---

谢谢。我可能还有那段代码，如果是的话，我会回去看一下它。 - jmilloy

是的，我使用了 lpSum，但我也使用 += 来添加约束。你能发一下另一种方法的代码吗？ - jmilloy

看起来正在开发一个补丁，通过使用类的__iadd__方法实际上允许"+="。这尚未得到PuLP作者的验证，但似乎很有前途。请查看以下链接： https://groups.google.com/forum/#!topic/pulp-or-discuss/6Q6tEBhdZ9I - Jesper - jtk.eth

请发布解决速度问题的代码。 从谷歌小组中，我不清楚我做错了什么。我也很慢地添加了约束条件。对我来说，添加4000个需要30分钟。 - Gulzar

Answer 2

我曾经遇到过类似的问题，我的目标函数中有超过10,000个变量。根本原因与原帖中所述相同。使用pulp.LpVariable数组上的sum比使用pulp.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])

我没有精确地计时两个版本。为了让你有一个时间差的想法，当运行较慢的版本时，我能够搜索互联网以了解为什么pulp可能如此缓慢，找到这个StackOverflow问题，阅读相关讨论并更新我的代码，而在此期间表达式还未完成评估。第二个版本需要几秒钟。

- wrdieter