Skip to main content

Why is my model infeasible?

Answered
Gaia Ebli
  • Gurobi-versary
  • First Comment
  • First Question

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")

Related to

0

Comments

3 comments

Date Votes
  • Jaromił Najman
    • 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
  • Gaia Ebli
    • Gurobi-versary
    • First Comment
    • First Question

    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]
    End
    0
  • Jaromił Najman
    • Gurobi Staff
    Edited

    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] <= 0

    There 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

Please sign in to leave a comment.

Didn't find what you were looking for?

New post