Skip to main content

LinExpr() as a faster alternative to quicksum() for constraint building?

Answered
Nitin Singh
  • Gurobi-versary
  • Conversationalist
  • First Question

I have defined sets of constraints using model.addConstrs(), quicksum and generator expression. As an example, take a look at below. 

model.addConstrs(
        (
            gp.quicksum(
                x[c1, c2]
                for (c1, c2) in d[(s1, s2)]["trips"]
            )
            <= d[(s1, s2)]["upper_bound"]
            for s1, s2 in d
        )
    )

 

So, essentially I have a dictionary d, whose keys are tuples (s1, s2). For every tuple, the values are multiple lists of [c1, c2] (say 10 lists for example). I use these lists to pick certain indexes of x over which I take a sum. The sum has to be less than ["upper_bound"]. 

I have plenty of such constraints in my model. I read in a post (here) that gp.LinExpr() may be a faster alternative to quicksum(). I would like to test this hypothesis in my code. I am new to Gurobipy API. Could someone suggest me a way to implement LinExpr() in here if possible. 

Also, as I mentioned I have multiple such constraints i.e multiple dictionaries d_1, d_2 .... which I pre-prepared for my requirement for building constraints. 
Could there be a faster alternative to this as well?

Best Regards,

Related to

0

Comments

6 comments

Date Votes
  • Nitin Singh
    Edited
    • Gurobi-versary
    • Conversationalist
    • First Question

    Comment:
    I attempted to use gp.LinExpr(). Is my below prototype correct?

    model.addConstrs(
        (
            gp.LinExpr(
                (1.0, x[c1, c2])
                for (c1, c2) in d[(s1, s2)]["trips"]
            )
            <= d[(s1, s2)]["upper_bound"]
            for s1, s2 in d
        )
    )

    I believe it is, as I got the code running and achieved the same model stats/obj func val. 
    However, despite this the model generation time was not noticeably changed. 

    0
  • Silke Horn
    • Gurobi Staff

    Yes, the code looks correct. The LinExpr constructor should be the fastest way to build these expressions. However, you will only see a noticeable difference for very large expressions (hundreds of terms).

    How long is your model building time? If it is slow, have you already profiled it?

    You can use cProfile to find out how much time is spent in which function. This should help you narrow down which part of your code you should focus on improving.

    1
  • Carsten Moldenhauer
    • Gurobi-versary
    • First Comment

    I found this discussion by searching via google for LinExpr versus Quicksum. If you don't mind I'll join the discussion.

    I think the LinExpr is quicker than quicksum is somewhat of a myth (notabene: I have changed all quicksums in my models to LinExpr but did not find any time improvements). A quick test seems to confirm this:

    import gurobipy
import timeit
m = gurobipy.Model("test")
x = m.addVar(vtype="B")
y = m.addVar(vtype="B")
r = 10000

v = [x,y]*r
timeit.timeit(lambda: gurobipy.quicksum(v), number=r)
# 4.448191999999835

v = [(1.,x),(1.,y)]*r
timeit.timeit(lambda: gurobipy.LinExpr(v), number=r)
# 22.695031899998867

v = [x,y]*r
timeit.timeit(lambda: gurobipy.MVar.fromlist(v).sum(), number=r)
# 6.934492300000784

coeff = [1,1]*r
timeit.timeit(lambda: gurobipy.LinExpr(coeff, v), number=r)
# 22.459542099999453

coeff = [1.,1.]*r
timeit.timeit(lambda: gurobipy.LinExpr(coeff, v), number=r)
# 21.710751999999047
    0
  • Riley Clement
    • Gurobi Staff
    Edited

    Hi Carsten,

    I don't think it's a fair comparison when using the quicksum without considering the coefficients.

    import numpy as np
import timeit


setup = """
import gurobipy as gp
import numpy as np
import timeit
m = gp.Model("test")
x = m.addVar(vtype="B")
y = m.addVar(vtype="B")
r = 10000
v = [x,y]*r
v2 = [(1.,x),(2.,y)]*r
coeff = [1,2]*r
"""

statement1 = """
m.addConstr(gp.MVar.fromlist(v)@np.array(coeff) == 0)
"""

statement2 ="""
m.addLConstr(gp.LinExpr(v2), '=', 0)
"""

statement3 = """
m.addLConstr(gp.LinExpr(coeff, v), '=', 0)
"""

statement4 = """
m.addLConstr(gp.quicksum(coeff*var for coeff,var in zip(coeff,var)), '=', 0)
"""

times = np.array([
    np.min(timeit.repeat(stmt=statement1, setup=setup, number=1, repeat=2000)),
    np.min(timeit.repeat(stmt=statement2, setup=setup, number=1, repeat=2000)),
    np.min(timeit.repeat(stmt=statement3, setup=setup, number=1, repeat=2000)),
    np.min(timeit.repeat(stmt=statement4, setup=setup, number=1, repeat=2000)),
])

normalized = times/np.min(times)

    normalized = array([1. , 3.26099551, 3.32283396, 5.32196182])

    - Riley

     

    0
  • Carsten Moldenhauer
    • Gurobi-versary
    • First Comment

    So the takeaway is that quicksum is fastest, if there are no coefficients (meaning all coefficients are 1). And otherwise one should either use `LinExpr` or the hacky `gp.MVar.fromlist(v)@np.array(coeff)`. Does that make sense?

    0
  • Riley Clement
    • Gurobi Staff

    If there are no coefficients then `gp.MVar.fromlist(v)@np.ones(len(v))` will often be the fastest but it depends on the size of the data.  The “fixed cost” for using the Matrix API is much larger, but it scales better (which is why users should compare approaches with realistic usage for their models).

    Compare the following with r = 10000, then r = 1

    import numpy as np
import timeit


setup = """
import gurobipy as gp
import numpy as np
import timeit
m = gp.Model("test")
x = m.addVar(vtype="B")
y = m.addVar(vtype="B")
r = 10000
v = [x,y]*r
"""

statement1 = """
m.addConstr(gp.MVar.fromlist(v)@np.ones(len(v)) == 0)
"""

statement2 = """
m.addLConstr(gp.quicksum(v), '=', 0)
"""

times = np.array([
    np.min(timeit.repeat(stmt=statement1, setup=setup, number=1, repeat=2000)),
    np.min(timeit.repeat(stmt=statement2, setup=setup, number=1, repeat=2000)),
])

normalized = times/np.min(times)
print(normalized)

    - Riley

    0

Please sign in to leave a comment.

Didn't find what you were looking for?

New post