Scipy：稀疏矩阵的线性规划

Question

我想用python解决一个线性程序。变量的数量（从现在开始我称之为 N）非常大（~50000），为了以scipy.optimize.linprog需要的方式表述问题，我必须构造两个 N x N 矩阵（A及B以下）。LP 可以写成

minimize: c.x
subject to:
    A.x <= a
    B.x  = b
    x_i >= 0 for all i in {0, ..., n}

其中.表示点积a，而b、 和c是长度为 N 的向量。

我的经验是构建如此大的矩阵（A并且B都有大约 50000x50000 = 25*10^8 个条目）会带来一些问题：如果硬件不是很强大，NumPy 可能根本拒绝构建如此大的矩阵（参见例如使用 Python 和 NumPy 的非常大的矩阵），即使 NumPy 创建矩阵没有问题，也存在巨大的性能问题。对于 NumPy 必须处理的大量数据，这是很自然的。

然而，尽管我的线性程序带有 N 个变量，但我使用的矩阵非常稀疏。其中一个只有第一行的条目，另一个只有前 M 行，其中 M < N/2。当然，我想利用这个事实。

据我所知（例如，尝试使用稀疏矩阵和失败来解决 Scipy 优化问题），scipy.optimize.linprog不适用于稀疏矩阵。因此，我有以下问题：

• SciPy 真的没有提供解决具有稀疏矩阵的线性程序的任何可能性吗？（如果没有，我该怎么做？）
• 你知道有什么替代库可以比使用非稀疏矩阵的 SciPy更有效地解决问题吗？（上面线程中建议的库似乎不足以满足我的目的-据我了解其文档）
• 能否预期利用矩阵稀疏性的单纯形算法的新实现（使用纯 Python，没有 C）将比使用非稀疏矩阵的 SciPy 更有效？

Answer 1

我会说形成一个（或两个）密集矩阵来解决一个大的稀疏 LP 可能不是正确的做法。在求解大型稀疏 LP 时，重要的是使用具有处理此类问题的工具的求解器，并以不显式创建任何这些零元素的方式生成模型。

用 Python 编写一个稳定、快速、稀疏的 Simplex LP 求解器来替代 SciPy 密集求解器并非易事。此外，用纯 Python 编写的求解器可能表现不佳。

对于您指出的大小，虽然不是很大，但（可能是大型中型模型是一个很好的分类），您可能需要考虑像Cplex、Gurobi或Mosek这样的商业求解器。这些求解器非常快速且非常可靠（它们基本上可以解决您向它们提出的任何 LP 问题）。它们都有 Python API。求解器对于学者来说是免费的或非常便宜的。

如果您想使用开源求解器，您可能需要查看 COIN CLP 求解器。它还有一个Python 接口。

如果您的模型更复杂，那么您可能还需要考虑使用 Python 建模工具，例如Pulp或Pyomo（Gurobi 在 Python 中也有很好的建模支持）。