Skip to main content

My model is infeasible, i have found the constraint which is causing it but i can\t find out what the reason is.

Answered

Comments

3 comments

  • Michel Soares
    Thought Leader

    Hi Jordi.

    Regarding your IIS constraints:

     LoadAfterVisit_11_22_1: - 1100 C1711 - C3661 + C3727 >= 849
     LoadAfterVisit_22_11_1: - 1100 C3235 + C3661 - C3727 >= 904

    Let's assume C1711 is zero and C3235 is zero, then we get:
    - C3661 + C3727 >= 849
    C3661 - C3727 >= 904
    If we sum both constraints we have:
    0 >= 1753, which is infeasible.

    Let's assume C1711 is 1 and C3235 is 1, then we get:
    -1100 - C3661 + C3727 >= 849
    -1100 + C3661 - C3727 >= 904
    If we sum both constraints we have:
    -2200 >= 1753, which is also infeasible.

    If we assume only one of the variables C1711 or C3235 is one and we sum the constraints, we get:
    -1100 >= 1753

    Therefore, any combination of the values of these binaries produce an infeasible model.

    0
  • Mario Ruthmair
    Gurobi Staff Gurobi Staff

    Hi Jordi,

    First, I would recommend to assign names to your variables via

    x = mdl.addVars( ..., name="x")
    u = mdl.addVars( ..., name="u")

    Usually, this helps a lot for debugging.

    Michel already argued correctly from a math perspective why your model is always infeasible.
    Applied to your CVRP model, it means that your Big-M constraints (LoadAfterVisit) seem to have an issue.

    Here are Python notebooks containing a few (homogeneous) CVRP modeling approaches (including the Big-M model), maybe they help to find the issue.

    Best regards,
    Mario

    0
  • Mario Ruthmair
    Gurobi Staff Gurobi Staff

    Hi Jordi,

    I could not resist diving deeper into your case (I am VRP-addicted). After relating your IIS with your model formulation, I found no flaw in your code and model.
    The only explanation I have that leads to your IIS is that the customer demands at node 11 and node 22 are larger than the capacity of vehicle 1 (Q_1=1100). In a heterogeneous VRP, this might happen, i.e., some vehicles just cannot serve some customers since their capacity is too small. But then, you need to catch that in your code and skip some constraints, e.g., the Big-M ones and maybe even further ones. If you know that some vehicles cannot serve some customers you might be able to fix some variables to 0 or better not even create them.

    0

Please sign in to leave a comment.