Why is my model infeasible?
AnsweredHi, can someone please help me to understand why my model is infeasible?
These are the constraints:


and this is my model:
x = model1.addMVar((T,n+1,n+1), obj=1.0, vtype=gp.GRB.BINARY, name="x")
y = model1.addMVar((n+1,n+1), 0, vtype=GRB.INTEGER, name="y")
b = model1.addMVar((n+1,n+1), vtype=GRB.BINARY, name="b")
# Set objective function
model1.setObjective(gp.quicksum(D[i,j]*x[k,i,j] for k in range(T) for i in range(n+1) for j in range(n+1) if i!=j), gp.GRB.MINIMIZE)
# Add constraints
model1.addConstrs((gp.quicksum(x[k,i,j] for k in range(T) for i in range(n+1))==1 for j in range(1,n+1)), name="constr_1.1")
model1.addConstrs(((gp.quicksum(x[k,i,p] for i in range(n+1))-gp.quicksum(x[k,p,j] for j in range(n+1)))==0 for k in range(T) for p in range(1,n+1)), name="constr_1.2")
model1.addConstrs((gp.quicksum(x[k,0,j] for j in range(1,n+1))<=t[k] for k in range(T)), name="constr_2")
model1.addConstrs(((gp.quicksum(y[i,j] for i in range(n+1))-gp.quicksum(y[j,i] for i in range(n+1)))==s[j] for j in range(1,n+1)), name="constr_3")
model1.addConstrs((s[j]*x[k,i,j]<=y[i,j] for k in range(T) for i in range(n+1) for j in range(n+1) if i!=j), name="constr_4left")
model1.addConstrs((y[i,j]<=(Q[k]-s[i])*x[k,i,j] for k in range(T) for i in range(n+1) for j in range(1,n+1) if i!=j), name="constr_4right")
model1.addConstrs((y[i,i]==0 for i in range(n+1)), name="constr_5")
model1.addConstrs((x[k,i,i]==0 for k in range(T) for i in range(n+1)), name="constr_6")
-
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 Gaia,
Please have a look at How do I determine why my model is infeasible? This should help.
At a first glance, it looks like an index issue. Sometimes you use \(\texttt{range(n+1)}\) and sometimes \(\texttt{range(1,n+1)}\).
Best regards,
Jaromił0 -
Thank you for you answer. All ranges are fine, I checked them multiple times and they are consistent with the solution I found on this paper, which is the one I based my solution on. I also followed the instructions on the link you sent but I can't understand what I'm doing wrong.
This is my .ilp file
Minimize
Subject To
constr_2[1]: x[1,0,1] + x[1,0,2] + x[1,0,3] + x[1,0,4] + x[1,0,5]
+ x[1,0,6] + x[1,0,7] <= 1
constr_3[1]: y[0,1] - y[1,0] - y[1,2] - y[1,3] - y[1,4] - y[1,5] - y[1,6]
- y[1,7] + y[2,1] + y[3,1] + y[4,1] + y[5,1] + y[6,1] + y[7,1] = 3
constr_3[2]: y[0,2] + y[1,2] - y[2,0] - y[2,1] - y[2,3] - y[2,4] - y[2,5]
- y[2,6] - y[2,7] + y[3,2] + y[4,2] + y[5,2] + y[6,2] + y[7,2] = 2
constr_3[3]: y[0,3] + y[1,3] + y[2,3] - y[3,0] - y[3,1] - y[3,2] - y[3,4]
- y[3,5] - y[3,6] - y[3,7] + y[4,3] + y[5,3] + y[6,3] + y[7,3] = 6
constr_3[4]: y[0,4] + y[1,4] + y[2,4] + y[3,4] - y[4,0] - y[4,1] - y[4,2]
- y[4,3] - y[4,5] - y[4,6] - y[4,7] + y[5,4] + y[6,4] + y[7,4] = 8
constr_3[5]: y[0,5] + y[1,5] + y[2,5] + y[3,5] + y[4,5] - y[5,0] - y[5,1]
- y[5,2] - y[5,3] - y[5,4] - y[5,6] - y[5,7] + y[6,5] + y[7,5] = 5
constr_3[6]: y[0,6] + y[1,6] + y[2,6] + y[3,6] + y[4,6] + y[5,6] - y[6,0]
- y[6,1] - y[6,2] - y[6,3] - y[6,4] - y[6,5] - y[6,7] + y[7,6] = 4
constr_3[7]: y[0,7] + y[1,7] + y[2,7] + y[3,7] + y[4,7] + y[5,7] + y[6,7]
- y[7,0] - y[7,1] - y[7,2] - y[7,3] - y[7,4] - y[7,5] - y[7,6] = 4
constr_4right[1,0,1]: - 10 x[1,0,1] + y[0,1] <= 0
constr_4right[1,0,2]: - 10 x[1,0,2] + y[0,2] <= 0
constr_4right[1,0,3]: - 10 x[1,0,3] + y[0,3] <= 0
constr_4right[1,0,4]: - 10 x[1,0,4] + y[0,4] <= 0
constr_4right[1,0,5]: - 10 x[1,0,5] + y[0,5] <= 0
constr_4right[1,0,6]: - 10 x[1,0,6] + y[0,6] <= 0
constr_4right[1,0,7]: - 10 x[1,0,7] + y[0,7] <= 0
Bounds
y[0,1] free
y[0,2] free
y[0,3] free
y[0,4] free
y[0,5] free
y[0,6] free
y[0,7] free
y[1,2] free
y[1,3] free
y[1,4] free
y[1,5] free
y[1,6] free
y[1,7] free
y[2,1] free
y[2,3] free
y[2,4] free
y[2,5] free
y[2,6] free
y[2,7] free
y[3,1] free
y[3,2] free
y[3,4] free
y[3,5] free
y[3,6] free
y[3,7] free
y[4,1] free
y[4,2] free
y[4,3] free
y[4,5] free
y[4,6] free
y[4,7] free
y[5,1] free
y[5,2] free
y[5,3] free
y[5,4] free
y[5,6] free
y[5,7] free
y[6,1] free
y[6,2] free
y[6,3] free
y[6,4] free
y[6,5] free
y[6,7] free
y[7,1] free
y[7,2] free
y[7,3] free
y[7,4] free
y[7,5] free
y[7,6] free
Binaries
x[1,0,1] x[1,0,2] x[1,0,3] x[1,0,4] x[1,0,5] x[1,0,6] x[1,0,7]
Generals
y[0,1] y[0,2] y[0,3] y[0,4] y[0,5] y[0,6] y[0,7] y[1,0] y[1,2] y[1,3]
y[1,4] y[1,5] y[1,6] y[1,7] y[2,0] y[2,1] y[2,3] y[2,4] y[2,5] y[2,6]
y[2,7] y[3,0] y[3,1] y[3,2] y[3,4] y[3,5] y[3,6] y[3,7] y[4,0] y[4,1]
y[4,2] y[4,3] y[4,5] y[4,6] y[4,7] y[5,0] y[5,1] y[5,2] y[5,3] y[5,4]
y[5,6] y[5,7] y[6,0] y[6,1] y[6,2] y[6,3] y[6,4] y[6,5] y[6,7] y[7,0]
y[7,1] y[7,2] y[7,3] y[7,4] y[7,5] y[7,6]
End0 -
Hi Gaia,
If you take a look at the IIS provided by Gurobi and add up all \(\texttt{constr_3}\) constraints, you end up with
constr_2[1]: x[1,0,1] + x[1,0,2] + x[1,0,3] + x[1,0,4] + x[1,0,5]
+ x[1,0,6] + x[1,0,7] <= 1
constr_3_add_up: y[0,1] + y[0,2] + y[0,3] + y[0,4] + y[0,5] + y[0,6] + y[0,7]
- y[1,0] - y[2,0] - y[3,0] - y[4,0] - y[5,0] - y[6,0] - y[7,0] = 32
constr_4right[1,0,1]: - 10 x[1,0,1] + y[0,1] <= 0
constr_4right[1,0,2]: - 10 x[1,0,2] + y[0,2] <= 0
constr_4right[1,0,3]: - 10 x[1,0,3] + y[0,3] <= 0
constr_4right[1,0,4]: - 10 x[1,0,4] + y[0,4] <= 0
constr_4right[1,0,5]: - 10 x[1,0,5] + y[0,5] <= 0
constr_4right[1,0,6]: - 10 x[1,0,6] + y[0,6] <= 0
constr_4right[1,0,7]: - 10 x[1,0,7] + y[0,7] <= 0There you can easily see why the model is infeasible. At most one \(x\) variable can be 1. Thus, at most one variable \(y_{0,i}\) can take values in \(\{0,\dots,10\}\). So the new constraint cannot be satisfied, because the left-hand side can add up to at most a value of \(10\).
I think it might make sense for you to write the model to an LP file
model1.write("myLP.lp")and analyze it. It might be easier to spot a mistake this way. If possible, you could also reduce the size of the model to make the analysis easier.
Best regards,
Jaromił0
Post is closed for comments.
Comments
4 comments