Speeding up Gurobi adding Constraint time
AnsweredHi,
I am trying to find N mxm binary matrices whose pairwise hamming distances are all greater than a given number C. However, it takes so long to add all the pairwise distance constraints (N*(N1)/2 constraints) when building the model (when m=30, N=50, it takes ~4644.3 sec).
I suspect the reason to be the way I calculate distance. Currently I use calculate the distance by trace(B_iB_j^\top)/m, where B_i, B_j are any two of the N binary matrices. I've also tried to calculate the absolute distance between matrices by introducing more auxiliary variables, but that attempt is even slower.
Is there any way to speed this up? Thanks a lot!
g = gu.Model()
g.params.SolutionLimit = 5
g.params.TimeLimit = 10
x = g.addMVar((N, q, m), vtype=GRB.BINARY, name="x")
g.setObjective(1, GRB.MAXIMIZE)
## Constraints
cstr_start = time.time()
for i in range(N):
for j in range(q):
g.addConstr(gu.quicksum(x[i, j, k] for k in range(m)) == 1, name = "sum_to_one" + str(i) + str(j))
for k in range(m):
g.addConstr(gu.quicksum(x[i, j, k] for j in range(q)) == 1, name = "sum_to_one" + str(i) + str(j))
cstr_middle = time.time()
for i in range(N1):
for k in range(i+1, N):
g.addConstr(gu.quicksum((x[i,:,:] @ x[k,:,:].T)[s,s] for s in range(q)) <= q*(1C), name = "dist"+str(i)+str(k))
cstr_end = time.time()
g.optimize()

Hi,
Take a look at addMConstr, in which you can add a matrix constraint. It should speed up your model building.
0 
Thank you for the reply. However I am confused  I have N(N1)/2 1dim constraint, each constraint resulting from the restriction of minimum distant between any (i,j), 1<=i<j<=N, pair of binary matrices. How can we reformulate it into a matrix constraint?
0 
ah! I fixed it by writing:
It's much faster now! Thansfor i in range(N1): for k in range(i+1, N): g.addConstr(gu.quicksum((x[i,s,:] @ x[k,s,:].T) for s in range(q)) <= q*(1C), name = "dist"+str(i)+str(k))
0
Please sign in to leave a comment.
Comments
3 comments