改善约束添加性能Gurobi python

Question

我有这套决策变量

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）。有人可以帮助我更有效地添加它们吗？

Answer 1

不确定是否可以降低复杂性，但可以减少内部循环的时间。

• 首先，在外层比较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 )