Proper TSP implementation by brute force 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 &amp; 12 &amp; 20 \\ 32 &amp; 0 &amp; 12 \\ 14 &amp; 17 &amp; 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 &amp; 2 &amp; 1 \\ 3 &amp; 10 &amp; 2 \\ 11 &amp; 2 &amp; 10\end{bmatrix}$$ 

Following, example shows the next matrix:

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

Which would be the same as:

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

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

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

Finally, the whole generated matrix is:

$$\begin{bmatrix} 1&amp;1&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0\\ 0&amp;0&amp;0&amp;1&amp;1&amp;1&amp;0&amp;0&amp;0\\ 0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;1&amp;1\\ 1&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;1&amp;0\\ 0&amp;0&amp;1&amp;0&amp;0&amp;1&amp;0&amp;0&amp;1\\ 0&amp;1&amp;0&amp;0&amp;1&amp;0&amp;0&amp;1&amp;0\\ 0&amp;1&amp;1 &amp; 0&amp;0&amp;0 &amp; 0&amp;0&amp;0 \\ 0&amp;0&amp;0 &amp; 1&amp;0&amp;1 &amp; 0&amp;0&amp;0 \\ 0&amp;0&amp;0 &amp; 0&amp;0&amp;0 &amp; 1&amp;1&amp;0 \\ 0&amp;0&amp;1 &amp; 0&amp;0&amp;1 &amp; 0&amp;0&amp;0 \\ 0&amp;1&amp;0 &amp; 0&amp;0&amp;0 &amp; 0&amp;1&amp;0 \\ 0&amp;0&amp;0 &amp; 1&amp;0&amp;0 &amp; 1&amp;0&amp;0 \end{bmatrix}$$
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 &amp; 12 &amp; 20 \\ 32 &amp; 0 &amp; 12 \\ 14 &amp; 17 &amp; 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$.