计算科学 - 使用 Google 的 ortools 加速解决 LP 的方法 - 吾爱随笔录

我在解决以下形式的 LP 时遇到问题：

min z = c^{T} x

$\min z = c^Tx$

s.t.

$\text{s.t.}$

A x \geq b

$Ax \geq b$

x \geq p

$x\geq p$

1 \leq a_{i j} ≪ b_{i}

$1 \leq a_{ij} \ll b_i$ ,和

p \leq 0

$p \leq 0$

c \geq 0

$c \geq 0$

我在使用 ortools GLOP求解器时遇到的具体问题是：

LP 需要非常长的时间才能在分布式系统上解决，其中每个工作人员都有内核和大约 GB 的内存。对我来说似乎有点太长了。我已经在进行更多计算的小型机器上以更短的时间解决了 TSP 实例（通过 AMPL 使用 CPLEX / Gurobi）。此外，lasso 回归可以简化为单纯形，并且可以在很短的时间内在类似大小的数据上运行。延迟非常重要，我希望在到分钟内完成这个烹饪过程。 $\geq 30$ $240$ $45$ $60$
我已经检查并仔细检查了生成的公式，输出（在小时后）是通过返回的解决方案来解决问题是不可行的。显然，这是不可能的，因为如果我们取，我们就有一个基本可行的解决方案，这意味着存在一个最优解决方案。 $\sim 6$ $x = 0$ $x = b$

关于数据：

$A$ 有行和列。但是，也非常稀疏，每行不超过条目。 $\sim 3 \cdot 10^6$ $\sim 1 \cdot 10^6$ $A$ $2$ $nonzero$

不幸的是，我是 Google 的 ortools 的新手，很难找到有关 API 中特定对象和方法的文档。 $python$

我对可能出现问题的位置和可能的解决方案的猜测是：

如果求解器使用两相单纯形法或“大 M”来查找初始 BFS。我想知道我是否可以通过向 GLOP 求解器（例如）提供初始 BFS 来加快处理速度来加快处理速度？ $x = b$
如果中没有问题，那么问题一定是太难了（值得怀疑）。但是，更好的配方可能会有所帮助。稀疏性表明我可以将其视为网络问题。有人对此有经验吗？ $(1)$ $A$
我可以通过使用Dantzig Wolfe分解之类的方法将“简单”约束（）与硬约束分开来更进一步吗？相关，但我想知道我是否也可以将简单的约束提升到目标中。有这方面的经验吗？ $x \geq p$
（与 3 相关）不确定列生成是否在这里有效，但可以吗？有没有人对这种性质的问题有任何经验？我的直觉是，我可以将 x 视为一组模式，因为 x 是紧密耦合的并且属于自变量集。

最重要的是，如果您以前使用过 Google 的 ortools，您能指出我的传统 API 文档（不是示例）的吗？而且，如果可以的话，您能否分享您的经验以及常见的陷阱和有用的性能改进技巧？ $python$

最后，我喜欢使用像 ortools 这样的开源求解器，而不是为此应用程序支付更昂贵的费用。如果您知道另一个存在的开源解决方案，请在评论中分享。任何具有不错的 Java、Scala 或 python API 的东西都会很棒。分布式解决方案的额外积分。利用 Apache Spark 的分布式环境的东西的额外加分。

非常感谢！