Why does it take so long to build the objective?

Answered

Florian Götz

• March 30, 2023 06:48
• Edited

Hi,

below you find a toy example of the problem I'm working with. If you increase the number of rows and columns to say 8000 and 70 (the real problems are even larger) respectively, the code tends to perform very slowly. I assume that this is due to my inefficient programming style. Could you please show me what best practices I should follow when constructing very large objective functions with many hundreds of thousands of quadratic and linear terms?

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

rows=8000
columns=70

np.random.seed(0)    
B=np.random.rand(rows,columns)*(-0.5) 
C=np.random.rand(columns)*100
   
model=gp.Model('model')
initialize_variables_start=time.time()
d=model.addVars(rows, columns,vtype=GRB.CONTINUOUS)
y=model.addVars(rows,columns,vtype=GRB.CONTINUOUS)
initialize_variables_end=time.time()
print('Time spent initializing the variables:',initialize_variables_end-initialize_variables_start)

build_constraints_start=time.time()
[[model.addConstr(d[i,k]<=5) for i in range(0,rows)] for k in range(0,columns)]
[[model.addConstr(y[i,n]<=4) for i in range(0,rows)] for n in range(0,columns)]
build_constraints_end=time.time()
print('Time spent building the constraints:',build_constraints_end-build_constraints_start)
model.update()
model.Params.LogToConsole = 0

obj=0
build_obj_start=time.time()
for i in range(0,len(B)):
    
    quadratic_terms=np.array([0.5*B[i,k]*d[i,k]**2 for k in range(0,columns)]).flatten()
    some_linear_terms=np.array([C[n]* y[i,n] for n in range(0,columns)]).flatten()    
    obj=obj+gp.quicksum(np.array([*quadratic_terms,*some_linear_terms]))
    
model.setObjective(obj, GRB.MAXIMIZE)   
build_obj_end=time.time()
print('Time duration building the objective:',build_obj_end-build_obj_start)

solve_start=time.time()
model.optimize() 
solve_end=time.time()
print('Solving time',solve_end-solve_start)

 

Time spent initializing the variables: 3.8894851207733154
Time spent building the constraints: 16.81585383415222
Time duration building the objective: 42.72946310043335
Solving time 0.5733067989349365

 

Related to

• Performance
• Python

0

• 

  Jonasz Staszek

  Community Moderator

  • March 30, 2023 12:13

  

  

  

  Dear Florian,

  you seem to be using numpy arrays to come up with an objective statement, which is - in your case - a Gurobi QuadExpr. I would invite you to explore that section and to build your \( obj \) object based on the methods described there. One could hope for an improvement in performance this way.

  Hope this helps.

  Best regards
  Jonasz

   

  0
• 

  David Torres Sanchez

  Gurobi Staff

  • March 30, 2023 15:44

  Hi Florian,
  
  You can also use the MVars and friends.
  For example, the following gives the same formulation (I think) and the total building time goes down to just under 12s. I think there must be a faster way but I am not a Matrix API whizz.
  
  

  d = model.addMVar((rows, columns), vtype=GRB.CONTINUOUS, ub=5)
  y = model.addMVar((rows, columns), vtype=GRB.CONTINUOUS, ub=4)
  model.setObjective(gp.quicksum(gp.quicksum(0.5 * B * d**2 + C * y)), GRB.MAXIMIZE)

   

  Cheers, 
  David

  0
• 

  Florian Götz

  • March 31, 2023 08:06

  

  

  

  Hi all,

  thank you for pointing out the documentation of "QuadExpr". Especially the QuadExpr.addTerms() function has enormously sped up the construction of the target function.

  I don't need the matrix API because I construct the variables and constraints only once and sometimes redefine the objective function. For clarity, I have neglected this aspect from the toy example.

  Best regards,

  Florian

  0

Please sign in to leave a comment.