Why is my model infeasible?
回答済みHi, 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")
-
-
Gurobi Staff
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 -
サインインしてコメントを残してください。
コメント
3件のコメント