\pdfpagewidth=8.5truein  \pdfpageheight=11truein
\hsize=6truein  \vsize=9.3truein
\pdfhorigin=1.25truein  \pdfvorigin=0.8truein

\input amssym.tex

\edef\restoreinterlineskip{\noexpand\baselineskip=\the\baselineskip\relax\noexpand\lineskiplimit=\the\lineskiplimit\relax\noexpand\lineskip=\the\lineskip}

\long\def\boxed#1{\vbox{\offinterlineskip
	\hrule
	\hbox to \hsize{%
	\hss\vrule\hskip1em%
	\vbox{\advance\hsize by-2em \advance\hsize by-0.8pt
	\restoreinterlineskip
	\vskip1ex
	\noindent#1\par
	\vskip1ex
	}\hskip1em\vrule\hss}%
	\hrule}}

\def\Rmax{R_{\max}}

\def\itemitemitem{\par\indent \hangindent3\parindent \hskip\parindent \textindent}

\headline={\hfil}  \footline={\hfil Page~\folio\hfil}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\centerline{\bf Branch-and-bound algorithm for the traveling salesman problem}

\medskip

\noindent The traveling salesman problem is discussed in Section~8.7 of the
textbook. The branch-and-bound algorithm described in that section is slightly
incomplete, so here is a careful description of an improved version of the
algorithm.

\bigbreak

\noindent{\bf The problem}

\medskip

\noindent The {\it traveling salesman problem\/} (TSP) is as follows: Given a
list of cities and a table of distances from each city to the others, find a
shortest circuit that visits each city exactly once and returns to the starting
city.

\bigbreak

\noindent{\bf Ingredients of the algorithm}

\medskip

\noindent The branch-and-bound algorithm for the traveling salesman problem
uses a branch-and-bound tree, like the branch-and-bound algorithms for the
knapsack problem and for solving integer programs.

\smallskip

\item{$\bullet$} The node at the top of the tree is called the {\it root}. All
edges (arrows) in the tree point downward. If an edge points from a node~$P$ to
a node~$C$, then $P$ is called the {\it parent\/} of~$C$, and $C$~is called a
{\it child\/} of~$P$.

\smallskip

\item{$\bullet$} Every node in the branch-and-bound tree has

\smallskip

\itemitem{--} a {\it node number\/};

\smallskip

\itemitem{--} a {\it label}, representing the decision made at that node either
to take or not to take a specific link from one city to another (the labels of
the terminal nodes of the tree represent two links);

\smallskip

\itemitem{--} a {\it bound}, giving a lower limit on the possible lengths of
circuits below that node in the tree;

\smallskip

\itemitem{--} an {\it incoming matrix\/}; and

\smallskip

\itemitem{--} an {\it opportunity matrix}.

\smallskip

\item{} (Exceptions: The root node of the branch-and-bound tree does not need a
label, and the terminal [leaf] nodes of the tree do not have incoming or
opportunity matrices.)

\smallskip

\item{$\bullet$} Every matrix (both incoming matrices and opportunity matrices)
has an associated ``$L$-value,'' which could be called the ``deduction total.''
As the algorithm progresses, distances in the matrix are decreased, and the
$L$-value keeps track of the total amount we have subtracted from distances
since the original distance matrix.

\bigbreak

\boxed{

\noindent{\bf Top-level outline of the algorithm}

\medskip

\item{1.} Draw and {\it initialize\/} the root node (see below for details).

\smallskip

\item{2.} Repeat the following step until a solution (i.e., a complete circuit,
represented by a terminal node) has been found $\underline{\bf and}$ no
unexplored non-terminal node has a smaller bound than the length of the best
solution found:

\smallskip

\itemitem{--} Choose an unexplored non-terminal node with the smallest bound,
and {\it process\/} it (see page~2 for details about this step).

\smallskip

\item{3.} When a solution has been found $\underline{\bf and}$ no unexplored
non-terminal node has a smaller bound than the length of the best solution
found, then the best solution found is optimal.

\smallskip

}  % end \boxed

\bigbreak

\noindent{\bf Initialization of the root node}

\medskip

\item{$\bullet$} The {\it node number\/} of the root node is~0 (or~1 if you
like; it doesn't really matter where you start counting).

\smallskip

\item{$\bullet$} The root node doesn't need a {\it label}, but if you want to
give it one you can label it ``All circuits'' as the textbook does, or use the
label~``$\varnothing$'' because the node doesn't represent a decision, or you
can label it ``Root,'' or whatever.

\smallskip

\item{$\bullet$} The {\it bound\/} of the root node is~0.

\smallskip

\item{$\bullet$} The {\it incoming matrix\/} of the root node is the original
matrix of distances, with $M$'s along the diagonal; the $L$-value of this
matrix is $L=0$.

\bigbreak

\noindent{\bf Steps to process a node}

\medskip

\item{1.} Compute the {\it opportunity matrix\/} for the node. Beginning
with the node's incoming matrix:

\smallskip

\itemitem{(a)} Set $L=\hbox{the}$ incoming matrix's $L$-value.

\smallskip

\itemitem{(b)} Ensure that every row and every column has exactly one~$M$. [The
matrix might contain $N$'s too, from step~6(b)---these don't count as~$M$'s.]
If necessary, replace one entry of the matrix with an~$M$ to meet this
condition. [The $M$'s enforce acyclicity until a full circuit has been
completed.]

\smallskip

\itemitem{(c)} Ensure that every column contains at least one zero. If
necessary, subtract the smallest number in a column from every number in that
column, and add the number that was subtracted to~$L$.

\smallskip

\itemitem{(d)} Ensure that every row contains at least one zero. If necessary,
subtract the smallest number in a row from every number in that row, and add
the number that was subtracted to~$L$.

\smallskip

\item{} The resulting matrix is this node's opportunity matrix, and the
$L$-value of this opportunity matrix is the value that $L$ has after possibly
being increased in steps (c)~and~(d) above.

\medbreak

\item{2.} [First special case.] Is the opportunity matrix $2\times2$? If so:

\smallskip

\itemitem{(a)} A $2\times2$ opportunity matrix will always look like either
$\bigl[{M\atop0}{0\atop M}\bigr]$ or $\bigl[{0\atop M}{M\atop0}\bigr]$.

\smallskip

\itemitem{(b)} Create a single child node, and assign it the next available node
number.

\smallskip

\itemitemitem{--} The {\it label\/} of the child node consists of the two links
that correspond to the zeroes in the $2\times2$ opportunity matrix. (For
example, if one zero is in the row for city~3 and the column for city~1, and
the other zero is in the row for city~4 and the column for city~5, then the
label of the child node is ``$3\to1$, $4\to5$.'')

\smallskip

\itemitemitem{--} The {\it bound\/} of the child node is the $L$-value of the
$2\times2$ opportunity matrix.

\smallskip

\itemitemitem{--} The child node has no {\it incoming matrix}.

\smallskip

\itemitem{(c)} The child node is a terminal node that represents a solution
(i.e., a complete circuit) given by the links specified by the labels of the
nodes along the path from the root node to the child node, and the length of
this circuit is equal to the bound of the child node.

\smallskip

\itemitem{(d)} $\underline{\it Check\/}$ that the length of this circuit equals
the bound of the child node by adding up the distances from the original
distance matrix. (If not, something is wrong. Check the arithmetic in your
work.)

\smallskip

\itemitem{(e)} You are done processing this node. Do not continue to the
following steps. Go back to the top-level outline on page~1.

\medbreak

\item{3.} [Second special case.] Check to see whether the opportunity matrix
has one or more zeroes that are the only number in their row or the only number
in their column. [This can happen if the opportunity matrix contains~$N$'s from
step~6(b).] If so:

\smallskip

\itemitem{(a)} Choose any such zero in the opportunity matrix. Because this
zero is the only number in its row (or in its column), it represents a link
that {\it must\/} be taken.

\smallskip

\itemitem{(b)} Create a single child node, and assign it the next available
node number.

\smallskip

\itemitemitem{--} The {\it label\/} of the child node is the link that
corresponds to the zero chosen in step~(a). (For example, if that zero is in
the row for city~2 and the column for city~3, then the label of the child node
is ``$2\to3$.'')

\smallskip

\itemitemitem{--} The {\it bound\/} of the child node is the $L$-value of the
opportunity matrix of the node being processed.

\smallskip

\itemitemitem{--} The {\it incoming matrix\/} of the child node is formed from
the opportunity matrix of the node being processed by deleting the row and
column of the chosen zero, and the $L$-value of this incoming matrix is the
$L$-value of the opportunity matrix of the node being processed.

\smallskip

\itemitem{(c)} You are done processing this node. Do not continue to the
following steps. Go back to the top-level outline on page~1.

\vfill\eject

\item{4.} Compute {\it regrets}. Every zero in the opportunity matrix has a
corresponding regret, which is the sum of the smallest other number in that
row (possibly zero) and the smallest other number in that column (possibly
zero).

\medbreak

\item{5.} Choose the largest regret, and call it~$\Rmax$.

\smallskip

\itemitem{(a)} If there is a tie: Choose the one that corresponds to the
smaller distance in the {\it original\/} distance matrix.

\smallskip

\itemitem{(b)} If there is still a tie: Choose arbitrarily.

\medbreak

\item{6.} Create two child nodes, and assign them the next available node
numbers.

\smallskip

\itemitem{(a)} Right child:

\smallskip

\itemitemitem{--} The {\it label\/} of the right child is the link
that corresponds to the regret~$\Rmax$. (For example, if $\Rmax$ came from the
row for city~4 and the column for city~1, then the label of the right child is
``$4\to1$.'')

\smallskip

\itemitemitem{--} The {\it bound\/} of the right child is the $L$-value of the
opportunity matrix of the node being processed.

\smallskip

\itemitemitem{--} The {\it incoming matrix\/} of the right child is formed from
the opportunity matrix of the node being processed by deleting the row and
column of the regret~$\Rmax$, and the $L$-value of this incoming matrix equals
the $L$-value of the opportunity matrix of the node being processed.

\smallskip

\itemitem{(b)} Left child:

\smallskip

\itemitemitem{--} The {\it label\/} of the left child is the ``negation'' of
the label of the right child. (For example, if $\Rmax$ came from the row for
city~4 and the column for city~1, then the label of the left child is
``$4\not\to1$,'' meaning that the link from 4 to~1 will {\it not\/} be used in
the circuit. The textbook uses the notation ``$\sim4\to1$'' instead.)

\smallskip

\itemitemitem{--} The {\it bound\/} of the left child is the $L$-value of the
opportunity matrix of the node being processed, plus~$\Rmax$.

\smallskip

\itemitemitem{--} The {\it incoming matrix\/} of the left child is formed from
the opportunity matrix of the node being processed by replacing the zero
corresponding to~$\Rmax$ with an~$N$ (not an~$M$!), and the $L$-value of this incoming matrix
equals the $L$-value of the opportunity matrix of the node being processed.
[The $N$ enforces the decision not to take that link.]

\smallskip

\itemitem{} Note that the bound of the left child does {\it not\/} equal the
$L$-value of its incoming matrix!

\medbreak

\item{7.} You are done processing this node. Go back to the top-level outline
on page~1.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\bye
