Little's algorithm example

Consider the complete graph on Aachen (Aa), Bamberg (Ba), Berlin (Be), Düsseldorf (Dü), Frankfurt (Fr), Hamburg (Ha), München (Mü), Nürnberg (Nü), and Stuttgart (St), with the diagonal set to $\infty$.

$$ \boldsymbol{A}=\begin{array}{c|ccccccccc} & \text{Aa} & \text{Ba} & \text{Be} & \text{Dü} & \text{Fr} & \text{Ha} & \text{Mü} & \text{Nü} & \text{St} \ \hline \text{Aa} & \infty & 57 & 64 & 8 & 26 & 49 & 64 & 47 & 46 \ \text{Ba} & 57 & \infty & 88 & 54 & 34 & 83 & 37 & 43 & 27 \ \text{Be} & 64 & 88 & \infty & 57 & 56 & 29 & 60 & 44 & 63 \ \text{Dü} & 8 & 54 & 57 & \infty & 23 & 43 & 63 & 44 & 41 \ \text{Fr} & 26 & 34 & 56 & 23 & \infty & 50 & 40 & 22 & 20 \ \text{Ha} & 49 & 83 & 29 & 43 & 50 & \infty & 80 & 63 & 70 \ \text{Mü} & 64 & 37 & 60 & 63 & 40 & 80 & \infty & 17 & 22 \ \text{Nü} & 47 & 43 & 44 & 44 & 22 & 63 & 17 & \infty & 19 \ \text{St} & 46 & 27 & 63 & 41 & 20 & 70 & 22 & 19 & \infty \end{array} $$

Heuristic for the upper bound

The [[Workspace/Traveling salesman problem/Metric traveling salesman problem|Metric TSP]] is a minimization problem. An upper bound $B_{up}$ can be found with the [[Workspace/Traveling salesman problem/Twice-around-the-tree heuristic|twice-around-the-tree heuristic]] followed by a [[Workspace/Neighborhood search/Neighborhood search|local search]] using 2-opt and 3-opt. This gives the upper bound $B_{up}=250$.

Cost matrix reduction for the lower bound

$\text{Aa}$: $\min=8$
$\text{Ba}$: $\min=27$
$\text{Be}$: $\min=29$
$\text{Dü}$: $\min=8$
$\text{Fr}$: $\min=20$
$\text{Ha}$: $\min=29$
$\text{Mü}$: $\min=17$
$\text{Nü}$: $\min=17$
$\text{St}$: $\min=19$

Sum of row reduction: $8+27+29+8+20+29+17+17+19=174$

$$ \boldsymbol{A}'=\begin{array}{c|ccccccccc} & \text{Aa} & \text{Ba} & \text{Be} & \text{Dü} & \text{Fr} & \text{Ha} & \text{Mü} & \text{Nü} & \text{St} \ \hline \text{Aa} & \infty & 49 & 56 & 0 & 18 & 41 & 56 & 39 & 38 \ \text{Ba} & 30 & \infty & 61 & 27 & 7 & 56 & 10 & 16 & 0 \ \text{Be} & 35 & 59 & \infty & 28 & 27 & 0 & 31 & 15 & 34 \ \text{Dü} & 0 & 46 & 49 & \infty & 15 & 35 & 55 & 36 & 33 \ \text{Fr} & 6 & 14 & 36 & 3 & \infty & 30 & 20 & 2 & 0 \ \text{Ha} & 20 & 54 & 0 & 14 & 21 & \infty & 51 & 34 & 41 \ \text{Mü} & 47 & 20 & 43 & 46 & 23 & 63 & \infty & 0 & 5 \ \text{Nü} & 30 & 26 & 27 & 27 & 5 & 46 & 0 & \infty & 2 \ \text{St} & 27 & 8 & 44 & 22 & 1 & 51 & 3 & 0 & \infty \end{array} $$

Find the smallest value in each column of $\boldsymbol{A}'$ and subtract it from all elements in that column:

$\text{Aa}$: $\min=0$
$\text{Ba}$: $\min=8$
$\text{Be}$: $\min=0$
$\text{Dü}$: $\min=0$
$\text{Fr}$: $\min=1$
$\text{Ha}$: $\min=0$
$\text{Mü}$: $\min=0$
$\text{Nü}$: $\min=0$
$\text{St}$: $\min=0$

Sum of column reduction: $0+8+0+0+1+0+0+0+0=9$

$$ \boldsymbol{B}_0=\begin{array}{c|ccccccccc} & \text{Aa} & \text{Ba} & \text{Be} & \text{Dü} & \text{Fr} & \text{Ha} & \text{Mü} & \text{Nü} & \text{St} \ \hline \text{Aa} & \infty & 41 & 56 & 0 & 17 & 41 & 56 & 39 & 38 \ \text{Ba} & 30 & \infty & 61 & 27 & 6 & 56 & 10 & 16 & 0 \ \text{Be} & 35 & 51 & \infty & 28 & 26 & 0 & 31 & 15 & 34 \ \text{Dü} & 0 & 38 & 49 & \infty & 14 & 35 & 55 & 36 & 33 \ \text{Fr} & 6 & 6 & 36 & 3 & \infty & 30 & 20 & 2 & 0 \ \text{Ha} & 20 & 46 & 0 & 14 & 20 & \infty & 51 & 34 & 41 \ \text{Mü} & 47 & 12 & 43 & 46 & 22 & 63 & \infty & 0 & 5 \ \text{Nü} & 30 & 18 & 27 & 27 & 4 & 46 & 0 & \infty & 2 \ \text{St} & 27 & 0 & 44 & 22 & 0 & 51 & 3 & 0 & \infty \end{array} $$

Total reduction: $174+9=183$, giving the root's lower bound $B_{low}=183$.

Penalty

Branching picks a zero entry $b_{ij}=0$ and asks whether the tour uses the edge $(i,j)$. Among all zero entries, the one chosen is the one with the largest penalty.

The penalty $r_{ij}$ of a zero entry $b_{ij}=0$ is the smallest other entry in row $i$ plus the smallest other entry in column $j$:

$$ r_{ij}=\min_{k\neq j} b_{ik} ;+; \min_{k\neq i} b_{kj} $$

Computing this for every zero entry of $\boldsymbol{B}_0$:

$$ \begin{array}{c|ccc} \text{Zero entry} & \text{Row min} & \text{Column min} & r_{ij} \ \hline \text{Aa}\to\text{Dü} & 17 & 3 & 20 \ \text{Ba}\to\text{St} & 6 & 0 & 6 \ \text{Be}\to\text{Ha} & 15 & 30 & 45 \ \text{Dü}\to\text{Aa} & 14 & 6 & 20 \ \text{Fr}\to\text{St} & 2 & 0 & 2 \ \text{Ha}\to\text{Be} & 14 & 27 & 41 \ \text{Mü}\to\text{Nü} & 5 & 0 & 5 \ \text{Nü}\to\text{Mü} & 2 & 3 & 5 \ \text{St}\to\text{Ba} & 0 & 6 & 6 \ \text{St}\to\text{Fr} & 0 & 4 & 4 \ \text{St}\to\text{Nü} & 0 & 0 & 0 \end{array} $$

The entry $\text{Be}\rightarrow\text{Ha}$ has the largest penalty, $r_{\text{Be},\text{Ha}}=45$, so branching happens on this edge.

Without $\text{Be}\rightarrow\text{Ha}$

Set $b_{\text{Be},\text{Ha}}\to\infty$ in $\boldsymbol{B}_0$ and re-reduce. Row Be loses its only zero, so its new minimum $15$ is subtracted from the row. Column Ha loses its only zero, so its new minimum $30$ is subtracted from the column.

$$ \Delta_{\text{excl}}=15+30=45 $$

$$ B_{low}=183+45=228 $$

$$ \boldsymbol{B}_1=\begin{array}{c|ccccccccc} & \text{Aa} & \text{Ba} & \text{Be} & \text{Dü} & \text{Fr} & \text{Ha} & \text{Mü} & \text{Nü} & \text{St} \ \hline \text{Aa} & \infty & 41 & 56 & 0 & 17 & 11 & 56 & 39 & 38 \ \text{Ba} & 30 & \infty & 61 & 27 & 6 & 26 & 10 & 16 & 0 \ \text{Be} & 20 & 36 & \infty & 13 & 11 & \infty & 16 & 0 & 19 \ \text{Dü} & 0 & 38 & 49 & \infty & 14 & 5 & 55 & 36 & 33 \ \text{Fr} & 6 & 6 & 36 & 3 & \infty & 0 & 20 & 2 & 0 \ \text{Ha} & 20 & 46 & 0 & 14 & 20 & \infty & 51 & 34 & 41 \ \text{Mü} & 47 & 12 & 43 & 46 & 22 & 21 & \infty & 0 & 5 \ \text{Nü} & 30 & 18 & 27 & 27 & 4 & 4 & 0 & \infty & 2 \ \text{St} & 27 & 0 & 44 & 22 & 0 & 21 & 3 & 0 & \infty \end{array} $$

Since the original matrix is symmetric, a tour avoiding $\text{Be}\rightarrow\text{Ha}$ is just the reverse of a tour using it. Only this exclude child needs to be searched here, and the include child is dropped for this one split.

The largest penalty in $\boldsymbol{B}1$ now belongs to the zero entry $b{\text{Ha},\text{Be}}=0$, with $r=14+27=41$. Branching continues on this entry.

Without $\text{Ha}\rightarrow\text{Be}$

Set $b_{\text{Ha},\text{Be}}\to\infty$ in $\boldsymbol{B}_1$ and re-reduce. Row Ha loses its only zero, so its new minimum $14$ is subtracted from the row. Column Be loses its only zero, so its new minimum $27$ is subtracted from the column.

$$ \Delta_{\text{excl}}=14+27=41 $$

$$ B_{low}=228+41=269 $$

$$ \boldsymbol{B}_2'=\begin{array}{c|ccccccccc} & \text{Aa} & \text{Ba} & \text{Be} & \text{Dü} & \text{Fr} & \text{Ha} & \text{Mü} & \text{Nü} & \text{St} \ \hline \text{Aa} & \infty & 41 & 29 & 0 & 17 & 11 & 56 & 39 & 38 \ \text{Ba} & 30 & \infty & 34 & 27 & 6 & 26 & 10 & 16 & 0 \ \text{Be} & 20 & 36 & \infty & 13 & 11 & \infty & 16 & 0 & 19 \ \text{Dü} & 0 & 38 & 22 & \infty & 14 & 5 & 55 & 36 & 33 \ \text{Fr} & 6 & 6 & 9 & 3 & \infty & 0 & 20 & 2 & 0 \ \text{Ha} & 6 & 32 & \infty & 0 & 6 & \infty & 37 & 20 & 27 \ \text{Mü} & 47 & 12 & 16 & 46 & 22 & 21 & \infty & 0 & 5 \ \text{Nü} & 30 & 18 & 0 & 27 & 4 & 4 & 0 & \infty & 2 \ \text{St} & 27 & 0 & 17 & 22 & 0 & 21 & 3 & 0 & \infty \end{array} $$

Since $B_{low}=269$ is greater than the incumbent $B_{up}=250$, this node is fathomed. No further branching happens here.

With $\text{Ha}\rightarrow\text{Be}$

Fixing edge $\text{Ha}\rightarrow\text{Be}$ removes row Ha and column Be from $\boldsymbol{B}_1$, since Ha's successor and Be's predecessor are now settled. The edge that would close the tour early, $\text{Be}\rightarrow\text{Ha}$, is already blocked from the previous step.

Every remaining row and column already contains a zero, so no further reduction is needed and $\Delta_{\text{incl}}=0$.

$$ B_{low}=228+0=228 $$

$$ \boldsymbol{B}_2=\begin{array}{c|cccccccc} & \text{Aa} & \text{Ba} & \text{Dü} & \text{Fr} & \text{Ha} & \text{Mü} & \text{Nü} & \text{St} \ \hline \text{Aa} & \infty & 41 & 0 & 17 & 11 & 56 & 39 & 38 \ \text{Ba} & 30 & \infty & 27 & 6 & 26 & 10 & 16 & 0 \ \text{Be} & 20 & 36 & 13 & 11 & \infty & 16 & 0 & 19 \ \text{Dü} & 0 & 38 & \infty & 14 & 5 & 55 & 36 & 33 \ \text{Fr} & 6 & 6 & 3 & \infty & 0 & 20 & 2 & 0 \ \text{Mü} & 47 & 12 & 46 & 22 & 21 & \infty & 0 & 5 \ \text{Nü} & 30 & 18 & 27 & 4 & 4 & 0 & \infty & 2 \ \text{St} & 27 & 0 & 22 & 0 & 21 & 3 & 0 & \infty \end{array} $$

The lower bound stays at $B_{low}=228$, still below the incumbent $B_{up}=250$, so this branch continues.

Penalty

Computing the penalty $r_{ij}=\min_{k\neq j} b_{ik} ;+; \min_{k\neq i} b_{kj}$ for every zero entry of $\boldsymbol{B}_2$:

$$ \begin{array}{c|ccc} \text{Zero entry} & \text{Row min} & \text{Column min} & r_{ij} \ \hline \text{Aa}\to\text{Dü} & 11 & 3 & 14 \ \text{Ba}\to\text{St} & 6 & 0 & 6 \ \text{Be}\to\text{Nü} & 11 & 0 & 11 \ \text{Dü}\to\text{Aa} & 5 & 6 & 11 \ \text{Fr}\to\text{Ha} & 0 & 4 & 4 \ \text{Fr}\to\text{St} & 0 & 0 & 0 \ \text{Mü}\to\text{Nü} & 5 & 0 & 5 \ \text{Nü}\to\text{Mü} & 2 & 3 & 5 \ \text{St}\to\text{Ba} & 0 & 6 & 6 \ \text{St}\to\text{Fr} & 0 & 4 & 4 \ \text{St}\to\text{Nü} & 0 & 0 & 0 \end{array} $$

The entry $\text{Aa}\rightarrow\text{Dü}$ has the largest penalty, $r_{\text{Aa},\text{Dü}}=14$, so branching happens on this edge next.

With $\text{Dü}\rightarrow\text{Aa}$

Fixing edge $\text{Dü}\rightarrow\text{Aa}$ removes row Dü and column Aa from $\boldsymbol{B}_2$, since Dü's successor and Aa's predecessor are now settled. The two fixed edges so far, $\text{Ha}\rightarrow\text{Be}$ and $\text{Dü}\rightarrow\text{Aa}$, do not share an endpoint, so no additional edge needs to be blocked yet.

Every remaining row and column already contains a zero, so no further reduction is needed and $\Delta_{\text{incl}}=0$.

$$ B_{low}=228+0=228 $$

$$ \boldsymbol{B}_3''=\begin{array}{c|ccccccc} & \text{Ba} & \text{Dü} & \text{Fr} & \text{Ha} & \text{Mü} & \text{Nü} & \text{St} \ \hline \text{Aa} & 41 & 0 & 17 & 11 & 56 & 39 & 38 \ \text{Ba} & \infty & 27 & 6 & 26 & 10 & 16 & 0 \ \text{Be} & 36 & 13 & 11 & \infty & 16 & 0 & 19 \ \text{Fr} & 6 & 3 & \infty & 0 & 20 & 2 & 0 \ \text{Mü} & 12 & 46 & 22 & 21 & \infty & 0 & 5 \ \text{Nü} & 18 & 27 & 4 & 4 & 0 & \infty & 2 \ \text{St} & 0 & 22 & 0 & 21 & 3 & 0 & \infty \end{array} $$

The lower bound stays at $B_{low}=228$, still below the incumbent $B_{up}=250$, so this branch continues.

Without $\text{Aa}\rightarrow\text{Dü}$

Set $b_{\text{Aa},\text{Dü}}\to\infty$ in $\boldsymbol{B}_2$ and re-reduce. Row Aa loses its only zero, so its new minimum $11$ is subtracted from the row. Column Dü loses its only zero, so its new minimum $3$ is subtracted from the column.

$$ \Delta_{\text{excl}}=11+3=14 $$

$$ B_{low}=228+14=242 $$

$$ \boldsymbol{B}_3'=\begin{array}{c|cccccccc} & \text{Aa} & \text{Ba} & \text{Dü} & \text{Fr} & \text{Ha} & \text{Mü} & \text{Nü} & \text{St} \ \hline \text{Aa} & \infty & 30 & \infty & 6 & 0 & 45 & 28 & 27 \ \text{Ba} & 30 & \infty & 24 & 6 & 26 & 10 & 16 & 0 \ \text{Be} & 20 & 36 & 10 & 11 & \infty & 16 & 0 & 19 \ \text{Dü} & 0 & 38 & \infty & 14 & 5 & 55 & 36 & 33 \ \text{Fr} & 6 & 6 & 0 & \infty & 0 & 20 & 2 & 0 \ \text{Mü} & 47 & 12 & 43 & 22 & 21 & \infty & 0 & 5 \ \text{Nü} & 30 & 18 & 24 & 4 & 4 & 0 & \infty & 2 \ \text{St} & 27 & 0 & 19 & 0 & 21 & 3 & 0 & \infty \end{array} $$

Since $B_{low}=242$ is still below the incumbent $B_{up}=250$, this node is not fathomed yet. It is set aside for later, while the search continues down the include child, which has the lower of the two bounds.

The largest remaining penalty in $\boldsymbol{B}3'$ belongs to the zero entry $b{\text{Dü},\text{Aa}}=0$, with $r=5+6=11$. Once this branch is resumed, branching continues on this entry.

Without $\text{Dü}\rightarrow\text{Aa}$

Set $b_{\text{Dü},\text{Aa}}\to\infty$ in $\boldsymbol{B}_3'$ and re-reduce. Row Dü loses its only zero, so its new minimum $5$ is subtracted from the row. Column Aa loses its only zero, so its new minimum $6$ is subtracted from the column.

$$ \Delta_{\text{excl}}=5+6=11 $$

$$ B_{low}=242+11=253 $$

$$ \boldsymbol{B}_4'=\begin{array}{c|cccccccc} & \text{Aa} & \text{Ba} & \text{Dü} & \text{Fr} & \text{Ha} & \text{Mü} & \text{Nü} & \text{St} \ \hline \text{Aa} & \infty & 30 & \infty & 6 & 0 & 45 & 28 & 27 \ \text{Ba} & 24 & \infty & 24 & 6 & 26 & 10 & 16 & 0 \ \text{Be} & 14 & 36 & 10 & 11 & \infty & 16 & 0 & 19 \ \text{Dü} & \infty & 33 & \infty & 9 & 0 & 50 & 31 & 28 \ \text{Fr} & 0 & 6 & 0 & \infty & 0 & 20 & 2 & 0 \ \text{Mü} & 41 & 12 & 43 & 22 & 21 & \infty & 0 & 5 \ \text{Nü} & 24 & 18 & 24 & 4 & 4 & 0 & \infty & 2 \ \text{St} & 21 & 0 & 19 & 0 & 21 & 3 & 0 & \infty \end{array} $$

Since $B_{low}=253$ is greater than the incumbent $B_{up}=250$, this node is fathomed. No further branching happens here.

With $\text{Dü}\rightarrow\text{Aa}$

Fixing edge $\text{Dü}\rightarrow\text{Aa}$ removes row Dü and column Aa from $\boldsymbol{B}_3'$, since Dü's successor and Aa's predecessor are now settled. The two fixed edges so far, $\text{Ha}\rightarrow\text{Be}$ and $\text{Dü}\rightarrow\text{Aa}$, do not share an endpoint, so no additional edge needs to be blocked yet.

Every remaining row and column already contains a zero, so no further reduction is needed and $\Delta_{\text{incl}}=0$.

$$ B_{low}=242+0=242 $$

$$ \boldsymbol{B}_4=\begin{array}{c|ccccccc} & \text{Ba} & \text{Dü} & \text{Fr} & \text{Ha} & \text{Mü} & \text{Nü} & \text{St} \ \hline \text{Aa} & 30 & \infty & 6 & 0 & 45 & 28 & 27 \ \text{Ba} & \infty & 24 & 6 & 26 & 10 & 16 & 0 \ \text{Be} & 36 & 10 & 11 & \infty & 16 & 0 & 19 \ \text{Fr} & 6 & 0 & \infty & 0 & 20 & 2 & 0 \ \text{Mü} & 12 & 43 & 22 & 21 & \infty & 0 & 5 \ \text{Nü} & 18 & 24 & 4 & 4 & 0 & \infty & 2 \ \text{St} & 0 & 19 & 0 & 21 & 3 & 0 & \infty \end{array} $$

The lower bound stays at $B_{low}=242$, still below the incumbent $B_{up}=250$, so this branch continues.