Lenteur de performance de PySCIPOpt

Question

J'ai résolu un problème d'IP dans PySCIPOpt et j'ai également résolu le même problème dans Julia et j'ai trouvé que le temps de solution était étonnamment différent. Julia a résolu le problème en 25 secondes en utilisant Cbc tandis que PySCIPOpt a pris 198 secondes en utilisant le solveur intégré. Lors de l'exécution de la ligne de code par ligne, j'ai constaté que la plupart du temps, on passait la partie de la formulation du problème dans PySCIPOpt par rapport à la résolution réelle. Je me demandais si cela était prévu ou s'il y avait des méthodes pour rendre cela plus efficace (ou comparable à la performance de Julia).

Éditer: Voici la formulation que j'ai.

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

Il s'avère que l'exploitation de la parcimonie de la matrice A accélère la construction du modèle. L'édition suivante du code l'a fait fonctionner beaucoup plus rapidement.

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

Ajouté: Voici le code de Julia pour la référence. La comparaison du temps de résolution est d'environ 17 secondes pour PySCIPOpt et d'environ 22 secondes pour Julia.

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