Modeling overlap constraint.
進行中
Hi, I am new to Gurobi and I am trying to implement overlap constraint.
I have two sets of variables X[0..n] and Y[0..n]. X is independent of Y. X represents length and Y represents start. I want to add a constraint to prevent overlapping. Precisely, given any pair
(X[i], Y[i]) and (X[j], Y[j]), I was thinking of adding constraint
Y[i] > Y[j] + X[j]
OR
Y[i] + X[i] < Y[j]
By reading the documentation, I think I should be using addGenConstrOr. This requires, me to capture the result of the above comparison in a binary aux variables and use it in the addGenConstrOr.
aux1 = opt_mod.addVar(name="aux1", vtype = gp.GRB.BINARY)
aux2 = opt_mod.addVar(name="aux2", vtype = gp.GRB.BINARY)
result = opt_mod.addVar(name="result", vtype = gp.GRB.BINARY)
-
正式なコメント
Hi Shesha,
Regarding the strict inequalities:
- If the X/Y variables are continuous, > and >= would mean the same thing
- If they are integer, then most likely >= is still what you need. For example, if you have discretized time and start/length both represent days, then I suspect >= does the job.
For the relation between auxiliary variables and your constraints, consider using indicator constraints. Note that a single auxiliary variable might be sufficient instead of two, because you can define the meaning of aux=0 and aux=1 when creating the indicator constraints. In that case, you also don't need the or constraint anymore.
Hope this helps!
Kind regards,
Ronald -
Thanks for introducing me to indicator constaints. I was thinking of implementing this way. Is there a better way ?
if i != k and j != l:
varname = "AUX1_%02d_%02d" % (k, l)
aux1 = opt_mod.addVar(name=varname, vtype = gp.GRB.BINARY)
varname = "AUX2_%02d_%02d" % (k, l)
aux2 = opt_mod.addVar(name=varname, vtype = gp.GRB.BINARY)
opt_mod.addGenConstrIndicator(aux1, True, VAR_START[i][j] >= VAR_START[k][l] + VAR_WIDTH[k][l] * W[k])
opt_mod.addGenConstrIndicator(aux2, True, VAR_START[i][j] + VAR_WIDTH[i][j] * W[i] <= VAR_START[k][l])
varname = "RANGE_%02d_%02d" % (k, l)
opt_mod.addConstr( aux1 + aux2 >= 1, name = varname)0 -
Hi,
I would make slight changes to reduce this to a single auxiliary variable:
if i != k and j != l: varname = "AUX_%02d_%02d" % (k, l) aux = opt_mod.addVar(name=varname, vtype = gp.GRB.BINARY) opt_mod.addGenConstrIndicator(aux, 0, VAR_START[i][j] >= VAR_START[k][l] + VAR_WIDTH[k][l] * W[k]) opt_mod.addGenConstrIndicator(aux, 1, VAR_START[i][j] + VAR_WIDTH[i][j] * W[i] <= VAR_START[k][l])
Kind regards,
Ronald0 -
Should I have to add?
opt_mod.addConstr( aux >= 1, name = varname)Additionally,|-----------| (uses index i,j)
|-------| (uses index k, l)In this case, for the first indicator evaluates to true, aux is set to 0 and the second indicator evaluates to false, and aux is set to 0 again. In this case, aux is saying false meaning it overlaps. May be I am misunderstanding the usage of single variable. Can you please clarify?
0 -
Hi Shesha,
There's two things at play here:
- Indicator constraints work the other way around. The rule is if AUX=0 then ; the variable in the first argument is the condition, not the "result".
- The solver always satisfies all constraints at once; there's no sequence of constraints being considered one by one.
So the idea is that we only tell the solver that it has to make a choice for AUX (by definition, every variable has to be assigned a single value by the solver). Either it sets AUX=0 and will then need to ensure that (i,j) is after (k,l). Or it sets AUX=1 and will ensure (k,l) is after (i,j).
So, adding AUX>=1 is not necessary and would even break the model. Instead, because AUX is a binary variable, the solver already knows it must assign either 0 or 1.
Kind regards,
Ronald0 -
Thanks Ronald for your explanation. So if I understand correctly, solver will choose AUX=0 and try to satisfy the first condition. If not, it will set to 1 and tries to satisfy the second condition. If neither can be satisfied, then solver bails our saying there is no feasible solution? On the other hand, if either of the conditions is satisfied, then model will output a the feasible solution.
Is my understanding accurate ?
0 -
I attempted to use your suggestions ..
for i in range (NVARS):
for j in range (NCONTAINERS):
for k in range (NVARS):
for l in range (NCONTAINERS):
if i != k and j != l:
varname = "AUX_%02d_%02d_%02d_%02d" % (i, j, k, l)
aux = opt_mod.addVar(name=varname, vtype = gp.GRB.BINARY)
opt_mod.addGenConstrIndicator(aux, 0, Y[i][j] >= Y[k][l] + X[k][l])
opt_mod.addGenConstrIndicator(aux, 1, Y[i][j] + X[i][j] <= Y[k][l])Looks like it is not getting the result I need. I can see overlaps. Am I missing anything ?
0 -
Hi Shesha,
Then it comes down to debugging. Your next step would be to find the (i,j) and (k,l) pair that overlap and then request/print the corresponding variable values including the AUX variable for that pair. Often seeing a specific case with corresponding variables, and putting those side-by-side with the constraint code above, reveals something that is off.
Kind regards,
Ronald0 -
Thank you Ron for all your kind responses . I will debug it. I have last two questions.
1. Can you confirm if the indicator constrains are specified correctly?
2. Is the one aux variable solution optimization over the two aux variable solution or is the two variable solution incorrect?
Ragards,
Shesha0
サインインしてコメントを残してください。
コメント
9件のコメント