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 是否真的没有提供任何求解具有稀疏矩阵的线性规划的可能性？（如果没有，我该怎么做？）
你知道有什么替代库可以比SciPy更有效解决非稀疏矩阵问题吗？（library suggested in the thread above 对于我的目的来说似乎不够灵活——据我了解它的文档）
是否可以预期利用矩阵稀疏性的单纯形算法的新实现（使用普通 Python，无 C）将比使用非稀疏矩阵的 SciPy 更有效矩阵？

Answer 1

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

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

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

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

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

Answer 2

我不敢相信没有人向您指出 PuLP 的方向！您将能够高效地创建问题，如下所示：

import pulp
prob = pulp.LpProblem("test problem",pulp.LpMaximize)
x = pulp.LpVariable.dicts('x', range(5), lowBound=0.0)
prob += pulp.lpSum([(ix+1)*x[ix] for ix in range(5)]), "objective"
prob += pulp.lpSum(x)<=3, "capacity"

prob.solve()
for k, v in prob.variablesDict().iteritems():
    print k, v.value()

PuLP 很棒，带有非常不错的求解器 (CBC)，并且可以连接到开源和商业求解器。我目前正在为一家林业公司在生产中使用它，并探索 Dippy 来解决我们遇到的最难（整数）问题。祝你好运！

Scipy：具有稀疏矩阵的线性规划

Scipy: Linear programming with sparse matrices

python

scipy

sparse-matrix

linear-programming