Gurobi/python의 희소 행렬 LP 문제

Question

Gurobi/python에서 희소 행렬을 사용하여 표현 된 LP 문제를 해결하려고합니다. X = B 대상

최대 ′ C, X, L, X ≤ ≤ U, A는 크기가 2 ~ 1,000 의 SciPy linked list sparse matrix이다

. Gurobi/매트랩 같은 작업에 비해 10 ~ 100 배 느린 코드

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 초, ~를 사용. 문제 정의의 효율성을 개선하기위한 제안 사항이나 sparse coordinate 형식으로의 변환을 피하기위한 제안 사항이 있습니까?

Answer 1

스파 스 매트릭스를 처리 할 때 MATLAB은 항상 scipy보다 더 효율적입니다. 그러나 속도를 높이려는 시도가 몇 가지 있습니다.

구로비의 파이썬 인터페이스는 개별 스파 스 제약을받습니다. 즉, 좌표 형식이 아닌 압축 된 스파 스 행 형식으로 행렬에 액세스하려고합니다. 일을

시도 :

S = S.tocsr() 

직접 압축 스파 스 열 형식으로 행렬을 구성.

이 page은 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() 생성자를 사용하여 다음과 같이 그래서 당신은 이러한 반복 할 수 있어야한다.