Skip to main content

How to write a more efficient code?

Answered
Daniele De Santis
  • Gurobi-versary
  • First Comment
  • First Question

Hi guys,

I want to write the following family of constraints using this code. The cardinality of sets K, D, T is respectively 31, 7, 65 so I am trying to initializate more or less 14k constraints. 

Using gurobipy this process is too slow. With other optimization sofware I am able to initialized them in about a minute.

I want to ask you if there is a more efficient way to write the code. 

Thank you in advance for the answers!

0

Comments

6 comments

Date Votes
  • Official comment
    Simranjit Kaur
    • Gurobi Staff
    Edited
    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

    Hi Daniele,

    You did not state if the variables \(p,C,\Delta\) are scalar or actual optimization variables. In the following I assumed that they are some scalar values.

    The following code

    import gurobipy as gp
    from gurobipy import GRB
    import numpy as np
    import time

    m = gp.Model("test")

    K = [i for i in range(31)]
    D = [i for i in range(7)]
    T = [i for i in range(65)]
    I = [i for i in range(10)]
    J = [i for i in range(10)]

    x = m.addVars(I,J,K,name="x")

    p = np.random.rand(10,7,65)
    C = np.random.rand(31)
    delta = np.random.rand(31,7,65)

    start = time.time()
    m.addConstrs(gp.quicksum(p[i][d][k] * x[i,j,k] for i in I for j in J) <= C[k] + delta[k][d][t] for k in K for d in D for t in T)
    end = time.time()
    print("time needed:"+str(end - start))

    produced the output

    time needed:48.732858180999756

    If I change cast the \(\texttt{np.arrays}\) to lists via

    p = np.random.rand(10,7,65).tolist()
    C = np.random.rand(31).tolist()
    delta = np.random.rand(31,7,65).tolist()

    I get

    time needed:2.1701600551605225

    and the problem stays the same. Is this what you are looking for?

    Best regards,
    Jaromił

    1
  • Daniele De Santis
    • Gurobi-versary
    • First Comment
    • First Question

    First of all thank you for you answer Jaromil.

    You are right, I was not enough clear:

    1. Delta are integer non-negative optimization variables of cardinality 31*7*65
    2. x are binary optimization variables of cardinality 483*142*31
    3. Both p and C are scalars: the first one is a matrix of integer of size 483*7*65 and the second one is an array of integer of size 31

    I guess with this size the initialization becomes much slower.

    0
  • Jaromił Najman
    • Gurobi Staff

    Hi Daniele,

    I guess with this size the initialization becomes much slower.

    Yes, with these dimensions, the code becomes much slower.

    Could you tell which other software you used, where the generation took ~1 min? This might provide an intuition of how to re-write the code in a better way.

    Best regards,
    Jaromił

    0
  • Daniele De Santis
    • Gurobi-versary
    • First Comment
    • First Question

    Hi Jaromil,

    Thank you for your support!

    The software is Fico Xpress Solver with all the default settings.

    Kind regards,

    Daniele.

    0
  • Jaromił Najman
    • Gurobi Staff
    Edited

    Hi Daniele,

    Sorry for not getting back to you for so long. An alternative way to speed up the construction process would be to introduce auxiliary variables \(xs_{i,k}\) and the equality constraints

    \[\sum_j x_{i,j,k} = xs_{i,k} \quad \forall i \in I k \in K\]

    The code would be

    import gurobipy as gp
    import numpy as np
    import time

    dim_K = 31
    dim_D = 7
    dim_T = 65
    dim_I = 483
    dim_J = 142

    p = np.random.rand(dim_I, dim_D ,dim_T)
    C = np.random.rand(dim_K)

    m = gp.Model("test")

    x = m.addMVar((dim_I, dim_J, dim_K), vtype='B', name="x")
    xs = m.addMVar((dim_I, dim_K), vtype='I', name="xs") # auxiliary variables
    delta = m.addVars(dim_K, dim_D, dim_T, name="delta")

    startOverall = time.time()

    for i in range(dim_I):
      for k in range(dim_K):
        coef = [1.0] * dim_J
        xvar = x[i, :, k].tolist()
        coef.append(-1.0) # coefficient for xs
        xvar.extend(xs[i, k].tolist()) # add xs to the list
        m.addConstr(gp.LinExpr(coef, xvar) == 0.0) # sum_j x_ijk - xs_ik = 0 forall i,k

    for k in range(dim_K):
      for d in range(dim_D):
        for t in range(dim_T):
          coef = list(p[:, d, t])
          xvar = xs[:, k].tolist()
          coef.append(-1.0) # coefficient for delta
          xvar.append(delta[k, d, t]) # add delta to the list
          m.addConstr(gp.LinExpr(coef, xvar) <= C[k]) # sum_i p_idt xs_ik - Delta_kdt <= C_k

    endOverall = time.time()
    print("time needed: "+str(endOverall-startOverall))

    With the above code, the constraints are constructed in ~7 seconds on my personal notebook.

    Unfortunately, there is currently no convenient way of achieving good construction performance without the introduction of auxiliary variables. We are aware of this issue and added it to our future roadmap.

    Best regards,
    Jaromił

    0

Post is closed for comments.

Didn't find what you were looking for?

New post