python-tsp Custom origin point

Hi, I've been amazed by your work and how this library is so simple to use.

One thing I've come across is the fact that the 0 is always considered the origin for the tour. I think it would be a nice and easy addition if a custom origin point could be provided.

I read the code and I think it would be fairly simply to add. Can you think about it? Alternatively, could I make a pull request (I'm just fairly new at using github :D ) with the updated code?

Aug 02 '22 20:08 lucaper23

Hi, @lucaper23 , thanks for the interest in the project!

So, the question about manipulating the starting point arised more than twice, so I began thinking about including this functionality as well.

Before answering your questions, it may be worthwhile to mention here some workarounds to change the starting point with the current version (0.3.1 at the moment of this comment).

Workaround 1

First, for the heuristic solvers (local search and simulated annealing), because of the way the perturbation schemes are created, if you provide a starting permutation x0 with the first node different from 0, it will remain the initial one.

Thus, say you have a problem with ten nodes: from 0 to 9. Also suppose the starting point should be node 2. In that case, we can simply provide an initial permutation starting at 2.

Here is a possible code:

from random import sample

from python_tsp.heuristics import solve_tsp_local_search  # or solve_tsp_simulated_annealing

starting_node = 2
num_nodes = 5
x0 = [starting_node] + sample([node for node in range(num_nodes) if node != starting_node], k=num_nodes - 1)

# Say the distance matrix is provided or computed at variable `distance_matrix`
xopt, fopt = solve_tsp_local_search(distance_matrix, x0=x0)  # `xopt` should start at 2

Workaround 2

This one is more complex but it should work for any solver (even outside this library). The idea is to manipulate the distance matrix by swapping the positions from 0 to the new starting point.

Say we have the following distance matrix:

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

As we know, the entries distance_matrix[0, 1] indicates the distance from node 0 to 1, distance_matrix[2, 0] indicates the distance from 2 to 0, and so son.

Say again our starting point should be 2. In that case, we can swap column 0 with column 2 and row 0 with row 2, and solve the problem as usual. However, with that change, at the end, node 0 now represents node 2, and vice-versa.

This is a possible approach for swapping these nodes:

distance_matrix_tmp = distance_matrix.copy()
distance_matrix_tmp[:, [2, 0]] = distance_matrix_tmp[:, [0, 2]]  # swap columns
distance_matrix_tmp[[2, 0], :] = distance_matrix_tmp[[0, 2], :]  # swap rows

And here we would get

array([[ 0,  8,  4,  3],
       [ 8,  0,  5,  5],
       [ 4,  5,  0, 10],
       [ 3,  5, 10,  0]])

Check here that distance_matrix_tmp[0, 1] is now the same as distance_matrix[2, 1] and so on.

Thus, we can solve the problem as usual with any algorithm, say, Dynamic Programming:

xopt_tmp, fopt = solve_tsp_dynamic_programming(distance_matrix_tmp)

At this execution I got xopt_tmp = [0, 2, 1, 3]. But since 0 was swapped with 2, this should read xopt = [2, 0, 1, 3]. Notice that when you evaluate the route [2, 0, 1, 3] on the original distance_matrix, you should get the same permutation distance as evaluating [0, 2, 1, 3] at distance_matrix_tmp. Thus, fopt is the same in both cases.

In summary, the second more general workaround is:

from typing import List

import numpy as np

from python_tsp.exact import solve_tsp_dynamic_programming  # or any other solver


def swap_distance_matrix(distance_matrix: np.ndarray, new_starting_node: int) -> np.ndarray:
    distance_matrix_tmp = distance_matrix.copy()
    distance_matrix_tmp[:, [new_starting_node, 0]] = distance_matrix_tmp[:, [0, new_starting_node]]  # swap columns
    distance_matrix_tmp[[new_starting_node, 0], :] = distance_matrix_tmp[[0, new_starting_node], :]  # swap rows

    return distance_matrix_tmp


def recover_correct_permutation(permutation_tmp: List[int], new_starting_node: int) -> List[int]:
    index1 = permutation_tmp.index(0)
    index2 = permutation_tmp.index(new_starting_node)
    
    correct_permutation = permutation_tmp.copy()
    correct_permutation[index1], correct_permutation[index2] = correct_permutation[index2], correct_permutation[index1]


new_starting_node = 2
# Say you have a distance matrix or you compute it with the functions of this lib
distance_matrix_tmp = swap_distance_matrix(distance_matrix, new_starting_node)

xopt_tmp, fopt = solve_tsp_dynamic_programming(distance_matrix_tmp)

xopt = recover_correct_permutation(xopt_tmp, new_starting_node)

Sorry if this was a lot. I should most likely add one of these two internally in the code to abstract from the main user :)

Aug 04 '22 22:08 fillipe-gsm

Now, with respect to your questions: yes, I thought about it, and I found two possible solutions as depicted above.

Alternatively, could I make a pull request (I'm just fairly new at using github :D ) with the updated code?

Sure, I would love more contributions! The only prerequisite I have is that the new functionality should be available for all solvers. I am trying to follow this rule unless one functionality is simply impossible to be ported to everyone.

With that in mind, I was leaning towards the second suggestion I provided above. But I am open to alternatives if you have more ideas.

@lucaper23 , could you open a new pull request with what you had in mind? And don't worry about being new to Github; I'll help you with code reviews and other questions you might have.

Aug 04 '22 22:08 fillipe-gsm