how to represent the earliest index among a set of boolean decision variables in Python
Answered
Hi,
below is my situation
- want to move (or transfer) products (p) from location A to B.
- location A has two levels (or stories); L1, L2. Each level has unique set of products. Use L to indicate level
- there is moving capacity limitation for each time t (i.e., week). T represent time index set.
- we do not want to start transferring products on L1, unless all products of L2 is moved. However, it is OK to transfer some L1 products for the last transfer week of L2, if weekly capacity allows.
- objective is to finish the transfer as early as possible, without violating the transfer capacity.
I wonder how to represent 'we do not want to start transferring products on L1, unless all products of L2 is moved'
I have a boolean decision variable y(p,t)
- = 1, if product p is transferred at time t
- = 0, otherwise
my approach is to define the following integer variables
- e(L1) the earliest time that any product in L1 is transferred
- e(L2) the earliest time that any product in L2 is transferred
- w(L1) the latest time that any product in L1 is transferred
- w(L2) the latest time that any product in L2 is transferred
then add the constraint
- w(L2) <= e(L1)
assuming that the time index (or the week) starts from 0, I can add the following constraint to find the last week of transfer for each level
- w(L1) >= t * y(p,t) for all p in L1, t in T
- w(L2) >= t * y(p,t) for all p in L2, t in T
my question is, how can i represent the e(L1) and e(L2)?
for instance, for e(L1), i thought of using e(L1) <= t * y(p,t) but it does not seem to work. suppose that we have T={0,1,2}. For simplicity, suppose L1 only has one product p1. If we transfer p1 at week 1, and 2 (e.g., half of p1 at week1, the remaining half at week 2 due to capacity limit). Then, we have three constraints,
- e(L1) <= 0 * y(p1,0)
- e(L1) <= 1 * y(p1,1)
- e(L1) <= 2 * y(p1,2)
, where
- y(p1, 0) is False
- y(p1, 1) is True
- y(p1, 2) is True
, as we transfer p1 at week 1 and 2.
due to this constraint e(L1) <= 0 * y(p1,0), e(L1) becomes 0, even though y(p1,0) is False (i.e., even though there is no transfer of p1 at time 0).
hope my question makes sense. would appreciate any advice. thanks.
-
-
Gurobi Staff
In terms of performance, I'm a bit concerned the constraints linking variables y and w/e could have a bad impact, especially when the number of weeks grows. Fortunately you might get away with a purely binary approach, without explicit variables for those earliest/latest times.
Originally you stated: "We do not want to start transferring products on L1, unless all products of L2 is moved. However, it is OK to transfer some L1 products for the last transfer week of L2, if weekly capacity allows. "
You could rephrase that as "You can only move products on L1 in period t if you are not transferring anything of L2 anymore at t+1 or later." or "You can only move products on L1 in period t if you are done moving L2 products before t+1".
This suggests adding a binary variable indicating if level L2 has been completed. Specifically, assume that d(t)=1 would mean we've moved the last product of L2 before time period t. So the variable starts at 0 for the first period and remains 0 until for some specific period t we find out that there's nothing left to move anymore.
Then we get the following:
- Obviously we have d(t+1) >= d(t) : if we're done now, then we're also done tomorrow
- Also we have y(p2,t) + d(t) <= 1 : if we're done already, then we can't move anything anymore for L2
- And we have y(p1,t) <= d(t+1) : we can only move things of L1 if we're either already done with L2 or we'll be done after the current period t
What do you think?
0 -
-
-
For completeness: I believe if you stayed with your existing approach, you would need to model the second constraint as y(p, t) * e(L1) <= t to make it work. Whenever y(p,t)=0 the constraint becomes irrelevant since the left side is 0. When y(p,t)=1 then it forces e(L1) to be less or equal to t. This will make it a lowerbound on all times in which you move a product. I'm saying "lowerbound" because it doesn't necessarily represent the earliest time but may be smaller than that. Combined with your w(L2)<=e(L1) that should not be a problem. Now there's a product of a binary and a continuous variable in your constraint, but there are tricks to linearize this, e.g. see our webinar.
0 -
Please sign in to leave a comment.
Comments
2 comments