Using Outer Products and Matrix Multiplication to Compute Tour Weight in Traveling Salesman Problems

Question

Set up

Let $G$ be a complete, weighted, and directed graph with $N$ vertices as in the asymmetric Traveling Salesman Problem (TSP). Without loss of generality, let the the vertex set $V$ of $G$ be such that $V = \{1, 2, 3, \ldots, N\}$. Let $A$ be the adjacency matrix of $G$. Then the weight of the edge from vertex $i$ to vertex $j$ is $A_{i,j}$.

Let $T$ be a tour of $G$ i.e. a permutation of the vertices of $G$. For example, $T = \langle 3,1,2 \rangle$ for a graph with $N = 3$ vertices. The return to the first vertex is implicitly included at the end of the tour. Then the weight $w_T$ of $T$ is then

\begin{equation} w_T = A_{T_N, T_1} + \sum_{i = 1}^{N-1} A_{T_i,T_{i+1}}. \end{equation}

Matrix Multiplication

Now, instead of "indexing into" $A$, another way to get $A_{ij}$ is through multiplication of basis vectors $e_i$ where $e_i$ is zero in all its entries except at index $i$ where it is $1$. For example, $A_{11} = e_1^\intercal A e_1 = \langle 1, 0, \ldots, 0\rangle^\intercal A \langle 1, 0, 0, \ldots, 0\rangle$, and in general $A_{ij} = e_i^\intercal A e_j$. Therefore, the above equation can be rewritten as

\begin{equation} w_T = e_{T_N}^\intercal A e_{T_1} + \sum_{i = 1}^{N-1} e_{T_i}^\intercal A e_{T_{i+1}}. \end{equation}.

Using the Outer Product

Another way to approach this problem, in some sense, more directly, is through the use of outer products. The first step is create two matrices $E_l, E_r$ defined by

\begin{align} E_l &= \sum_{i = 1}^N e_i \otimes e_{T_i} \\ E_r &= \sum_{i = 1}^N e_i \otimes e_{T_{i + 1}}, \end{align}

where $T_{N + 1} = T_1$, and $u \otimes v$ is the outer product of $u$ and $v$. These matrices effectively have the basis vectors $e_{T_j}$ as their columns. Then, using the Trace, the weight of the tour can usually be succinctly represented as

\begin{equation} w_T = \mathrm{Tr}\hspace{1pt}(E_l A E_r). \end{equation}

The problem is that sometimes $E_l$ and $E_r$ have zero-diagonal, which mean so does the resulting matrix $E_l A E_r$, and thus the trace is also equal to zero while the actual weight of the tour is not.

Example

Consider a TSP whose graph has the adjacency matrix $A$ defined such that

\begin{equation} A = \begin{bmatrix} 0 & 2 & 3 \\ 4 & 0 & 6 \\ 7 & 8 & 0 \end{bmatrix} \end{equation}

and tours $T_1 = \langle 1,2,3 \rangle$ and $T_2 = \langle 2,3,1 \rangle$. These tours result in

\begin{align} E_{1,l} &= \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} & E_{1,r} &= \begin{bmatrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix} \implies& E_{1,l} A E_{1,r} &= \begin{bmatrix} 2 & 3 & 0 \\ 0 & 6 & 4 \\ 8 & 0 & 7 \end{bmatrix} \implies& \mathrm{Tr}\hspace{1pt} (E_{1,l} A E_{1,r}) &= 15 \\ % E_{2,l} &= \begin{bmatrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix} & E_{2,r} &= \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{bmatrix} \implies& E_{2,l} A E_{,r} &= \begin{bmatrix} 0 & 7 & 8 \\ 3 & 0 & 2 \\ 6 & 4 & 0 \end{bmatrix} \implies& \mathrm{Tr}\hspace{1pt} (E_{2,l} A E_{2,r}) &= 0 \\ \end{align}

Question

Because this formulation works for all the other tours of the 3-vertex instance (using the Julia code below), I'm curious why it doesn't work for all of them. Coincidence? Additionally, what would be a way to alter this method to make it work for all tours?

tour: [1, 2, 3] tour weight: 15
tour: [2, 1, 3] tour weight: 15
tour: [3, 2, 1] tour weight: 15
tour: [1, 3, 2] tour weight: 15
tour: [2, 3, 1] tour weight: 0
tour: [3, 1, 2] tour weight: 15

Code

Julia code implementing this method. The basis-vector outer-products are effectively taken care of with the stack function.

using LinearAlgebra

function basisVector(dim :: Int, index :: Int) :: Vector
    v = zeros(Int, dim)
    v[index] = 1
    return v
end

function tourWeight(adjacencyMatrix :: Matrix{T}, tour :: Vector{Int}) :: T where T <: Real
    basis = basisVector.(size(adjacencyMatrix)[1], [tour; view(tour, 1)])
    left  = basis[1:end-1] |> stack
    right = basis[2:end]   |> stack
    mat   = left * adjacencyMatrix * right
    return tr(mat)
end

mat = [0 2 3; 4 0 6; 7 8 0]
permutationVector = [[1,2,3],[2,1,3],[3,2,1],[1,3,2],[2,3,1],[3,1,2]]
(tour -> println("tour: $tour tour weight: ", tourWeight(mat, tour))).(permutationVector)

Answer 1

I think there is a problem both in the calculation of your matrices, and in the formula for your sum.

You want $E_l$ to order rows according to the permutation, I think it accomplishes what it does. You want $E_r$ to order columns according to the permutation but shifted by one. Your definition our $E_r$ gives the permutation matrix for the permutation shifted by one, but for swapping columns, you need to transpose it.

If we follow your notations, we should have \begin{equation} E_{1, r}= \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{bmatrix} \end{equation} This is the permutation matrix for the permutation $\langle 2,3,1 \rangle$ which is $T_1$ shifted by one.

Then you calculate $w^T = Tr(E_lAE_R^T)$.