How to create a tupledict of linear expressions?

Answered

Daniel Martin Baquero Guerrero

• February 23, 2022 15:59

I have the following variable that’s indexed by three sets:

x = m.addVars(C,D,T,vtype= GRB.INTEGER, name="X")

Before adding the constraints on x first I need to multiply each “x” to all elements of a matrix. This matrix is indexed by different sets, so the result is a new matrix. This parameter is a tupledict called A and is indexed by [D,T,J,I]. After multiplying both I get what essentially is a linear expression called “Disp” indexed by [C,J,I]. I implemented this by declaring a new variable as:

disp = m.addVars(C,J,I, name="disp ")

And then adding the linking constraint as:

for c in C:
    for d in D:
        for t in T:
            m.addConstr(disp[c,d,t] == sum(x[c,j,i]*A[j,i,d,t] for j in J for i in I))

After this, there are new constraints imposed on “disp”, for example:

m.addConstrs(disp[c,d,t] >= D[c,d,t] for c in C for d in D for t in T)

There are also constraints impose directly on “x”.

I’m concerned that declaring “disp” as a variable is harming the performance of the model by introducing what essentially is a linear expression of “x” as a variable. So, I have two questions:

Is my concern right? Am I hurting the performance by adding this “dummy” variables?

How could I define “disp” as a linear expression to avoid introducing it as a variable?

0

• 

  Matthias Miltenberger

  Gurobi Staff

  • February 24, 2022 14:26

  Hi Daniel,

  I cannot see an obvious flaw in your formulation, but I also don't know what you are trying to model.

  I strongly recommend writing out the LP file after constructing the model to check and verify that this actually corresponds to your mathematical formulation.

  Concerning the performance: You should inspect the presolving section when optimizing this model. Gurobi may reduce the model size on its own, so you should first check whether the performance is acceptable. Then, you can still try improving the formulation.

  Cheers,
  Matthias

  0
• 

  Daniel Martin Baquero Guerrero

  • February 24, 2022 18:39

  

  

  

  Dear Matthias,

   

  I’m modelling a time assignment (scheduling) model. The variable x is indexed by the position, the day, and time of the start of the shift. X represent the amount of people of the position (c) that start their shift at time and day (t,d). This people would only be available in certain time windows. The A matrices are binary matrices with 1’s in time window (i,j) when shift (t,d) is available and 0 otherwise. As there are overlaps between shifts and time windows the total available workers for position (c), in time window (i,j) is disp[c,t,d]:

  sum(x[c,j,i]*A[j,i,d,t] for j in J for i in I)

  The model is right, when checking the LP file everything is working as expected. My concern was about performance as in competing solvers the time the model takes to converge is lower.

   

  Kind regards,

  Daniel M. Baquero

  0
• 

  Matthias Miltenberger

  Gurobi Staff

  • February 25, 2022 11:35

  Hi Daniel,

  It's good to hear that your formulation appears to be correct. How do you construct the model for other solvers to get a better performance? Maybe you could write out the MPS file and feed this into Gurobi to have a better performance comparison.

  Best regards,
  Matthias

  0
• 

  Daniel Martin Baquero Guerrero

  • February 25, 2022 12:52

  

  

  

  Hi Matthias,

  I used the same MPS file in the other solvers to compare the performance. I'm already post a service request to compare the performance and other staff member is working with me.

  Thank you

  0

Please sign in to leave a comment.