Skip to main content

Why is my model infeasible?

Answered

Comments

4 comments

  • Official comment
    Simranjit Kaur
    • Gurobi Staff
    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.
  • 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

    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

Post is closed for comments.