Infeasibility in TSP

Awaiting user input

Ishana Raghoebardajal

November 23, 2022 21:37

• 
• 

Hi! I am trying to solve a type of Traveling Salesman Problem without eliminating subtours (it is a constrained multi-depot problem so for the first sub-problem, I consider flexible depots). I studied the example given on the Gurobi website and tried to implement it for my own problem.

The constraint that makes sure two edges are adjacent to one another, does not seem to be working in my model. Only when I remove this specific constraint from the model, is it feasible.

cons = m.addConstrs(decision.sum(c, '*') == 2 for c in coordinates)

"coordinates" is the list of coordinates in a 6x6 matrix ( (0,0), (0,1), (0,2)....(6,6)).

"decision" represents the choice of going from e.g. (0,0) to (3,4)

 

Specifically, if I change the 2 (which would mean being able to leave each node you get to if I understand correctly) to 0, I get a feasible solution in which about 80% of nodes are visited, but if I want it at least larger than 0, it immediately becomes infeasible. 

 

I am not sure what I am doing wrong. Any advice or input would be appreciated :)

Related to

• General Constraints
• Infeasible
• TSP

0

• Official comment

  

  Simranjit Kaur

  • Gurobi Staff

  November 13, 2026 01:52

  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

  November 24, 2022 10:53

  Hi Ishana,

  Did you try computing an IIS as discussed in How do I determine why my model is infeasible?

  Best regards, 
  Jaromił

  0

Post is closed for comments.