2

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

主要要求：
最重要的要求是它应该非常快。随机近似解是可以接受的，如果它更快的话。

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因上述大小问题而内存不足。

谁能推荐一些高效的库？请推荐免费和商业可用的，可以用来精确或近似地解决问题。

4

1 回答 1

2

关于其他求解器选项，这里有两个 SO 问题，如果您还没有检查过它们，您应该看看它们：

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

  2. Java 求解器选项

但我发布的原因是我有一些其他的建议给你，而不是追求求解器的速度。（在你的问题中，Q ~ 15K 可能有用，但如果 Q 变大，你将不得不寻找更快的求解器。）

其他尝试的建议

  1. 您是否options在 MATLAB 或 GLPK 中使用过求解器？您可以尝试很多事情：设置iteration limit，或Timelimit（到 10000 毫秒）。

  2. 研究分解和放松你的配方。通常，在这些大型 LP 中有一个很好的底层结构，但是一些密集的约束会破坏运动，而这些约束会给求解器带来麻烦。如果你能识别出这些，你就可以放宽它们，甚至可以用乘数将其放入目标函数中。

    为了使它更具体一点，您考虑“麻烦的约束”的拉格伦松弛。（作为我所指的一个参考，看看问题 12.3 在放松后如何变成 12.4。您可以对问题中的密集几个约束执行相同的操作。

希望这可以帮助您继续前进。

于 2013-11-08T00:43:06.810 回答