PySCIPOpt的慢性能

Question

我在PySCIPOpt中解决了一个IP问题，在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约为17秒，朱莉娅约为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()