Низкая производительность PySCIPOpt

Question

Я решил проблему с IP в PySCIPOpt, а также решил ту же проблему с Юлией и обнаружил, что время решения было разным. Юлия решила проблему за 25 секунд, используя Cbc, в то время как PySCIPOpt заняла 198 секунд, используя встроенный решатель. Выполняя код построчно, я обнаружил, что большую часть времени проводил в части формулировки проблемы в PySCIPOpt по сравнению с фактическим ее решением. Мне было интересно, если это что-то ожидается или есть какие-то методы, чтобы сделать это более эффективным (или сопоставимым с показателями Джулии).

Изменить: ниже формулировка, которую я имею.

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

Добавлено: вот код Джулии для справки. Сравнение времени решения составляет около 17 секунд для PySCIPOpt и около 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()