PySCIPOpt的性能下降

Question

我在PySCIPOpt中解決了IP問題，並且在Julia解決了同樣的問題，並發現解決方案時間顯着不同。 Julia使用Cbc在25秒內解決了問題，而PySCIPOpt使用內置求解器花費了198秒。在逐行運行代碼時，我發現大部分時間都花在了PySCIPOpt中的問題表達部分，而實際上是在解決它。我想知道這是否是預期的事情，或者是否有一些方法可以使這種效率更高（或與Julia性能相當）。

編輯：下面是我有的表述。

model=Model("Route_Selection") 

start_time=time.clock() 
x={} 
for j in range(J): 
    x[j]=model.addVar(vtype = 'B', name = 'x (%s)' %j) 

y={} 
for i in range(I): 
    y[i]=model.addVar(vtype='C', name = 'y (%s)' %i) 

model.setObjective(quicksum(C[j]*x[j] for j in range(J))+ M* quicksum(y[i] for i in range(I)), "minimize") 

for i in range(I): 
    model.addCons(quicksum(A_mat[i,j]*x[j] for j in range(J))+y[i] ==1, name='coverage of (%s)' %i) 

model.addCons(quicksum(x[j] for j in range(J))<= N, name = 'vehicle constraint') 

model.optimize() 
print (time.clock()-start_time, "seconds") 

Answer 1

事實證明，利用矩陣A的稀疏性使得模型建立得更快。下面的代碼編輯使其運行得更快。

model=Model("Route_Selection") 

start_time=time.clock() 
x={} 
for j in range(J): 
    x[j]=model.addVar(vtype = 'B', name = 'x (%s)' %j) 

y={} 
for i in range(I): 
    y[i]=model.addVar(vtype='C', name = 'y (%s)' %i) 

model.setObjective(quicksum(C[j]*x[j] for j in range(J))+ M* quicksum(y[i] for i in range(I)), "minimize") 

from scipy.sparse import csr_matrix #added line 1 
B=csr_matrix(A_mat) #added line 2 

for i in range(I): 
    start=B.indptr[i] #added line 3 
    end=B.indptr[i+1] #added line 4 
    model.addCons(quicksum(x[j] for j in B.indices[start:end])+y[i] ==1, name='coverage of (%s)' %i) #edited line 5 

model.addCons(quicksum(x[j] for j in range(J))<= N, name = 'vehicle constraint') 

model.optimize() 
print (time.clock()-start_time, "seconds") 

補充：這裏是朱莉婭代碼的參考。 PySCIPOpt的求解時間比較約爲17secs，Julia約爲22秒。

tic() 
Routing=Model(solver=CbcSolver(logLevel=0)) 

#Variables 
@variable(Routing, X[j=1:J], Bin) 
@variable(Routing, Y[i=1:I], Bin) 

#Objective 
@objective(Routing, Min, sum(C[j]*X[j] for j=1:J)+sum(M*Y[i] for i=1:I)) 

#Constraints 
A=sparse(A_mat) 
@constraint(Routing, consRef[i=1:I], sum(A[i,j]*X[j] for j=1:J)+Y[i]==1) 
@constraint(Routing, sum(X[j] for j=1:J)<=N) 

solve(Routing) 
toc()