Infeasibility in TSP

ユーザーの入力を待っています。

Ishana Raghoebardajal

2022年11月23日 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 :)

関連

• General Constraints
• Infeasible
• TSP

0

• 

  Jaromił Najman

  • Gurobi Staff

  2022年11月24日 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

サインインしてコメントを残してください。