Skip to main content

Improve performance of constraint-adding in Gurobi Python

Ongoing

Comments

2 comments

  • 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
    First Question
    First Comment

    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

Please sign in to leave a comment.

Powered by Zendesk