\documentclass[12pt]{article}

\input{cps130}

\begin{document}

\title{Traveling Salesperson (24)}
\author{Michael L. Littman}
\date{December 10th, 1998}

\maketitle 

\section{TRAVELING SALESPERSON PROBLEM}

\subsection{Drilling Holes}

\ni Let's say you are manufacturing printed-circuit boards.  Each
board needs to have a set of holes drilled in it that the components
will later be inserted into.

\ni Your automated driller drills a hole, then moves to the next
location and repeats.  Once all holes are drilled, the circuit board
continues down the assembly line and the next one appears.

\ni Time spent drilling is a constant.  Want to minimize the time
spent in transit between holes!

\ni Example...


\subsection{Traveling Salesperson Problem}

\ni This is an example of the classic traveling salesperson problem.

\ni Formally, we are given a set of $n$ nodes $V$ (points, vertices,
cities, holes), and a distance function $D:V\times V\rightarrow \Re$
giving travel time between any given pair of nodes.

\ni We want to find a {\em tour\/} (Hamiltonian circuit, permutation)
of the nodes $v_1,\ldots,v_n$ such that $\sum_{i=1}^{n-1}
D(v_i,v_{i+1}) + D(v_n,v_1)$ is minimized.  It's the shortest trip
that visits every city once and only once.

% \ni If the distance function $D$ is symmetric ($D(u,v)=D(v,u)$ for all
% $u$ and $v$ in $V$), we call this the {\em undirected\/} TSP.
% Otherwise it is directed.

\ni We'll assume the distance function $D$ is symmetric:
$D(u,v)=D(v,u)$ for all $u$ and $v$ in $V$.

\ni In the {\em metric\/} TSP, we additionally assume that distances
obey the {\em triangle inequality\/}: for all $u$ and $v$ and $w$ in
$V$, $D(u,v) \le D(u,w)+D(w,v)$ (shortcut is never worse).

\subsection{Hamiltonian Circuit}

\ni Before we go after the full-blown TSP, let's look at a related
simpler problem.

\ni Given a graph $G=(V,E)$, a {\em Hamiltonian circuit\/} (vertex
tour) is a non-repeating, all-inclusive sequence of nodes in the graph
that form a path.

\ni The problem HAM is the decision problem: Does $G$ have a
Hamiltonian circuit?

\ni Is HAM in NP?

\subsection{Hardness of HAM}

\ni HAM is NP-complete.  First, we'll show that deciding if a directed
graph has a Hamiltonian circuit is NP-hard.  We'll reduce 3-CNF-SAT to
it.

\ni Idea: We have a widget for each clause and an assignment-selection
gadget that makes us choose Boolean values for each of the variables
one at a time.  We have the option of satisfying a clause and
returning to variable selection.  We must satisfy all clauses and then
complete the loop.

\ni Picture...

\begin{verbatim}
 x   v with loop
o--->o              x   ->   x   ->  x -> y -> y -> y  ...
 \   o
  \->o
 not x
\end{verbatim}

\ni Now, we can turn any undirected instance into a directed instance
by expanding each node into a trio of nodes: for incoming edges,
outgoing edges, and a middle node to force us to go from in to out.
Why do we need the middle node?

\ni Picture...

\subsection{Linking HAM and TSP}

\ni Take the decision problem: Given a TSP instance, is the optimal
tour less than some given size $C$?  It is in NP...

\ni We can reduce HAM to this.  Given an $n$-node graph $G=(V,E)$, we
generate a TSP instance by using the same set of nodes and setting
$D(u,v) = 1$ if $(u,v)\in E$ and $D(u,v) = 2$ otherwise.

\ni This TSP has a tour of size $n$ if and only if $G$ has a
Hamiltonian circuit (otherwise it is at least $n+1$).  So,x if we could
solve TSP in polynomial time, we could solve HAM in polynomial time,
and P would equal NP.


\subsection{Dealing with NP-Completeness}

\ni What do we do now?  TSP is NP-hard.  So, we'd be real surprised if
we could actually solve this both optimally and efficiently in the
worst case.

\ni But, we still need to solve the problem.  People are depending on
us!  What can we do?  Lower our standards!

\ul

\li Find an approximation quickly.

\li Find an optimal solution as quickly as you can (given that we'll
get worst-case exponential-time performance).

\li Try to find a solution quickly that isn't too awful (``empirical
miracle'').

\el


\section{APPROXIMATION}

\subsection{Approximation Idea}

\ni We want an efficient algorithm, just like we've had all along.

\ni Ok, such an algorithm won't be able to find the best tour, but
maybe we can guarantee ourselves to find something that's {\em
close\/} to being optimal.

\ni Idea: Let's say the cost of the truly optimal tour is $\OPT$, but
we find a tour of length $C$.  The {\em ratio\/} $C/\OPT\ge 1$ tells
us how close we are to being optimal (the closer to 1, the better).

\ni We'll give a fast algorithm that produces tours for metric TSP
with a worst-case ratio of 2.  So, we're never further than a factor
of 2 away from optimal!

\subsection{Hardness Results}

\begin{tabular}{|c||c|c|}
\hline
  & {\bf TSP} & {\bf metric TSP} \\
 \hline \hline
ratio of 1 & NP-hard & NP-hard \\
ratio of 2 & NP-hard & polynomial \\
\hline
\end{tabular}

\ni Proved the hardness results for exact metric TSP already (since $2
\le 1 + 1$).

\ni The hardness for a ratio of 2 come from replacing the distance 2
edges with distance $2 n$ edges (violating the ``metric'' property).
Then, if there is a Hamiltonian circuit, the approximation algorithm
would have to give us a tour of length no more than $2 n$.  Such a
tour could only consist of the length 1 edges and, therefore, would
indicate the existence of a Hamiltonian circuit in the original graph.

\subsection{Approximation Algorithm}

\ni Here's what we do.  Given a metric TSP instance with distance
function $D$:

\ul

\li 1. Take $D$ and treat it as the weight function for a weighted
graph.  Compute a minimum spanning tree (MST) of the graph.  Let's say
its cost is $M$.

\li 2. Pick a node in the MST and begin walking along the edges in an
inorder traversal.  Make sure to skip over nodes we've already
visited.

\li 3. Return the list of visited nodes as the tour.

\el

\subsection{Running Time}

\ni We compute an MST on $n^2$ edges: $O(n^2 \log n)$.

\ni We then walk the tree, avoiding duplicates: $O(n)$.

\ni Total: $O(n^2 \log n)$ (not too bad).

\subsection{Analysis of Solution Quality}

\ni This is the interesting part.  How does the tour we find relate to
the optimal tour?

\ni Recall $\OPT$ is the length of the best tour, $M$ is the size of
the MST we found, and $C$ is the length of the tour we return.  Facts:

\ul

\li $M \le \OPT$.  Tour spans nodes.  So, $2 M \le 2\; \OPT$

\li $C \le 2 M$.  Touring the tree is $2 M$, shortcuts only make it smaller.

\li Therefore, $C \le 2 \; \OPT$!  (Ratio of 2.)

\el

\ni So, even though we don't know $\OPT$, we know it can't be too far
away!

\subsection{Other Algorithms}

\ni Other approximation algorithms have been proposed.

\ul

\li One starts with an MST and then uses a matching algorithm to add
some edges to the tree from which we can build a good tour.  Ratio is
3/2 and good tours are found in practice.

\li For TSP in 2-d, there is a dynamic-programming algorithm that
exploits the sequence structure of the tour to find approximations
with arbitrarily good ratios (the ratio shows up in the exponent in
the running time).

\el

% \section{LOWER BOUND}
% 
% TSP via LP:
%  2/3 of true length

\section{OPTIMAL APPROACHES}

\subsection{Idea}

\ni If we really need the absolute best tour, approximation algorithms
are not the way to go.

\ni Instead, we will need to, in essence, check all tours.

\ni We can do this in enumerating all permutations of the nodes.
Running time?

\ans{$n!$.}

\ni More clever schemes can actually get this down to $O(2^n)$.

\subsection{Partial-Tour Graph}

\ni Let's say a {\em partial tour\/} is a graph with no degree-three
nodes and no ``premature'' loops.  That is, it is a subgraph of a
tour.

\ni We can view the space of all partial tours as a big DAG where the
edges connect a partial tour to another partial tour that includes one
additional edge.  The weight of a partial-tour-graph edge is the
weights of the added edge in the graph.

\ni The empty graph is a partial tour with no incoming
partial-tour-graph edges.

\ni What is the out degree of a partial-tour-graph node corresponding
to a complete tour?  What is the length of any path from the empty
graph to a complete tour?

\ans{Complete tour has zero outdegree.  All paths from the empty graph
to a complete tour have $n$ steps.}


\subsection{Shortest Path}

\ni Now, the problem has become one of doing a single-source shortest
path search, which terminates when a complete tour is reached.

\ni We can't actually construct the entire graph, but we can generate
it on an as-needed basis.

\ni Dijkstra's algorithm will only visit as many partial tours as have
weight less than or equal to $\OPT$.  But, that's still pretty
inefficient.

\subsection{Heuristic Search}

\ni Recall that \as\ search gives us a more guided way to search the
graph looking for a shortest path.

\ni Needs an admissible heuristic to get going... that's something
that gives us a lower bound on the distance to the target node.

\ni Here, a target node is any complete tour.

\ni What gives us a lower bound on how the partial tour can be
extended to form a complete tour?  MST!

\ni I actually have no idea if this would be useful... I did see it
mentioned in an AI textbook, though.


\section{HEURISTIC APPROACHES}

\subsection{Motivation}

\ni We've talked about getting a nearly optimal tour fast and getting
a truly optimal tour slowly.

\ni What people actually do in practice is get a not-entirely-stupid
tour in not-too-long time.  Heuristics.

\ni Let your imagination run wild!  Ants, rubber bands, neurons, DNA
computers, you name it!

\subsection{Nearest Neighbor}

\ni Idea: Start at a node.  Find closest unvisited node.  Visit it.
Repeat until finished, then return to start.

\ni Runs fast.

\ni Worst-case ratio of about $1/2 \log n$ (not so good).

\ni Not too bad in practice.

\ni Running time?

\ans{At each step, we need to find the nearest unvisited node.  Keep a
table of which nodes have been visited.  Loop over the unvisited nodes
and keep the min in $O(n)$.  Move and update the table.  Total is
$O(n^2)$.}

\subsection{Greedy}

\ni Kind of like MST algorithm, but works with partial tours.

\ni Start with empty partial tour.  Add smallest edge that results in
a valid partial tour.  Repeat until complete tour reached.

\ni Worst-case ratio no worse than $1/2 \log n$, maybe better.

\ni In practice, performs better than MST-based approximation scheme.

\ni Running time?

\ans{Can sort all edges in $O(n^2\log n)$.  How test quickly for valid
partial tour?  Can keep the standard Kruskal data structure to say
which nodes are linked to which others.  We also keep track of the
number of edges coming out of each node.  We're ok as long as we don't
connect two nodes that already have a path between them (except for
the final edge) and we don't put an edge on a vertex that already has
two.  Like Kruskal's algorithm, this second phase takes $O(n \log n)$,
so $O(n^2\log n)$ is the total.}


\subsection{Local Search}

\ni A more popular approach is {\em local search\/}: we start off with
a valid tour and then use {\em local moves\/} to improve the tour.

\ni Basic hill-climbing algorithm:

\ul

\li Pick a tour (perhaps using the MST approximation).

\li While there is some local move that improves the tour, make it.

\el

\ni Terminates at a ``local minimum.''  Kind of like a ``minimal''
tour in that the only way to improve it is to do something drastic.

\subsection{Some Local Moves}

\ni The $k$-OPT class of moves takes the tour and removes $k$ edges
from it, then reglues the pieces in some other way.

\ul

\li 2-OPT: flips a half tour.  Pretty fast, can get badly stuck.

\li 3-OPT: shuffles thirds.  Slower, less prone to sticking.

\el

\ni Picture...

\ni Theoretically, even in metric TSPs, ratio between $1/4 \;
\sqrt{n}$ and $4 \sqrt{n}$ in the worst case.

\ni Furthermore, it can take $O(2^{n/2})$ moves to get there!

\ni Good performance in practice, though.

\subsection{Other Approaches}

\ni In practice, more sophisticated search strategies are used.

\ul

\li Kernigan-Lin was the champ from 1973 to about 1989.  It is a
variation of 2-OPT that uses a technique to move away from local
minima to get unstuck.

\li Many ``neural net'' approaches have been advocated.

\li Some of the best techniques now are based on genetic search.


\el

\ni Lots of cool variations.



% Can use a splay tree to find a make moves in log n!

\pagebreak

\section{CONCLUSION}

\subsection{Today's Lecture}

Fitting last class, draws on much of what we've learned:

\ul

\li Analysis: Critical for understanding why the problem is so
difficult in the first place!
\li Sorting: Used in Kruskal's algorithm.
\li Statistics: Useful for comparing algorithms empirically.
\li Heap: Used in Dijkstra's algorithm.
\li Binary Search Trees: splay trees provide efficient implementation
of local-search heuristics.
\li Hashing: can map node labels to identifiers.
\li Matching: Important approximation method.
% \li Strings: zzz.
\li Matrix Algorithms: linear programming (which builds on solving
	systems of linear equations) used extensively
	in generating lower bounds. 
\li Graphs: Special type of graph problem, tree walk is a DFS.
\li Minimum Spanning Tree: Simple approximation method.
\li Shortest Paths: Search the graph of partial tours.
\li DP: New approximation schemes for 2-d TSP.
\li Complexity: NP-complete.
\el

\subsection{The Course}

\ni Take Home Lessons: 
\ul

\li  Algorithms matter
\li  Some classic algorithms and their analyses
\li  How to analyze algorithms
\li  How to invent new algorithms
\li  Empirical evaluation of algorithms
\el

\subsection{Thanks!}

\ni I had fun and learned stuff.  I hope you did, too!

\ni Thanks to the UTAs (Mike, Matt, Jimmy, Spence, Iris, Geoff) and TA
(Cheng) for helping makes things run smoothly.



\section{PRACTICE PROBLEMS}

\ul

\li Explain how to use a solution to the bipartite matching decision
problem to find a maximum bipartite matching of a graph.  Hint: First
use a binary search to find the size of the maximum matching, then use
self-reducibility to find the set of edges that attains this value.

% \li CLR Exercise 36.4-6 (pg. 946).

\li CLR Exercise 36.4-7 (pg. 946).

\li CLR Exercise 36.5-2 (pg. 960).

\li Why are those middle nodes needed in the reduction from undirected
HAM to directed HAM?  What would happen if they were omitted?

\li Argue that, in non-metric TSPs, for every ratio $r>1$, there is no
algorithm that can efficiently produce a tour within a ratio bound of
$r$ unless P=NP.


\el


\end{document}



http://www.ing.unlp.edu.ar/cetad/mos/TSPBIB_home.html
