Skip to main content

Improve performance of constraint-adding in Gurobi Python

Ongoing

Comments

3 comments

  • Official comment
    Simranjit Kaur
    Gurobi Staff Gurobi Staff
    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?.
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    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
  • ahmad alanaqreh
    Gurobi-versary
    Conversationalist
    Investigator

    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.