Speeding up Gurobi adding Constraint time

回答済み

Yen-Chun Liu

2024年03月12日 00:30 編集済み

• 
• 
• 

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

 

関連

• Model Building

0

• 正式なコメント

  

  Simranjit Kaur

  • Gurobi Staff

  2026年11月13日 01:28

  This post is more than two years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum, or try Gurobot, our chatbot interface offering instant, expert-level support.
• 

  Michel Soares

  2024年03月12日 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

  2024年03月13日 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

  2024年03月13日 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

投稿コメントは受け付けていません。