Speeding up Gurobi adding Constraint time

Answered

Yen-Chun Liu

• March 12, 2024 00:30
• Edited

Hi,

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*(N-1)/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(N-1):
    for k in range(i+1, N):
        g.addConstr(gu.quicksum((x[i,:,:] @ x[k,:,:].T)[s,s] for s in range(q)) <= q*(1-C), name = "dist"+str(i)+str(k))

cstr_end = time.time()
g.optimize()

 

Related to

• Model Building

0

• 

  Michel Soares

  • March 12, 2024 12:49

  

  

  Hi,

  Take a look at addMConstr, in which you can add a matrix constraint. It should speed up your model building.

  0
• 

  Yen-Chun Liu

  • March 13, 2024 00:09

  

  

  Thank you for the reply. However I am confused - I have N(N-1)/2 1-dim 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
• 

  Yen-Chun Liu

  • March 13, 2024 00:24

  

  

  ah! I fixed it by writing:
  
  It's much faster now! Thans

  for i in range(N-1):
      for k in range(i+1, N):
          g.addConstr(gu.quicksum((x[i,s,:] @ x[k,s,:].T) for s in range(q)) <= q*(1-C), name = "dist"+str(i)+str(k))
  

  0

Please sign in to leave a comment.