Improve constraint adding performance Gurobi python

Question

I have this set of decision variables

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

and I need to add constraints for each like below

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

This is taking huge time, Experts are in range(30) and skills are in range (10). Can someone help me add them more efficiently?

you could avoid to loop just to eliminate the "upper triangle" of experts. Then assign variables to your condition data to avoid repeated fetches. — Jean-François Fabre
– Jean-François Fabre ♦, Commented Mar 18, 2019 at 16:30
@Jean-FrançoisFabre Thanks for your quick response, but I couldn't understand clearly what you meant. Could you help more — Sagarika Khandelwal
– Sagarika Khandelwal, Commented Mar 18, 2019 at 16:40
Unless you are using a very old version of Gurobi, you should remove the call to Model.update(). — Greg Glockner
– Greg Glockner, Commented Mar 18, 2019 at 17:48

Jean-François Fabre · Accepted Answer · 2019-03-18 19:14:21Z

1

Not sure if you can reduce the complexity but you can reduce the time of the inner loops.

first, compare u != v at an outer level, don't perform inner loops just to see that there's nothing do do
second, sort your expert list, and don't process the 2 "halves", just to drop half of the iterations with a comparison.
then, cache your condition variables to avoid computing them many times

like this (for the last condition)

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 )

edited Mar 18, 2019 at 19:14

answered Mar 18, 2019 at 17:19

Jean-François Fabre♦

141k24 gold badges179 silver badges246 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Greg Glockner Over a year ago

Why not do this iteration once when you create the dictionaries y and z, then do the subsequent iteration over the keys of z?

Jean-François Fabre Over a year ago

but the keys of y and z depend on all 4 loop variables.

Collectives™ on Stack Overflow

Improve constraint adding performance Gurobi python

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related