Difference between nested quicksum and several quicksums
AnsweredHello,
I have a question about optimization effiency. I implement gurobi optimizer in Python. I wonder if model with nested quicksum would performs better that with parellel quicksums. I provide an example to decribe my question. Given my objective function is
would it better to construct it as
The corresponding codes are
model.setObjective(
quicksum(P[i] * x[i] for i in I) 
quicksum(C[i, j] * y[i, j] for i in I for j in J),
GRB.MAXIMUM
)
model.setObjective(
quicksum(
P[i] * x[i]  quicksum(
C[i, j] * y[i, j]
for j in J
)
for i in I
),
GRB.MAXIMUM
)
I have tried to analize the difference between the above two methods. The total number of iterations may be lower in the latter one. While I doubt if they are the same after processed and reconstructed by Gurobi optimizer. Besides, the above instance is simplified. I consider the complexity may impact the advatages or disadvatages in each way. Would the advantages keep consistant even in constraints?
I have another problem is regarding to the usage of quicksum
. May I assign the quicksum
value to a variable and use the variable in both addConstrs
and setObjectives
?
The code block below is a simple example. x
is decision variables. I
and P
are static parameters.
I = ["1", "2", "3"]
P = {"1": 2, "2": 2, "3": 4}
model = Model()
x = model.addVars(I, vtype=GRB.BINARY)
tmp_var = quicksum(P[i] * x[i] for i in I)
model.addConstr(tmp_var < 5)
model.setObjective(tmp_var, GRB.MAXIMUM)
I wonder whether creating a variable reference to the quicksum
object helps in efficiency.
Thanks a lot! I really appreciate your help.

Hi Trista,
You can check your thesis by writing a small script and checking the times
import gurobipy as gp
from gurobipy import GRB
import numpy as np
import time
I = 1000
J = 1000
P = np.random.rand(I)
C = np.random.rand(I,J)
m = gp.Model()
x = m.addVars(I)
y = m.addVars(I,J)
start = time.time()
m.setObjective(
gp.quicksum(P[i] * x[i] for i in range(I)) 
gp.quicksum(C[i, j] * y[i, j] for i in range(I) for j in range(J))
)
time_needed = time.time()  start
print("Time needed for 1st version: %f"%(time_needed))
start = time.time()
m.setObjective(
gp.quicksum(
P[i] * x[i]  gp.quicksum(
C[i, j] * y[i, j]
for j in range(J)
)
for i in range(I)
)
)
time_needed = time.time()  start
print("Time needed for 2nd version: %f"%(time_needed))You will notice that there is no much difference between the two versions. However, you can significantly improve model building speed with the following version
start = time.time()
lexpr = gp.LinExpr(0)
for i in range(I):
lexpr.add(x[i], P[i])
for j in range(J):
lexpr.add(y[i,j], C[i,j])
m.setObjective(lexpr)
time_needed = time.time()  start
print("Time needed for 3rd version: %f"%(time_needed))You can read more on efficient model building in How do I improve the time to build my model?
Would the advantages keep consistant even in constraints?
Yes, if the constraints are build in a similar way.
May I assign the
quicksum
value to a variable and use the variable in bothaddConstrs
andsetObjectives
?Yes. The quicksum function returns an expression object which can be reused in other expression objects.
Note that Gurobi does not support strict inequalities. Thus
model.addConstr(tmp_var < 5)
is not available in Gurobi, only \(\leq\). Moreover, it should be
model.setObjective(tmp_var, GRB.MAXIMIZE)
Best regards,
Jaromił0 
Hello Jaromił,
Thanks for your promt reply. I look into the links you provided and did some search concerning
LinExpr
,quicksum
,tupledict.sum
,add
,addTerms
.I tried different writing ways to solve the problem in network.py. Accoring to the same instance in it, I derive some observations.
addConstr
with for loop is faster thanaddConstrs
.quicksum
with for loop is faster than that withtupledict.select
ortupledict.sum
. I doubt that these observations are general enough and prove some universal prospositions.However, I encountered that
LinExpr
may not help in effiency in this instance. I wonder what is the factor to makeLinExpr
dominant. Is it the nested structure of the expression to bring the advantage? Besides, one math equation with some summation may be written inLinExpr
withadd
,addTerms
,quicksum
or+
. Which one would be the fastest? In another case, if the righthandside equation is only a product of two objects, is it still faster to useLinExpr
instead of*
ortupledict.prod
? Is it more ideal to construct a expression with equality or inequality sign to form a constraint or make the LHS and RHS respectively and use them inaddConstr
?I truely appreciate your kind response.
Best regards,
Trista
0 
Hi Trista,
Gurobi methods should be more efficient than the methods built into the data structures. Thus, it makes sense that quicksum is faster than .select or .sum. It is also true that addConstr in a forloop can be slightly faster than addConstrs in some cases.
Using LinExpr with addTerms should be fastest followed by add. However, there quicksum can outperform those in some cases. In general, the difference in speed between the 3 should not be too big. However, the difference in speed is significant if you would construct your linear expressions via the += and *= operators.
In another case, if the righthandside equation is only a product of two objects, is it still faster to use
LinExpr
instead of*
ortupledict.prod
?If the number of objects is small, then there should be no significant difference.
Is it more ideal to construct a expression with equality or inequality sign to form a constraint or make the LHS and RHS respectively and use them in
addConstr
?There should be no significant difference between those 2 options. I would recommend using the version which you find to be easier to read/understand.
In general, if model construction speed is crucial for your application, I would test different alternatives to find the best performing one for your particular model.
Best regards,
Jaromił0 
Hi
Thanks for your promt reply. I have another relative question. The screenshot below is captured from the official website document.
Could you please provide some examples of explicit constructors? I truely appreciate your time and help.
Best regards,
Trista
0 
Hi Trista,
What the documentation means is
For linear expressions of moderate size (only a few terms) and for the ease of usage, you should generally use overloaded operators instead of the explicit constructor to build linear expression objects.
An example of an explicit constructor usage would be
X = []
coeffs = []
for i in range(1,1001):
X.append(m.addVar( name="X%d"%(i)))
coeffs.append(i)
expr = gp.LinExpr(coeffs, X) # LinExpr constructor taking 2 lists
m.addConstr(expr <= 5)Best regards,
Jaromił0
Please sign in to leave a comment.
Comments
5 comments