Efficient of defining decision variables

Answered

whwhwh55

• March 30, 2022 04:12

Hi, Gurobi team

I need to find a way of reducing decision variables. Here I need to define a binary decision variable called x_wjl. For worker index w, there are 428 values such as "worker 1", "worker 2" etc., For task index j, there are 431 values such as "Task 1", "Task 2".... For time slot index l, there are 2880 values for different times (such as 09/01/2021 0:00, 09/01/2021 0:15 etc.). If I simply use addVars to include the sets for w, j, and l, such as x= model.addVars(worker, task_t, time_slots, vtype  = GRB.BINARY),  there will be 428X431X2880 = 531 M variables for x_wjl. It seems to pose a huge computational challenge. But I realize many of these decisions do not happen since the time index l is related to task index j. I have a dictionary called ts[j] that lists the time slots l for each task j. If a task j1 does not happen at a time slot l1, then decision x_wj1l1 does not need to be defined. Though I can still define it and let x_wj1l1 = 0, it will generate many columns for the branch and bound and consumes a huge amount of memory beyond my computing workstation. 

Is there a way of defining decisions more efficiently? I am thinking of a way to define the decision variable adaptively. For example, if task j1 can happen only at time slots l1, l2, l3, then I will only define x_wj1l1, x_wj1l2, x_wj1l3 and do not have to define a huge amount of unnecessary decision variables for x_wj1l4, x_wj1l5... x_wj1l2880. If task j2 only happens at time slots l2, l3, then I just define x_wj2l2, x_wj2l3, no need to define x_wj2l1, x_wj2l4... xwj2l2880. Again, the relationship between tasks j and time slot l has already been defined in a dictionary ts_j[j] which gives a list of time slots for l corresponding for task j. I hope this way will reduce a lot of decision variables.

Thank you very much!

0

• 

  Jaromił Najman

  Gurobi Staff

  • March 30, 2022 09:46
  • Edited

  You can provide a list of tuples holding all indices of interest to the addVars method instead of just all possible combinations. For example

  import gurobipy as gp
  from gurobipy import GRB
  
  m = gp.Model()
  
  I = [1,2,3]
  J = [1,2,3,4]
  K = [1,2,3,4,5]
  
  x = m.addVars(I,J,K) # defines I x J x K = 3 * 4 * 5 variables
  # define indices of interest
  indices = [(1,2,3),(1,3,4),(2,1,5),(3,4,2),(3,1,5)]
  y = m.addVars(indices, name="y") # defines only 5 variables of interest
  m.update()
  
  for i in indices:
    print(y[i]) # access y variables via tuples defined in indices list
  
  # Console output:
  # <gurobi.Var y[1,2,3]>
  # <gurobi.Var y[1,3,4]>
  # <gurobi.Var y[2,1,5]>
  # <gurobi.Var y[3,4,2]>
  # <gurobi.Var y[3,1,5]>

  The hard part which is up to you is to efficiently construct the indices list. This should be possible, given the fact, that you have the \(\texttt{ts_j}\) dictionary.

  Best regards, 
  Jaromił

  0
• 

  whwhwh55

  • March 30, 2022 12:37

  

  

  

  Thank you very much for the prompt reply. This seems to be a very good approach. I will try. Sometimes I don’t have the right keywords searching for the answers. I hope these examples may be present somewhere in the online help or documentation.

  0

Please sign in to leave a comment.