Efficiently model set up binary variables between start and end time variables
AnsweredDear 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!
-
Official comment
This post is more than two 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. -
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
Post is closed for comments.
Comments
2 comments