Proper TSP implementation by brute force

Question

I need to implement TSP algorithm by brute force for learning purposes.

I've understood there's a set of cities, let's call it V and it's possible to get a matrix representation for the costs for going from a v1 city to a v2 city. I'll assume there are not cycles, so it's no possible to going from v1 back to v1

Then, I should generate a matrix after these sum series:

However, I really can't see in a practice way how a matrix would be outputed from restrictions.

Let's say we got 3 cities:

Madrid, Berlin and Malmo

So the path costs are (and they're not forced to be the same for ways back):

From Madrid to:

Berlin: 12
Malmo: 20

From Berlin to

Madrid: 32
Malmo: 12

From Malmo to:

Madrid: 14
Berlin: 17

So my input is:

$$\begin{bmatrix} 0 & 12 & 20 \\ 32 & 0 & 12 \\ 14 & 17 & 0\end{bmatrix}$$

How should the matrix be outputed according to the sum series?

I assume the algorithm would need to generate a matrix from this exampple:

There are 3 cities x1, x2 and x3 and got the costs matrix shown below:

$$\begin{bmatrix} 10 & 2 & 1 \\ 3 & 10 & 2 \\ 11 & 2 & 10\end{bmatrix}$$

Following, example shows the next matrix:

$$\begin{bmatrix} x_{11}+x_{12}+x_{13} & & \\ & x_{21}+x_{22}+x_{23} & \\ & & x_{31}+x_{32}+x_{33}\\x_{11} & x_{21} & x_{31} \\ x_{12} & x_{22} & x_{32} \\ x_{13}& x_{23} & x_{33} \end{bmatrix}$$

Which would be the same as:

$$\begin{bmatrix} 1&1&1&0&0&0&0&0&0\\ 0&0&0&1&1&1&0&0&0\\ 0&0&0&0&0&0&1&1&1\\ 1&0&0&1&0&0&0&1&0\\ 0&0&1&0&0&1&0&0&1\\ 0&1&0&0&1&0&0&1&0\\ \end{bmatrix}$$

Then, considering the power ser of the three cities, matrix got the following rows added:

$$\begin{bmatrix} 0&1&1 & 0&0&0 & 0&0&0 \\ 0&0&0 & 1&0&1 & 0&0&0 \\ 0&0&0 & 0&0&0 & 1&1&0 \\ 0&0&1 & 0&0&1 & 0&0&0 \\ 0&1&0 & 0&0&0 & 0&1&0 \\ 0&0&0 & 1&0&0 & 1&0&0 \end{bmatrix}$$

Finally, the whole generated matrix is:

$$\begin{bmatrix} 1&1&1&0&0&0&0&0&0\\ 0&0&0&1&1&1&0&0&0\\ 0&0&0&0&0&0&1&1&1\\ 1&0&0&1&0&0&0&1&0\\ 0&0&1&0&0&1&0&0&1\\ 0&1&0&0&1&0&0&1&0\\ 0&1&1 & 0&0&0 & 0&0&0 \\ 0&0&0 & 1&0&1 & 0&0&0 \\ 0&0&0 & 0&0&0 & 1&1&0 \\ 0&0&1 & 0&0&1 & 0&0&0 \\ 0&1&0 & 0&0&0 & 0&1&0 \\ 0&0&0 & 1&0&0 & 1&0&0 \end{bmatrix}$$

Answer 1

I don't think you should build your matrix according to the integer program, but rather the distance matrix is given as input.

Label your cities in some way, for example let $1$ be Madrid, $2$ be Berlin, and $3$ be Malmo. In your matrix, the entry $(i,j)$ will contain the distance from the city $i$ to city $j$. So you'll get a $3 \times 3$ matrix with zeros on the diagonal (the distance from Madrid to Madrid is zero):

$$\begin{bmatrix} 0 & 12 & 20 \\ 32 & 0 & 12 \\ 14 & 17 & 0\end{bmatrix}$$

Notice that the matrix would be symmetric, if the distance from city $i$ to $j$ would equal the distance from $j$ to $i$.

Answer 2

You write: "I should generate a matrix given by..." That seems to come out of nowhere. You didn't explain why you think that is the way to solve this problem.

Anyway, if you want to solve it by exhaustive search, that's not the way to solve the problem. Exhaustive search means something different. It means you enumerate all possible solutions, compute how good each one is, and keep the best one.

Do you know what the set of possible solutions is? What does a possible solution look like? That would be a good place for you to start. Then, you should double-check that you know how to measure how good a possible solution is. From there, the solution should be straightforward.