Can you ignore node-0 in brute force attempts?

[thatcode]

The comment on https://github.com/fillipe-gsm/python-tsp/blob/master/python_tsp/exact/brute_force.py#L32 says:
However, we can fix node 0 and permutate only the remaining.

This is true for closed loops - once you've found the best you can rotate the loop until any node you want is node 0.

Is it really true for open loops? I haven't worked out a counter example yet, but I'm sure one can exist with not much effort!

[thatcode]

#!/usr/bin/env python3

import numpy as np
from python_tsp.exact import solve_tsp_dynamic_programming

distance_matrix = np.array(
    [
        [0, 4, 4, 10],
        [4, 0, 8, 5],
        [4, 8, 0, 3],
        [10, 5, 3, 0],
    ]
)
distance_matrix[:, 0] = 0
permutation, distance = solve_tsp_dynamic_programming(distance_matrix)

print(distance)
print(permutation)

Output:

12
[0, 1, 3, 2]

Expected output:

11
[1, 0, 2, 3]

[fillipe-gsm]

Hi, @thatcode , sorry for the late answer

You bring a very valid point and a nice example. But there may be some caveats with letting the algorithm choosing the initial node freely:

• Some users expect the initial node in the final route to always be the origin 0, as exemplified in this issue. So even if the best route as in your example does not start at 0 it may be confusing for some to change this behavior now.

  (This was probably my fault for never making it explicit)

• The brute force and the heuristic solvers can be adapted with not too much effort to find the best starting point, but the Dynamic Programming solver still needs an explicit starting point. The best that could be done is to run it multiple times, each one with a different starting point.

  I am perfectly o.k. if that the user manually enclose the solver inside a for loop in his/her code. But I am not in favor of doing this implicitly in this lib as it may be overkill, increase code complexity and simply become confusing for some users as mentioned before.

With all that said, I think the best approach is to implement a start_node argument to the solvers to make this explicit. For all solvers but Dynamic Programming it can receive value None, in which case the first node also varies with the rest. This also handles this open issue.

What do you think?

[thatcode]

Thanks for your reply :)

Since posting this I had also realised that, in the actual travelling salesman problem the 1st city is their home, so can't change. And you do implement this faithfully!

Given this, I think a minimal fix would be to update your README.md (the "Open TSP problem" section) to make it clearer that node 0 is fixed! I just followed (literally copy/pasted...) the distance_matrix[:, 0] = 0 line then was a bit confused!

Beyond that, making it programmable gives users the option to work around this. To avoid back-compatibility you might want to default to 0 rather than None until your next breaking change, but I'm fine with either.

(Also, as a support engineer, +1 for fixing two issues with one change :p)