Gurobi/Python中的稀疏矩阵线性规划问题

Question

我正在尝试用稀疏矩阵在Gurobi和Python中解决一个线性规划（LP）问题。

这个问题可以表示为：最大化 c′ x，满足 A x = b，以及 L ≤ x ≤ U

其中，A是一个大小大约为1000x1000的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倍。你有什么建议可以提高问题定义的效率，或者有什么方法可以避免转换成稀疏坐标格式吗？

Answer 1

在处理稀疏矩阵时，MATLAB的效率总是比scipy高。不过，你可以尝试一些方法来加快速度。

Gurobi的Python接口可以处理单独的稀疏约束。这意味着你需要以压缩稀疏行格式来访问你的矩阵，而不是坐标格式。

你可以试试这样做：

   S = S.tocsr()

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

这个页面说明你可以从scipy的稀疏矩阵中以CSR格式访问原始数据、索引和行指针。因此，你应该可以像下面这样遍历这些数据：

  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()构造函数一次性把所有项添加到表达式中的。