Conditional two-sided constraints
Answered
Hi
I followed the approach in this post to code a constraint (https://support.gurobi.com/hc/en-us/articles/4414392016529-How-do-I-model-conditional-statements-in-Gurobi). However, my model is infeasible. Do I have any mistakes:
This is what I am trying to code:
for k in clusters:
for j in nodes:
if (k-1)<Number[j]<=k:
y[j,k]=1
else:
y[j,k]=0
And this is what I am coding in Gurobi, where y[j,k] is a binary variable. I am trying to assign node j to a cluster k based on the number of objects. For example if node 1 has between 1.1 and 1.9 objects, then it should be assigned to k=2, and y[1,2]=1, else 0. clusters=[*range(1,50)], and j [*range(1,25)]
eps=0.0001
M=60+eps
for k in clusters:
for j in nodes:
m.addConstr((Number[j]>=(k-1)+eps-M*(1-y[j,k])), name="bigM_c1")
m.addConstr((Number[j]<=(k-1)+M*y[j,k]), name="bigM_c2")
m.addConstr((k>=Number[j]-M*(1-y[j,k])), name="bigM_c3")
m.addConstr((k<=Number[j]-eps+M*y[j,k]), name="bigM_c4")
Thanks!
-
Official comment
-
Gurobi Staff
This post is more than three 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,
Your constraints look fine at a first glance. You might want to drop the "-eps" term in constraint "bigM_c4". You don't need it, because your condition read Number <= k.
You say that your model is infeasible. Did you have a look at the article How do I determine why my model is infeasible?
Best regards,
Jaromił0 -
-
Thanks! I followed your suggestions. Also, I looked at the article and I computed the IIS. My model still is infeasible and I have the following message:
\ Model sc_it.lp_copy
\ LP format - for model browsing. Use MPS format to capture full model detail.
Minimize
Subject To
bigM_c2: Number[18] - 60.0001 y[18,18] <= 17
bigM_c3: Number[18] + 60.0001 y[18,18] <= 78.0001
bigM_c1: Number[18] - 60.0001 y[18,40] >= -21
bigM_c4: Number[18] + 60.0001 y[18,40] >= 40
Bounds
Number[18] free
Binaries
y[18,18] y[18,40]
EndDo you have any idea of what could be my issue according to the output? I appreciate your help, thanks
0 -
-
-
Do you have any idea of what could be my issue according to the output?
You can implement any combination of \(y_{18,18} \in \{0,1\}, y_{18,40} \in \{0,1\}\) to verify that any is infeasible. Having a look at your previous comments, it looks like you are modeling
17 < Number[18] <= 18
39 < Number[18] <= 40which is infeasible.
Best regards,
Jaromił0 -
-
Hi, I appreciated it your previous help, and I appreciate your help with this:
I might have an issue with the constraint formulation. I want to assign “j” to a cluster based on the rounding up of the number of objects (Number[j]). For example, if "j" have 11.4 objects then I want to assign it to "k=12" (since is between 11 and 12), then y[j,12]=1, and y[j,k≠12]=0. To this effect, I usually formulate the if-else as:
for k in clusters:
for j in nodes:
if (k-1)<Number[j]<=k:
y[j,k]=1
else:
y[j,k]=0
However, when I am using Gurobi python and add it as a constraint, I separate it as:
Number[j]<=k (equivalent to -Number[j]>=-k), and
Number[j]>k-1
And in gurobi python:
for k in clusters:
for j in nodes:
if j>0:
m.addConstr((Number[j]>=(k-1)+eps-M*(1-y[j,k])), name="bigM_c1")
m.addConstr((Number[j]<=(k-1)+M*y[j,k]), name="bigM_c2")
m.addConstr((-Number[j]>=-k-M*(1-y[j,k])), name="bigM_c3")
m.addConstr((-Number[j]<=-k+M*y[j,k]), name="bigM_c4")
Using the previous example (Number[j]=11.4 and evaluating k=1, which I expect y[j,1]=0, M=60, eps=0.0001)
((11.4>=0+0.0001-60*(1-0)), name="bigM_c1") OK
((11.4<=0+60*0, name="bigM_c2") NO
((-11.4>=-1-60*(1-0)), name="bigM_c3") OK
((-11.4<=-1+60*0), name="bigM_c4") OK
The second constraint of course does not hold with y[j,k]=0
I appreciate any advice regarding how to model this constraint in Gurobi python. I am not sure if the issue is because I need that if Number[j]<=k and Number[j]>k-1, then y[j,k], both should hold.
Thanks,
0 -
-
-
I think the issue arises because you are currently using one y[j,k] for both conditions k-1 < Number[j] and Number[j] <= k. With only one binary the condition reads 0 < 11.4 <= 1. The left "<" part is true but the "<=" is not. Thus, only one binary variable cannot capture this information.
Instead you should add 2 additional binaries, one for each condition, i.e., one binary x_left for k-1 < Number[j] and another one x_right for Number[j]<=k. Then, you set y[j,k] to 1 only if both binaries x_left and x_right are equal to 1. You can use Gurobi's built-in addGenConstrAnd method to model the and condition.
This would be something similar to
m.addConstr((Number[j]>=(k-1)+eps-M*(1-x_left[j,k])), name="bigM_c1")
m.addConstr((Number[j]<=(k-1)+M*x_left[j,k]), name="bigM_c2")
m.addConstr((-Number[j]>=-k-M*(1-x_right[j,k])), name="bigM_c3")
m.addConstr((-Number[j]<=-k+M*x_right[j,k]), name="bigM_c4")
m.addGenConstrAnd(y[j,k],[x_left[j,k],x_right[j,k]], name="and_c5")Best regards,
Jaromił0 -
-
That makes a lot of sense
Thank you so much for your help!
0 -
Post is closed for comments.
Comments
7 comments