I am looking at the famous travelling salesman problem, and am following this video tutorial (note: this link goes to the specific point I am confused about; please read on before clicking this link).
Apparently, in order to solve this using a "branch and bound" method, we need to reduce the matrix that shows the distances (and the "map" of locations to visit) which I include a screenshot of below for convenience.
At the video link, the teacher proceeds to describe we need to "reduce" the matrix, and shows how this is done. Whereas I understand how this works, I am not familiar with mathematics enough to know why this needs to be done and how it helps solve this problem; I can't see why using the original matrix numbers is not good enough.
Moreover, when drawing the state space tree for the problem, the teacher shows the cost of travelling from 1->2 as 35, yet the matrix shows the cost of 1->2 is 20 (see below).
Can someone please explain this and why I can't just use the numbers in the original matrix?
(Please update tags as appropriate)
I had the same question when I saw the matrix reduction stuff, so I have tried to prove something below and hope it helps.
In general, additional to the basic version of branch and bound (uniformed cost search or weighted breadth first search), we may also need a lower bound of the optimal solution to serve as an admissible heuristic, which will significantly decrease the number of times of state (node) expansion. Here, reducing the matrix is to have a lower bound for the potential optimal solution. Mathematically, given a feasible solution $\pi$ (i.e. a legal tour in TSP that may or may not be with minimum cost), if $\forall \pi. c(\pi) \geq h$, then $c(\pi^*) \geq h$. Then $h$ will be an admissible heuristic. We will prove that $h$ defined by the reduced cost from the original matrix is admissible.
Given a feasible tour $\pi$, each out-edge (w.r.t. every vertex) in the tour is trivially longer than the shortest edge going out of that vertex, i.e. $\forall (i,j)\in \pi. c(i,j) \geq \min_{k\in V} c(i,k)$. Therefore, $$ c(\pi) = \sum_{(i,j)\in \pi} c(i,j) \geq \sum_{i\in V} \min_{k\in V} c(i,k). $$ Note that this relaxation may be too much. If we can even have a lower bound for $[c(i,j) - \min_{k\in V} c(i,k)]$, then the total lower bound will be tighter. Observe that $c(i,j)$ is actually a function with two arguments, so that it can actually be relaxed from either side of $i$ or $j$. Denote $g(i) := \min_{k\in V} c(i,k)$, we have $$ c(i,j) - g(i) \geq \min_{q\in V} c(q,j) - g(q) $$ Substitute things back, and sum over $j$, we have $$ \sum_{(i,j) \in \pi} c(i,j) - g(i) \geq \sum_{j\in V} \min_{q\in V} c(q,j) - g(q) $$ Note that $\sum_{(i,j)\in \pi} g(i) = \sum_{i\in V} g(i)$. Therefore, $$ \sum_{(i,j)\in \pi}c(i,j) \geq \sum_{i\in V} \min_{k\in V} c(i,k) + \sum_{j\in V} \min_{q\in V} [c(q,j) - \min_{k'\in V} c(q,k')] $$ where, in the RHS, the first part constitutes the reduced row cost and the second part constitutes the reduced column cost.