python - 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 可能根本拒绝构造如此大的矩阵(例如参见 Very large matrices using Python and NumPy )，即使 NumPy 毫无问题地创建矩阵，也存在巨大的性能问题。对于 NumPy 必须处理的大量数据，这是很自然的。

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

据我所知(例如 Trying to solve a Scipy optimization problem using sparse matrices and failing )，scipy.optimize.linprog 不适用于稀疏矩阵。因此，我有以下问题:

• SciPy 真的没有提供任何解决具有稀疏矩阵的线性规划的可能性吗？ (如果没有，我该怎么做？)
• 你知道有什么替代库可以更有效解决非稀疏矩阵问题吗？ (据我了解其文档，library 中建议的 thread above 似乎不够灵活，无法满足我的目的)
• 是否可以预期利用矩阵稀疏性的单纯形算法的新实现(使用纯 Python，无 C)会比使用非稀疏矩阵的 SciPy 更有效？

Answer 1

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

用 Python 编写一个稳定、快速、稀疏的 Simplex LP 求解器来替代 SciPy 密集求解器并不是一项简单的练习。此外，用纯 Python 编写的求解器可能性能不佳。

对于您指定的尺寸，虽然不是很大，但很大(可能是大中型模型会是一个很好的分类)您可能需要考虑商业求解器，如 Cplex , Gurobi或 Mosek .这些求解器非常快速且非常可靠(它们基本上可以解决您抛给它们的任何 LP 问题)。它们都有 Python API。求解器对学术界来说是免费的或非常便宜的。

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

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