Улучшение ограничений добавления производительности Gurobi Python - PullRequest
Новая
       18

Улучшение ограничений добавления производительности Gurobi Python

0 голосов
/ 18 марта 2019

У меня есть этот набор переменных решения 

for p in projects:
    for u in Skills:
        for v in Skills:
            for i in Experts:
                for j in Experts:
                    if u!=v:
                        if i >= j:
                            z[(i,u,j,v,p)]=m.addVar(vtype=GRB.BINARY,name='Z')
                            y[(i,u,j,v,p)]=m.addVar(vtype=GRB.BINARY,name='Y')

, и мне нужно добавить ограничения для каждого, как показано ниже 

#Constraint 6: To linearize the product of two decision variables linear  
#z_{i_u_p_j_v_p} <= V_i_u_p + V_i_u_p -1

for p in projects:
    for u in Skills:
        for v in Skills:
            for i in Experts:
                for j in Experts:
                    if u!=v:
                        if i >= j:
                            m.addConstr( z[i,u,j,v,p] <= Viup[i,u,p] )
                            m.addConstr( z[i,u,j,v,p] <= Viup[j,v,p] )
                            m.addConstr( z[i,u,j,v,p] >= Viup[i,u,p] + Viup[j,v,p] -1 )

m.update()

#Constraint 7:                           
for p1 in projects:
    for u1 in Skills:
        for v1 in Skills:
            for i1 in Experts:
                for j1 in Experts:
                    if u1!=v1:
                        if i1 >= j1:
                            m.addConstr( y[i1,u1,j1,v1,p1]  <= z[i1,u1,j1,v1,p1] )
                            m.addConstr( y[i1,u1,j1,v1,p1]  <= Wp[p1] )
                            m.addConstr( y[i1,u1,j1,v1,p1]  >= z[i1,u1,j1,v1,p1]+ Wp[p1] - 1 )

Это занимает огромное время, эксперты находятся в диапазоне (30) и навыки находятся в диапазоне (10).Может ли кто-нибудь помочь мне добавить их более эффективно?

1 Ответ

1 голос
/ 18 марта 2019

Не уверен, что вы можете уменьшить сложность, но вы можете сократить время внутренних циклов.

  • сначала сравните u != v на внешнем уровне, не выполняйте внутренние циклы, просто чтобы увидеть, что ничего не поделаешь
  • во-вторых, сортируйте свой список экспертов и не обрабатывайте 2 "половины", просто отбросьте половину итераций при сравнении.
  • затем кешируйте переменные условия, чтобы избежать их многократного вычисления

вот так (для последнего условия) 

sorted_experts = sorted(Experts)
for p1 in projects:
    for u1 in Skills:
        for v1 in Skills:
            if u1!=v1:  # do this check here
                for ei,i1 in enumerate(sorted_experts):
                   for ej in range(ei+1,len(sorted_experts)):
                        j1 = sorted_experts[ej]  # no need to test for indices
                        ycond = y[i1,u1,j1,v1,p1] # cache your condition variables
                        zcond = z[i1,u1,j1,v1,p1]
                        w = Wp[p1]
                        m.addConstr( ycond <= zcond )
                        m.addConstr( ycond <= w )
                        m.addConstr( ycond >= zcond + w - 1 )
...