Improve performance of constraint-adding in Gurobi Python
Ongoing
In the model I am working on I have to add constraints, the constraints based on the edges of a graph, I have the decision variable
x = {}
for (i, j) in E:
x[i, j] = model.addVar(vtype=GRB.BINARY, name="x%d,%d," % (i, j))
then I have to constraints, for instance :
# Constraint 1
model.addConstrs((x[i, j] + x[j, i] <= 1 for (i, j) in E), name='first')
# Constraint 4
model.addConstrs(((quicksum(x[g, i] for g in range(initial, n + 1) if (g, i) in E and g != i and g != j)
+ quicksum(x[j, g] for g in range(initial, n + 1) if (j, g) in E and g != j and g != i)
) <= 2 for (i, j) in E)
, name='fourth')
now E is defined in this way :
E = gp.tuplelist([(0, 1), (5, 22), (15, 27), (29, 33), (9, 3), (29, 12), (29, 22), (8, 39),
(0, 2), (6, 14), (16, 19), (29, 34), (11, 3), (32, 12), (31, 22), (39, 8),
(0, 3), (6, 27), (16, 22), (29, 36), (12, 3), (15, 13), (33, 22), (9, 39),
(0, 9), (7, 9), (16, 24), (29, 37), (15, 3), (17, 13), (36, 22), (39, 9),
(0, 11), (7, 11), (16, 26), (30, 32), (22, 3), (22, 13), (37, 22), (10, 39)])
my problem is when E with a lot of edges it takes a lot of time to create the constraints, there is any way to add variables and constraints in a more efficient way?
0
-
Official comment
This post is more than three 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 why not try our AI Gurobot?. -
Hi,
The time issue is not reproducible. The value of the \(\texttt{initial}\) parameter is missing. Constraint 1 results in a Keyerror because \(\texttt{x[1,0]}\) is not present. Could you provide a minimal reproducible example (MRE) showing the build time issue?
Best regards,
Jaromił0 -
Hi Jaromil, this is just the smallest example I have, the time here is acceptable but when the graph has hundreds or thousands of nodes and edges it really takes a lot of time, there is any part that can be modified to avoid this?
Thanks alot
import gurobipy as gp
from gurobipy import GRB, quicksum
from collections import defaultdict
#############################################
initial = 0
n = 39
s = 39
E = gp.tuplelist([(0, 1), (6, 32), (14, 15), (28, 31), (30, 4), (32, 11), (31, 20), (39, 15),
(0, 12), (6, 33), (14, 16), (28, 32), (9, 5), (33, 11), (32, 20), (16, 39),
(0, 22), (6, 35), (14, 17), (28, 33), (11, 5), (34, 11), (34, 20), (39, 16),
(0, 2), (6, 36), (14, 18), (28, 34), (12, 5), (35, 11), (35, 20), (17, 39),
(0, 13), (6, 37), (14, 19), (28, 35), (14, 5), (36, 11), (23, 22), (39, 17),
(0, 3), (6, 38), (14, 20), (28, 36), (28, 5), (37, 11), (28, 25), (18, 39),
(0, 4), (7, 9), (14, 21), (28, 37), (9, 6), (38, 11), (28, 26), (39, 18),
(0, 5), (7, 11), (14, 24), (28, 38), (11, 6), (13, 12), (36, 26), (19, 39),
(0, 9), (7, 12), (14, 25), (29, 36), (12, 6), (14, 12), (28, 27), (39, 19),
(0, 11), (7, 14), (14, 26), (32, 37), (14, 6), (14, 13), (29, 28), (20, 39),
(1, 2), (7, 28), (14, 27), (35, 38), (28, 6), (24, 13), (30, 28), (39, 20),
(1, 3), (7, 35), (14, 29), (1, 0), (32, 6), (15, 14), (31, 28), (21, 39),
(1, 4), (7, 36), (14, 30), (12, 0), (33, 6), (16, 14), (32, 28), (39, 21),
(1, 5), (7, 37), (14, 31), (22, 0), (35, 6), (17, 14), (33, 28), (22, 39),
(1, 6), (8, 10), (14, 32), (2, 0), (36, 6), (18, 14), (34, 28), (39, 22),
(1, 7), (8, 23), (14, 33), (13, 0), (37, 6), (19, 14), (35, 28), (23, 39),
(1, 8), (9, 10), (14, 34), (3, 0), (38, 6), (20, 14), (36, 28), (39, 23),
(1, 9), (9, 12), (14, 35), (4, 0), (9, 7), (21, 14), (37, 28), (24, 39),
(1, 10), (9, 13), (14, 36), (5, 0), (11, 7), (24, 14), (38, 28), (39, 24),
(1, 11), (9, 14), (14, 37), (9, 0), (12, 7), (25, 14), (36, 29), (25, 39),
(2, 6), (9, 22), (14, 38), (11, 0), (14, 7), (26, 14), (37, 32), (39, 25),
(2, 7), (9, 23), (15, 16), (2, 1), (28, 7), (27, 14), (38, 35), (26, 39),
(2, 9), (9, 24), (15, 30), (3, 1), (35, 7), (29, 14), (0, 39), (39, 26),
(2, 11), (10, 21), (15, 31), (4, 1), (36, 7), (30, 14), (39, 0), (27, 39),
(2, 12), (11, 12), (15, 32), (5, 1), (37, 7), (31, 14), (1, 39), (39, 27),
(2, 13), (11, 13), (15, 33), (6, 1), (10, 8), (32, 14), (39, 1), (28, 39),
(2, 24), (11, 15), (15, 34), (7, 1), (23, 8), (33, 14), (2, 39), (39, 28),
(2, 25), (11, 16), (16, 17), (8, 1), (10, 9), (34, 14), (39, 2), (29, 39),
(2, 26), (11, 17), (16, 18), (9, 1), (12, 9), (35, 14), (3, 39), (39, 29),
(2, 27), (11, 18), (16, 19), (10, 1), (13, 9), (36, 14), (39, 3), (30, 39),
(2, 28), (11, 19), (16, 20), (11, 1), (14, 9), (37, 14), (4, 39), (39, 30),
(3, 9), (11, 20), (17, 29), (6, 2), (22, 9), (38, 14), (39, 4), (31, 39),
(3, 11), (11, 21), (17, 30), (7, 2), (23, 9), (16, 15), (5, 39), (39, 31),
(3, 12), (11, 22), (17, 31), (9, 2), (24, 9), (30, 15), (39, 5), (32, 39),
(3, 14), (11, 23), (17, 32), (11, 2), (21, 10), (31, 15), (6, 39), (39, 32),
(3, 29), (11, 24), (17, 33), (12, 2), (12, 11), (32, 15), (39, 6), (33, 39),
(4, 9), (11, 25), (17, 34), (13, 2), (13, 11), (33, 15), (7, 39), (39, 33),
(4, 11), (11, 26), (18, 29), (24, 2), (15, 11), (34, 15), (39, 7), (34, 39),
(4, 12), (11, 27), (18, 32), (25, 2), (16, 11), (17, 16), (8, 39), (39, 34),
(4, 14), (11, 29), (19, 21), (26, 2), (17, 11), (18, 16), (39, 8), (35, 39),
(4, 28), (11, 30), (20, 29), (27, 2), (18, 11), (19, 16), (9, 39), (39, 35),
(4, 29), (11, 31), (20, 30), (28, 2), (19, 11), (20, 16), (39, 9), (36, 39),
(4, 30), (11, 32), (20, 31), (9, 3), (20, 11), (29, 17), (10, 39), (39, 36),
(5, 9), (11, 33), (20, 32), (11, 3), (21, 11), (30, 17), (39, 10), (37, 39),
(5, 11), (11, 34), (20, 34), (12, 3), (22, 11), (31, 17), (11, 39), (39, 37),
(5, 12), (11, 35), (20, 35), (14, 3), (23, 11), (32, 17), (39, 11), (38, 39),
(5, 14), (11, 36), (22, 23), (29, 3), (24, 11), (33, 17), (12, 39), (39, 38),
(5, 28), (11, 37), (25, 28), (9, 4), (25, 11), (34, 17), (39, 12),
(6, 9), (11, 38), (26, 28), (11, 4), (26, 11), (29, 18), (13, 39),
(6, 11), (12, 13), (26, 36), (12, 4), (27, 11), (32, 18), (39, 13),
(6, 12), (12, 14), (27, 28), (14, 4), (29, 11), (21, 19), (14, 39),
(6, 14), (13, 14), (28, 29), (28, 4), (30, 11), (29, 20), (39, 14),
(6, 28), (13, 24), (28, 30), (29, 4), (31, 11), (30, 20), (15, 39)])
E = sorted(E)
#######################################################
try:
with gp.Model("sub_problem") as model:
y = {}
u = {}
for a in range(initial, n):
y[a] = model.addVar(lb=0, name="y%d" % a)
for b in range(initial, n + 1):
u[b] = model.addVar(lb=0, name="u%d" % b)
for (i, j) in E:
xH = defaultdict(lambda: 0, {(i, j): 0, })
xH[1, 0] = 1
xH[0, 39] = 1
xH[39, 1] = 1
# Constraint 1,2
for (i, j) in E:
if i != s and j != s:
model.addLConstr(y[i] >= xH[i, j], name='first%d,%d' % (i, j))
model.addLConstr(y[j] >= xH[i, j], name='second%d,%d' % (i, j))
# Constraint 3,4
for i in range(initial, n):
model.addLConstr(y[i] == quicksum(xH[i, j] for j in range(initial, n + 1) if (i, j) in E),
name='third%d' % i)
model.addLConstr(y[i] == quicksum(xH[j, i] for j in range(initial, n + 1) if (j, i) in E),
name='fourth%d' % i)
# Constraint 5
for (i, j) in E:
if j != s:
model.addLConstr(u[i] - u[j] <= (n * (1 - xH[i, j]) - 1), name='fifth%d,%d' % (i, j))
# Constraint 6
model.addLConstr(u[s] == 1, name='sixth')
# Set global sense for ALL objectives
model.ModelSense = GRB.MINIMIZE
# Set objective
model.setObjective(-1 * (quicksum(y[i] for i in range(initial, n))))
# Save model
model.write('SP2.lp')
finally:
gp.disposeDefaultEnv()
try:
with gp.Model("master_problem") as model:
Z = model.addVar(lb=-gp.GRB.INFINITY, name="Z")
x = {}
for (i, j) in E:
x[i, j] = model.addVar(vtype=GRB.BINARY, name="x%d,%d," % (i, j))
# Constraint 1
for (i, j) in E:
model.addLConstr(x[i, j] + x[j, i] <= 1, name='first%d,%d' % (i, j))
# Constraint 2
model.addLConstr(quicksum(x[s, v] for v in range(initial, n)) == 1, name='second')
# Constraint 3
model.addLConstr(quicksum(x[v, s] for v in range(initial, n)) == 1, name='third')
# Constraint 4
for (i, j) in E:
if i != s and j != s:
model.addLConstr(
(quicksum(x[g, i] for g in range(initial, n + 1) if (g, i) in E and g != i and g != j)
+quicksum(x[i, g] for g in range(initial, n + 1) if (i, g) in E and g != i and g != j)
+ quicksum(x[j, g] for g in range(initial, n + 1) if (j, g) in E and g != j and g != i)
+ quicksum(x[g, j] for g in range(initial, n + 1) if (g, j) in E and g != i and g != j))
<= 2
, name='fourth%d,%d' % (i, j))
# Constraint 5,6,7
for i in range(initial, n):
model.addLConstr((quicksum(x[i, j] for j in range(initial, n + 1) if (i, j) in E and i < j) <= 1),
name='fifth%d' % i)
model.addLConstr((quicksum(x[j, i] for j in range(initial, n + 1) if (j, i) in E and i < j) <= 1),
name='sixth%d' % i)
model.addLConstr((quicksum(x[j, i] for j in range(initial, n + 1) if (j, i) in E)) ==
(quicksum(x[i, j] for j in range(initial, n + 1) if (i, j) in E)), name='seventh%d' % i)
# Set global sense for ALL objectives
model.ModelSense = GRB.MINIMIZE
# Set objective
model.setObjective(Z)
# Save model
model.write('MP2.lp')
finally:
gp.disposeDefaultEnv()
########################################################
for (i, j) in E:
if i != s and j != s:
d = defaultdict(lambda: 0.0, {(1, i, j): 0.0, })
f = defaultdict(lambda: 0.0, {(1, i, j): 0.0, })
for v in range(initial, n):
p = defaultdict(lambda: 0.0, {(1, v): 0.0, })
m = defaultdict(lambda: 0.0, {(1, v): 0.0, })
for (i, j) in E:
if j != s:
l = defaultdict(lambda: 0.0, {(1, i, j): 0.0, })
t = defaultdict(lambda: 0.0, {1: 0.0, })
###################################################
SP_model2 = gp.read("SP2.lp")
MP_model2 = gp.read("MP2.lp")
SP_model2.setParam(GRB.Param.Presolve, 0)
SP_model2.setParam("InfUnbdInfo", 1)
SP_model2.optimize()
#####################################################
x_temp = MP_model2.getVars()
Z = x_temp[0]
x_temp.pop(0)
variables = sorted(x_temp, key=lambda x: (float(x.VarName.split(",")[0][1:]), float(x.VarName.split(",")[1])))
#######################################################
init = 0
for (a, b) in E:
x[a, b] = variables[init]
init += 1
##################################################
# k = 0
if SP_model2.status >= 3:
k = 1
for (i, j) in E:
if i != s and j != s:
d[k, i, j] = -1 * SP_model2.getConstrByName('first%d,%d' % (i, j)).FarkasDual
f[k, i, j] = -1 * SP_model2.getConstrByName('second%d,%d' % (i, j)).FarkasDual
for v in range(initial, n):
p[k, v] = -1 * SP_model2.getConstrByName('third%d' % v).FarkasDual
m[k, v] = -1 * SP_model2.getConstrByName('fourth%d' % v).FarkasDual
for (i, j) in E:
if j != s:
l[k, i, j] = -1 * SP_model2.getConstrByName('fifth%d,%d' % (i, j)).FarkasDual
t[k] = -1 * SP_model2.getConstrByName('sixth').FarkasDual
MP_model2.addConstr(0 >= (quicksum(x[i, j] * d[k, i, j] for (i, j) in E if i != s and j != s)
+ quicksum(x[i, j] * f[k, i, j] for (i, j) in E if i != s and j != s)
+ quicksum(x[i, j] * p[k, i] for (i, j) in E if i != s)
+ quicksum(x[j, i] * m[k, i] for (j, i) in E if i != s)
+ quicksum((n * (1 - x[i, j]) - 1) * l[k, i, j] for (i, j) in E if j != s)
+ t[k]), name='cut%d' % k)
MP_model2.write("MP2.lp")
else:
k = 1
for (i, j) in E:
if i != s and j != s:
d[k, i, j] = SP_model2.getConstrByName('first%d,%d' % (i, j)).Pi
f[k, i, j] = SP_model2.getConstrByName('second%d,%d' % (i, j)).Pi
for v in range(initial, n):
p[k, v] = SP_model2.getConstrByName('third%d' % v).Pi
m[k, v] = SP_model2.getConstrByName('fourth%d' % v).Pi
for (i, j) in E:
if j != s:
l[k, i, j] = SP_model2.getConstrByName('fifth%d,%d' % (i, j)).Pi
t[k] = SP_model2.getConstrByName('sixth').Pi
MP_model2.addConstr((quicksum(x[i, j] * d[k, i, j] for (i, j) in E if i != s and j != s)
+ quicksum(x[i, j] * f[k, i, j] for (i, j) in E if i != s and j != s)
+ quicksum(x[i, j] * p[k, i] for (i, j) in E if i != s)
+ quicksum(x[j, i] * m[k, i] for (j, i) in E if i != s)
+ quicksum((n * (1 - x[i, j]) - 1) * l[k, i, j] for (i, j) in E if j != s)
+ t[k]) <= Z, name='cut%d' % k)
MP_model2.write("MP2.lp")
MP_model2.setParam(GRB.Param.Presolve, 0)
MP_model2.optimize()
print("####################################")
print('The optimal objective SP is %g' % SP_model2.objVal)
print('The optimal objective MP is %g' % MP_model2.objVal)
print("####################################")
for (st, nd) in E:
if nd != s:
fifth = SP_model2.getConstrByName('fifth%d,%d' % (st, nd))
fifth.rhs = n * (1 - x[st, nd].X) - 1
for (st2, nd2) in E:
if st2 != s and nd2 != s:
first = SP_model2.getConstrByName('first%d,%d' % (st2, nd2))
second = SP_model2.getConstrByName('second%d,%d' % (st2, nd2))
first.rhs = x[st2, nd2].X
second.rhs = x[st2, nd2].X
for st3 in range(initial, n):
third = SP_model2.getConstrByName('third%d' % st3)
fourth = SP_model2.getConstrByName('fourth%d' % st3)
temp_x1 = 0
for nd3 in range(initial, n + 1):
if (st3, nd3) in E:
temp_x1 += x[st3, nd3].X
third.rhs = temp_x1
fourth.rhs = temp_x1
SP_model2.write("SP2.lp")
###########################################################0
Post is closed for comments.
Comments
3 comments