<分区>
我需要解决一个稀疏线性规划问题，我正在寻找一个相同的库。
主要要求:
最重要的要求是它应该非常快。如果速度更快，则可以接受随机近似解。
LP 规范:
问题的大小是 2 个参数的函数:P 和 Q，大多数时候 P << Q。
变量数 ~ P + Q
约束数量 ~ 2Q
约束矩阵是稀疏的——它只有 O(Q) 个非零项。
尝试过的解决方案
1) MATLAB : MATLAB 的 linprog 函数在我们的设置中不是特别有用，因为求解 LP 需要很长时间。
2) GLPK:glpk_simplex 也没有预期的那么快 - 对于 P=15，Q=15,000 的问题，我最多需要 10 秒才能得到答案，但是glpk_simplex 需要 20-25 分钟。 glpk_interior 因上述大小的问题而耗尽内存。
谁能推荐一些高效的库？请推荐可用于精确或近似解决问题的免费和商业可用的。
最佳答案
关于其他求解器选项，这里有两个 SO 问题，如果您还没有检查过它们，您应该看看它们:
但是我发帖的原因是我有一些其他的建议给你，而不是为了求解器的速度。 (某些方法可能适用于您问题中的 Q ~ 15K，但如果 Q 变大，您将不得不寻找更快的求解器。)
您是否在 MATLAB 或 GLPK 中使用过求解器选项？您可以尝试很多事情:设置 iteration limit 或 Timelimit(至 10000 毫秒)。
研究分解和放松你的公式。通常，在这些大型 LP 中，有一个很好的底层结构，但一些密集的约束会破坏运动，而这些约束会给求解器带来麻烦。如果你能识别出那些，你就可以放宽它们，甚至可以将其放入带有乘数的目标函数中。
为了使它更具体一点，您考虑将拉格朗尼松弛用于“麻烦的约束”。 (作为对我所指的内容的一个引用 see how problem 12.3 becomes 12.4 here 放松下来之后。您可以对问题中的密集多个约束执行相同的操作。
希望这能帮助您前进。
关于shared-libraries - 快速(可能近似)线性规划库，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19844030/