Quicksum: bound is a variable

Answered

Peter Joon

• August 25, 2020 11:12
• Edited

In a Resource Constrained (Multi) Project Scheduling Problem, I want to model jobs as part of projects with variable processing times. Projects consist of 5 jobs, of which two are dummy having variable processing times depending on the start times of the other jobs (Starting times of jobs are decision variables). 

Now if I do this, I run into trouble if I want to model my resource availability constraint, where I take the sum over the job processing times. Gurobi presents me with NotImplementedError if I add the following constraint: 

con2_2 = {}
    for t in T:
        for k in K:
             con2_2[t,k] = model.addConstr(gp.quicksum(r_ijk[i,j,k]*x[i,j,y] 
for i in I for j in range(3) for y in range(t, min(time[-1], t + P_dummy[i,0] ))) 
                      <= 
             float(RA_kt[k,t]) , name = 'Resource_Req_dum[' +str(k)+ ',' +str(t)+ ']')

Where r_ijk are the resources k used by job j of project i, x_ijt are the starting time DVs and the dummy jobs are the fourth and fifth jobs of the job list J. P_dummy[i,0] is the processing time (variable) of dummy 1  and this all needs to be less than or equal to the RA -> resource availability. 

This is how the general constrained looks mathematically:

Is there a way of programming this in Gurobi with the dummy job processing time as a variable and taking the sum over this to make sure we take the resource usage during that time into account?

Thank you very much for your help!

Addition: 
After altering the constraint to:

con2 = {}
 for t in T:
  for k in K:
   con2[t,k] = model.addConstr(gp.quicksum(r_ijk[i,j,k]*x[i,j,y] 
     for i in I for j in range(len(Jobs)-2) for y in range(t , min(time[-1], int(t + P_ij[i,j]) ))) 
     + gp.quicksum(r_ijk[i,j,k]*x[i,j,y] 
     for i in I for j in range(3,5) for y in range(t , t + P_dummy[i,j-2] )) 
     <= 
     RA_kt[k,t] , name = 'Resource_Req[' +str(k)+ ',' +str(t)+ ']')

I get an error:

TypeError: 'gurobipy.LinExpr' object cannot be interpreted as an integer

Where it refers to the 3rd to last line: y in range(t , t + P_dummy[i,j-2] )

And if I add int() around P_dummy I get:

TypeError: int() argument must be a string, a bytes-like object or a number, not 'Var'

0

• 

  Jaromił Najman

  Gurobi Staff

  • August 25, 2020 13:09
  • Edited

  Hi,

  I will make the modeling problem slightly easier to better explain how you can reformulate your model. An equivalent explanation can be found here.

  If I understand correctly you would like to model some constraint \(\sum_{i=1}^p x_i = 0\), where \(x_i\) and \(p\) are variables.
  First, let's assume that you have a valid upper bound on the integer variable \(p\) called \(p^U\) and that \(x_i \in [x^L,x^U]\) are continuous variables.

  We introduce binary variables \(z_i\) and replace the above sum by  \(\sum_{i=1}^p x_i \cdot z_i = 0\). The bilinear terms can be linearized by the introduction of auxiliary variables \(v_i\) and the constraints \(x^L\cdot z_i \leq v_i \leq x^U \cdot z_i\) and \(x^L\cdot (1-z_i) \leq x_i - v_i \leq x^U\cdot (1-z_i)\). Meaning that ultimately we get \(\sum_{i=1}^p v_i = 0\). Now, we take care of the index part.
  
  What we want to achieve is that if \(i \geq p+1\) then \(z_i = 0\) and if \(i \leq p\) then \(z_i=1\). This can be achieved by the addition of the constraints \(i \geq p+1 - z_i \cdot p^U\) and \(i \leq p + (1-z_i)\cdot p^U\).

  I think that with the above you are able to reformulate your problem accordingly. Please note that this may result in a lot of additional variables, making your problem even more complex than it already is. Thus, I would recommend to try to find a different formulation where a variable does not have to be used as an index.

  Best regards,
  Jaromił

  0
• 

  Peter Joon

  • August 28, 2020 13:59

  

  

  

  Hi Jaromił,

  Thank you for your consideration! I took your last advice to consider a different formulation, I will explain my steps below in case it may help anybody.
  
  What I have now and what works is using a tracker variable which substitutes my earlier idea of adding dummy jobs. This tracker variable is binary and takes the value 1 if we are between regular jobs and zero otherwise, furthermore the sum over the time of the tracker variable needs to be regulated to make sure the tracker is filled with ones in the gap between regular jobs.

  What this than gives is a more simple consideration in the resource usage constraint where we keep the constraint for regular jobs as I described but add for the tracker variables the sum over all tasks (i) of the trackers multiplied by the resource usage the dummy jobs had and check this constraint for each timestep t. 
  
  This fixes the variable index in the sum and I believe that there is limited extra complexity in terms of added variables as you remove the dummy start time and duration variables. Furthermore in terms of additional code I found that this does not significantly change compared to using dummy jobs. 
  
  Feel free to reach out if you want to now more about the exact code used.
  
  Kind regards,
  Peter

  0

Please sign in to leave a comment.