I am trying to solve TSP using linear Integer Programming. I am trying to detect subtour to element them. When I solve the optimisation problem, I get a matrix with all the allowable routes as 1. I then multiply this with the distance matrix to get the total distance.
My matrix is very big but a smaller example will be:
As you can see here starting from 1st location, it first goes to 3rd location, then to 2nd location, then to 5th location and back to 1st location. This is one subtour and the second subtour is from 4th location it goes to 6th location and then back to 4th.
I am not sure how to go about coding this subtour such that it finds the smallest subtour and adds the constraint and then rerun the optimisation problem in a loop until there is only 1 subtour left.
Right now I am trying to find column location of 1 in 1st row and then go to row = column and repeat this. But I am not sure how to write this.