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

补充：这是供参考的Julia代码。 PySCIPOpt 的求解时间比较约为 17 秒，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()

PySCIPOpt 性能缓慢

Slow performance of PySCIPOpt

scip