2

我正在尝试解决在 Gurobi / python 中使用稀疏矩阵表示的 LP 问题。

最大 c′ x, 服从 A x = b, L ≤ x ≤ U

其中 A 是大小为 ~1000 2的 SciPy链表稀疏矩阵。使用代码

model = gurobipy.Model()
rows, cols = len(b), len(c)
for j in range(cols):
    model.addVar(lb=L[j], ub=U[j], obj=c[j])
model.update()
vars = model.getVars()
S = scipy.sparse.coo_matrix(A)
expr, used = [], []
for i in range(rows):
    expr.append(gurobipy.LinExpr())
    used.append(False)
for i, j, s in zip(S.row, S.col, S.data):
    expr[i] += s*vars[j]
    used[i] = True
for i in range(rows):
    if used[i]:
        model.addConstr(lhs=expr[i], sense=gurobipy.GRB.EQUAL, rhs=b[i])
model.update()
model.ModelSense = -1
model.optimize()

该问题在约 1 秒内构建并解决，这比 Gurobi / Matlab 中的相同任务慢约 10-100 倍。你有什么提高问题定义效率的建议，或者避免翻译成稀疏坐标格式的建议吗？

4

1 回答 1

4

在处理稀疏矩阵时，MATLAB 总是比 scipy 更有效。但是，您可以尝试一些事情来加快速度。

Gurobi 的 Python 接口采用单独的稀疏约束。这意味着您希望以压缩的稀疏行格式（而不是坐标格式）访问您的矩阵。

尝试做：

   S = S.tocsr()

或直接以压缩稀疏行格式构建矩阵。

此页面表明您可以从 CSR 格式的 scipy 稀疏矩阵访问原始数据、索引和行指针。因此，您应该能够按如下方式迭代这些：

  model = gurobipy.Model()
  row, cols = len(b), len(c)
  x = []
  for j in xrange(cols):
      x.append(model.addVar(lb=L[j], ub=U[j], obj=c[j])
  model.update()

  # iterate over the rows of S adding each row into the model
  for i in xrange(rows):
      start = S.indptr[i]
      end   = S.indptr[i+1]
      variables = [x[j] for j in S.indices[start:end]]
      coeff     = S.data[start:end]
      expr = gurobipy.LinExpr(coeff, variables)
      model.addConstr(lhs=expr, sense=gurobipy.GRB.EQUAL, rhs=b[i])

   model.update()
   model.ModelSense = -1
   model.optimize()

请注意，我使用LinExpr()构造函数一次将所有项添加到表达式中。

于 2014-04-03T23:06:22.367 回答