Gurobi/python中的稀疏矩阵LP问题 [英] sparse matrix LP problems in Gurobi / python

问题描述

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

I am trying to solve an LP problem represented using sparse matrices in Gurobi / python.

max c′ x，服从A x = b，L≤ x≤

max c′ x, subject to A x = b, L ≤ x ≤ U

其中A是SciPy 已链接列出大小为〜1000 ² 的稀疏矩阵.使用代码

where A is a SciPy linked list sparse matrix of size ~1000². Using the code

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倍.您是否对提高问题定义的效率有任何建议，或者对避免转换为

the problem is built and solved in ~1s, which is ~10-100 times slower than the same task in Gurobi / Matlab. Do you have any suggestions for improving the efficiency of the problem definition, or suggestions for avoiding translation to sparse coordinate format?

推荐答案

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

MATLAB will always be more efficient than scipy when dealing with sparse matrices. However, there are a few things you might try to speed things up.

Gurobi的Python接口采用单独的稀疏约束.这意味着您要以压缩的稀疏行格式(而不是坐标格式)访问矩阵.

Gurobi's Python interface takes individual sparse constraints. This means that you want to access your matrix in compressed sparse row format (rather than coordinate format).

尝试做:

   S = S.tocsr()

或直接以压缩的稀疏行格式构造矩阵.

or directly constructing your matrix in compressed sparse row format.

此页面表示您可以访问原始数据，索引以及来自CSR格式的稀疏稀疏矩阵的行指针.因此，您应该能够如下遍历这些内容:

This page indicates that you can access the raw data, indicies, and row pointers from a scipy sparse matrix in CSR format. So you should then be able to iterate over these as follows:

  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( )构造函数.

Note that I added all the terms at once into the expression using the LinExpr() constructor.

这篇关于Gurobi/python中的稀疏矩阵LP问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！