How to create a tupledict of linear expressions?

回答済み

Daniel Martin Baquero Guerrero

2022年02月23日 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

• 正式なコメント

  

  Simranjit Kaur

  • Gurobi Staff

  2025年11月16日 23:43

  This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum, or try Gurobot, our chatbot interface offering instant, expert-level support.
• 

  Matthias Miltenberger

  • Gurobi Staff

  2022年02月24日 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

  2022年02月24日 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

  2022年02月25日 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

  2022年02月25日 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

投稿コメントは受け付けていません。