constraints load too long

回答済み

崇林 潘

• 2024年09月19日 08:55

# 参数
num_experts = 125
num_works = 3000
L = 0
U = 5

# 初始化模型
m = gp.Model("CrossAssignment")

# 定义决策变量
x = m.addVars(num_works, num_experts, vtype=GRB.BINARY, name="x")
z = m.addVars(num_experts, num_experts, vtype=GRB.BINARY, name="z")

# 线性化约束
for i in range(num_experts):
    for k in range(num_experts):
        if i != k:
            m.addConstr(z[i, k] == gp.quicksum(x[j, i] * x[j, k] for j in range(num_works)))

# 范围约束
for i in range(num_experts):
    m.addConstr(gp.quicksum(z[i, k] for k in range(num_experts) if k != i) >= L)
    m.addConstr(gp.quicksum(z[i, k] for k in range(num_experts) if k != i) <= U)

this constr has run over 5min ,please give some advice to make it more fast

関連するエンティティ

• Matrix API
• Model Building

1

• 

  崇林 潘

  • 2024年09月19日 08:56

  

  

  now ,it runs over 10 min

  0
• 

  Matthias Miltenberger

  Gurobi Staff

  • 2024年09月19日 09:39

  Hi!

  The problematic part of this model is this:

  for i in range(num_experts):
      for k in range(num_experts):
          if i != k:
              m.addConstr(z[i, k] == gp.quicksum(x[j, i] * x[j, k] for j in range(num_works)))

  You are constructing 125*124=15 500 constraints, each with 3000 quadratic terms. In total, you are generating 46 500 000 quadratic terms. This is going to take a while and then it will be hopeless to solve such a model.

  You need to reformulate your model and come up with a different approach that does not need to explicitly contain all those constraints.

  Cheers,
  Matthias

  0
• 

  崇林 潘

  • 2024年09月19日 11:23
  • 編集済み

  

  

  My plan is make it to linear constrains.But,it isn't become better,please  help me.
  
  

  # 线性化约束 z[i,k] = sum(x[i,j] * x[k,j] for j in range(num_works))
  for i in range(num_experts):
      for k in range(num_experts):
          if i != k:  # 仅在 i != k 的情况下定义约束
              for j in range(num_works):
                  m.addConstr(z[i, k] <= x[i,j] )
                  m.addConstr(z[i, k] <= x[k,j] )
                  m.addConstr(z[i, k] >= x[i,j] + x[k,j] - 1 )
              # 对每个 i, k 定义 z[i, k] 表示共同评审的作品数量
              # 我们可以直接定义 z[i, k] 为 x[i,j] 和 x[k,j] 的乘积的和
              # m.addConstr(z[i, k] == gp.quicksum(x[i, j] * x[k, j] for j in range(num_works)))

   

  0
• 

  Matthias Miltenberger

  Gurobi Staff

  • 2024年09月19日 18:40
  • 編集済み

  You can use our matrix-friendly API to get rid of most of the overhead when building these constraints:

  x = m.addMVar((num_works, num_experts), vtype=GRB.BINARY, name="x")
  z = m.addMVar((num_experts, num_experts), vtype=GRB.BINARY, name="z")
  
  for i in range(num_experts):
      for k in range(num_experts):
          if i != k:
              m.addConstr(z[i, k] == x[:, i] @ x[:, k])

  With this update, the model is built within a few seconds. I should have suggested this method right in the beginning.

  Cheers,
  Matthias

  0

サインインしてコメントを残してください。