sparse matrix LP problems in Gurobi / python

问题:

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

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

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()

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?

回答1:

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'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).

Try doing:

   S = S.tocsr()

or directly constructing your matrix in compressed sparse row format.

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()

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