快速（可能是近似的）线性规划库

Question

我需要解决一个稀疏线性规划问题，正在寻找相应的库。

主要需求：
最重要的要求是速度非常快。如果速度更快，则可以接受随机近似解。

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 对于上述大小的问题会耗尽内存。

请问有哪些高效的库？请同时提供免费和商业可用的库，可用于精确或近似求解问题。

- user2966082

---

呵呵...“如果更快，随机近似解是可以接受的。”好的，42就是解决方案...大致随机，非常近似，给定某个任意阈值... - twalberg

lpsolve是一个非常高效（单线程）的开源LP/MILP求解器。在我的三年老i7笔记本电脑上，它可以在不到5秒钟的时间内解决具有1000个变量和2000个约束条件的密集问题。就商业求解器而言，我建议您看看Gurobi，它提供了一个高效的多线程LP引擎。 - Anders Gustafsson

Answer 1

关于其他求解器选项，如果你还没有查看过的话，以下是两个SO问题，建议你去看一下：

1. 关于使用哪些求解器的SO问题

2. Java求解器选项

但我发帖的原因是，我有几个其他建议，而不是只考虑求解器速度。（对于Q ~ 15K的问题可能会有用，但如果Q变得更大，你将不得不寻找更快的求解器。）

尝试其他建议

1. 你是否在MATLAB或GLPK中尝试了求解器选项？有很多事情可以尝试：设置迭代次数限制，或者时间限制（10000毫秒）。

2. 研究分解和放松你的公式。通常，在这些大型LP中有一个不错的基本结构，但是一些密集的约束条件会破坏它们，并给求解器造成麻烦。如果你能识别出那些问题所在，你可以放松它们，甚至可以用乘数将其放入目标函数中。

   为了使它更加具体，你可以考虑“Lagranian relaxations”来处理“棘手的约束”。（关于我所指的内容，请参考这里的问题12.3在被放松后变成了12.4。你可以对问题中的一些密集约束条件采取同样的措施。）

希望这能帮助你前进。

- Ram Narasimhan