Efficiently model set up binary variables between start and end time variables

回答済み

Daniel

2023年05月23日 10:09 編集済み

• 
• 

Dear GUROBI Team,

I am struggling with the runtime of a task assignment/capacity planning model. I suspect it is due to an inefficient modelling of the following constraints:

 

Variables:

Set of periods p ∈ P

Set of resources r ∈ R which can be acquired or removed in each p

start_period[r]; start_binary[p, r], =1, if r is acquired in p

end_period[r]; end_binary[p, r], =1, if r is removed in p

is_available[p, r], =1, if r is available in p

If is_available[p, r] =1, tasks can be assigned to the resource in p

As a result I want the optimal start_period and end_period of each resource (can also be 0 for certain r)

 

Hence, is_available[p, r] =1 for all p under the following conditions:

1. p ≥ start_period[r]

2. p < end_period[r]

3. start_period[r] ≥ 0

 

I modeled it by creating 3 indicator constraint variables for the 3 conditions and combining them for all p, r:

m.addGenConstrAnd(is_available[p, r],
                  [is_available_criterion_1[p, r], is_available_criterion_2[p, r],
                   is_available_criterion_3[p, r]], "set_up_constraint")

The model works but since I added these constraints, the runtime increased drastically and it is almost impossible to receive a satisfying result within a reasonable time. So my question is, if you can think of a more efficient way to model this?

Thanks a lot in advance!

関連

• Scheduling

0

• 

  Simranjit Kaur

  • Gurobi Staff

  2023年05月26日 23:52 編集済み

  Hi Daniel,

  You can possibly use the binary variables start_binary[p, r] and end_binary[p, r] to model the definition of is_available[p,r] variable. Would something like the following work for you?

  is_available[p, r] = is_available[p-1, r] + start_binary[p, r] - end_binary[p, r]

  The is_available[p,r] variable remains 0 for all periods before the period when resource r is acquired. It becomes 1 in the period when start_binary[p, r] equals 1. Subsequently, it takes a value of 1 for all periods until the resource r is removed, which occurs when end_binary[p, r] equals 1. After that, it returns to 0 and remains 0 in subsequent periods.

  Best regards,

  Simran

  0

サインインしてコメントを残してください。