Quicksum in constraint leads to too many nonzeros

Ongoing

Pieter Degeling

• December 05, 2023 13:56

Dear,

I want to model a power system in which the performance characteristics are affected by its usage through degradation. I am minimising fuel consumption over time [t].
I modelled the on/off status of the system using the big M method and a binary variable z[t].
When the system is on, z=1, and if it is off, z=0.
The degradation at timestep 1 is influenced by the status at timestep 0. The degradation at timestep 2 is the sum of degradation at timestep 0 and 1, etc.
The degradation is defined using the constraint:
condegtot = {}
for t in T:
      condegtot[t] = model.addConstr(deg[t] == quicksum(c*z[test-1]  for test in range(1,t+1)))

deg[t] then influences the available power at timestep t. This works well for small number of timesteps, but as the set for timesteps T increases problems occur. For 1000 timesteps, the number of nonzeros increases to more than 500,000; it is clear that the number of nonzeros increases quadratically with the range of set T.

Is there a way to simplify this constraint? Any help would be greatly appreciated.

Best regards,
Pieter

0

• 

  Eli Towle

  Gurobi Staff

  • December 05, 2023 15:05

  The degradation at timestep 2 is the sum of degradation at timestep 0 and 1, etc.

  Your constraints set the degradation equal to the sum of the weighted statuses at previous timesteps. Do you mean the degradation at timestep 2 is the sum of the weighted statuses (not degradations) at previous timesteps?

  If I understand your problem correctly, an equivalent, sparser formulation would set the degradation at time \( t \) equal to the degradation at time \( t - 1 \) plus \( c \) times the status at time \( t - 1\). I don't know exactly how you define your Python variables, but something like this should work:

  model.addConstr(deg[0] == 0)
  for t in T[1:]:
      model.addConstr(deg[t] == deg[t - 1] + c * z[t - 1])

   

  0
• 

  Pieter Degeling

  • December 05, 2023 16:04

  

  

  Hi Eli,
  
  Thanks so much for your quick response, it is really appreciated. I think this works perfectly!

  In this context, the coefficient c translates the on-off status to a degradation penalty. In my actual model, I defined various operations that lead to different degradation mechanisms. One of these is a penalty (degradation) for being on, described by c*z.
  The sum of degradation due to the various mechanisms leads to a degradation status for each timestep.
  In this example, the term 'sum of weighted statuses' is equal to the term 'total degradation'.
  
  Thanks again.

  Best regards,
  Pieter

  0

Please sign in to leave a comment.