constraints load too long
Answered# 参数
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
-
Official comment
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. -
now ,it runs over 10 min
0 -
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,
Matthias0 -
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 -
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,
Matthias0
Post is closed for comments.
Comments
5 comments