\chapter{Combinatorial Optimization and Heuristics}\label{ch:CO}

Unlike many topics in computer science, that of optimization
is something with which we are all familiar with in our everyday
lives, be it through finding the shortest route home from the office,
or arranging a diary to accommodate competing demands on our time each
day. A vast number of such problems, in which the task is to find the
optimal solution amongst a space of possible solutions subject to
external constraints on that choice, arise throughout science,
engineering, and industry. Problems in which the possible solutions
from a finite set are termed {\it combinatorial optimization}
problems. It is a general class of optimizing problems restricted to a
finite, discrete solution space. For this class of problems the
standard function of maximization/minimization techniques of
differential calculus are clearly not applicable. Since the 1940s
however, new developments in mathematics, e.g. linear
programming~\cite{PS:combopt, Sh:linear} and advances in graph 
theory~\cite{Har:graph}, have led to a large body of 
knowledge -- termed {\it operations research} -- concerning these problems 
and methods for their exact or approximate solution.

Combinatorial optimization problems are of great interest in many
fields of research for two reasons. First, from a practical viewpoint,
due to their applicability to real world situations, good answers to
combinatorial problems are often vital to the success or failure of
various projects. Second, from a more theoretical viewpoint, they
represent an intriguing challenge due to their simplicity of statement
coupled with a difficulty of solution. It is because of this
difficulty in attempting to solve many combinatorial optimization
problems that algorithms designed to produce solutions to such
problems are forced to be heuristic in nature, i.e. are not guaranteed
to return the best solution possible. When designing a heuristic
algorithm, the amount of information used that is specific to the
problem can vary. This categorizes algorithms into two arbitrary
groupings: tailored algorithms; that use a lot of problem specific
knowledge and generally applicable algorithms; that seek to minimize
the amount of problem specific information used.

We would like to note that the terms ``energy function'', ``cost'', and 
``objective function'' are used synonymously throughout the thesis.

\section{Concept of Optimization}
Optimization is primarily concerned with determining the
value of a variable that is best for some purpose. This is formalized
as follows: We have an {\it objective function} $f(x,p)$ where $x$ is a
variable to be varied and $p$ represents problem data which is
fixed. The function $f$ evaluates to a number and we assume that $x$
is to minimize this function. Then optimization is to minimize
$f(x,p)$ as a function of $x$. It is often convenient to identify
constraints that must be satisfied by $x$. In principle these can be
incorporated into $f$ but in practice it is often easier to keep them
separated so the optimization problem can then be restated as to
minimize $f(x,p)$ as a function of $x$ subject to the constraints
$c(x,p) = 0$. 

Note that the theory and practice of optimization is very closely
related to that of solving nonlinear equations. For example, the value 
of $x$ that minimizes $f(x,p)$ is one which solves $df(x,p) / dx =
0$. Traditional optimization involves various standard
mathematical functions for $f(x,p)$ and the constraints involved. 

Optimization theory and practice have generated many ideas and
methods. Some of these methods are very general, such as gradient
descent, convex minimization, and penalty functions for
constraints. These can be and have been used in the determination of
``best'' or ``good'' values for the parameters of selection forms. 

\section{Optimization Problems}
Optimization problems are synonymous with search problems, and the
most studied problem involving search is the 
traveling salesman problem (TSP) which is a combinatorial 
optimization problem defined as follows:

The TSP is the problem of finding the shortest closed path around 
a number of points. Formally, each instance is specified by a set of
$N$ points (the `cities') labeled $i = 1,\ldots,N$, and an $N$ X $N$ matrix 
of positive inter-city `distances' $d_{ij}$. Each tour around the
cities can be represented by a permutation $\pi$ of the $N$ points,
with the tour-length given by

\be{TSP.1}
L_{\pi} = \sum_{i=1}^{N} d_{\pi(i) \pi(i+1)}
\ee

where $\pi(N+1) = \pi(1)$. The task is to find the tour with the
minimum $L$.

For symmetric TSPs, i.e. those where $d_{ij} = d_{ji} \forall i, j$,
there are ${1 \over 2}(N - 1)!$ distinct tours, indicating that an
exhaustive search strategy is untenable for large $N$. The symmetric
class can usefully be broken down into the Euclidean and non-Euclidean 
subclasses. In the former, cities are specified by coordinates and the 
$d_{ij}$ are computed in a Euclidean metric, whereas in the latter
class each instance is specified purely by a matrix of $d_{ij}$ terms.

A large number of practical optimization problems can be framed as
TSPs, either directly or indirectly. The 2-D Euclidean TSP, for
example, describes a goods distribution problem in which a truck must
deliver items to a number of locations and then return to the depot,
using the shortest route. Similarly, the question of optimizing the
route of a drill which must produce thousands of holes in a circuit
board can also be seen as a 2-D geometrical TSP. On the other hand,
simple scheduling problems can be represented by non-Euclidean
TSPs. Consider for example the problem of scheduling $N$ jobs, $i = 1
\ldots N$, to run sequentially on a single machine in the shortest
time. Job $i$ requires time $t_i$, plus a lag-time $d_{ji}$ in which
the machine is altered to allow execution of job $i$ after the
previous job $j$. The initial (and final) state can be regarded as a
dummy job, indexed by $0$, with $t_0 = 0$. Representing a schedule by
a permutation $\pi$ of jobs $0 \ldots N$, with $\pi(N+1) = \pi(0)$,
the total run time $T$ equals

\be{TSP.2}
T = \sum_{i=0}^N (d_{\pi(i)\pi(i+1)} + t_{\pi(i)}) = \sum_{i=0}^N
d_{\pi(i)\pi(i+1)} + \sum_{i=0}^N t_i
\ee

As $\sum t_i$ is independent of $\pi$, minimizing $T$ is equivalent to 
an ($N+1$)-city non-Euclidean TSP (which may be either symmetric or
asymmetric).

Further applications, extensions and variations of the basic TSP
formulation can be found in Lawler et al.~\cite{LLRS:tsp}.

\section{Optimization Algorithms}\label{sec:OA}
In order to solve an optimization problem such as, for example, the
TSP or scheduling, we design a series of steps, or a procedure, 
which can tackle a problem instance to which it claims to adhere and, 
ideally, be sure of getting a good answer in a given amount of time. 
Such a procedure is known as an `optimization algorithm'. 

Sometimes we may be happy with (or forced to accept) a less than
optimal solution, in which case it may be easier to find a suitable
algorithm. We would like our algorithms to return as good an answer as
possible in as little time as possible, and these will be important
comparative measures of the merit of different algorithms. Again, this
is more subtle than it seems in that the time will vary from problem
instance to another, and we have to decide whether we want to minimize
the best case, the worst case or the average case. One important thing to 
point out is that many optimization problems are NP-hard
(see~\cite{GJ:candi}); all known algorithms which guarantee
optimal solutions to these problems operate in exponential time 
in the size of the problem in the worst case. For reasonably large 
problem instances this is impractical and so we reduce our expectations 
of the solution from `optimal' to `good', and seek algorithms which can 
still search effectively in these difficult search spaces. As well as
average versus best/worst case in time-requirements, we also want to
understand average versus best/worst case in quality of solution
found.

There were a number of studies discussing the issue of the
distribution of the fitness or ``goodness'' of solutions to a given
problem and the time required to find those solutions. Generally,
those studies were for the idealized cases of complete algorithms
which guarantee the best possible solutions (and therefore, sometimes
take a very large amount of time). However, comparisons of such
complete algorithms with stochastic optimization approaches in studies 
in {\it phase transitions}~\cite{HHW:phase, M:phase} in problem
difficulty have shown empirically that the results are
unchanged~\cite{GW:sat, GW:phase}, and therefore of relevance to some 
of the issues raised in this thesis. Furthermore, such studies 
have shown how the time required to find good solutions by stochastic
algorithms such as Simulated Annealing increases as the 
{\it phase transition} is approached. Hence, the {\it phase transition} 
results are also relevant to the search for good (not just optimal) 
solutions.

\section{Type of problems addressed}

A question to ask here is that: What problems can stochastic
optimization algorithms such as simulated annealing address?

Most of the algorithms we have examined adhere to a simple set of 
requirements upon the space of problems to which they apply. In fact
we require no more of a problem than that:
\begin{enumerate}
\item We can generate a random solution.
\item A `local perturbation' to a solution is defined. `Perturbation' 
means choosing a neighboring point in the search space, and this is 
accomplished by a `perturbation operator'.
\item Such perturbations cover all relevant parts of the solution space
  (this is usually naturally satisfied).
\end{enumerate}

All of the algorithms discussed in this thesis, with some minor
variations, fall within this category. Also note that because we
search directly in the problem space, all the algorithms we consider
will return both the actual solution and its cost (or value of utility
depending upon the context). One can also envisage algorithms which
only return a bound upon the solution cost, and not the actual
solution. Whilst of theoretical value, in most practical instances we
would ordinarily require the solution as well. Finally, it is
important to note that: 

\begin{itemize}
\item Individual problem instances may vary enormously in
  difficulty. The average versus best or worse case difficulty (or
  complexity) of search and problem solving may depend in quite
  particular fashions on the method of problem selection. These issues
  are addressed later in some depth.
\item These algorithms may not specify a natural termination
  condition, and in such cases heuristic principles must be
  used. Possibilities include: maximum running time, solution quality,
  time since last improvement; or combinations thereof.
\end{itemize}

\section{Local Search}

Local search is meant to represent a large class of similar techniques
that can be used to find a good solution from a problem. The idea is
to think of the solution space as being represented by an undirected
graph. That is, each possible solution is a node in the graph. An edge 
in the graph represents a possible move we can make between solutions.
For an optimization problem such as scheduling, even if we want to,
we could never hope to write down the graph of the problem search
space.

Before discussing the idea of local search, we would like to introduce
the concept of local minima, which is a point in the search space where no 
neighboring point has a better value for the objective function. 

Therefore, the simple idea of local search is that we never actually
try to write the whole graph down; we just move from one possible
locally optimal solution to a ``nearby'' possible locally optimal solution 
as well, either for as long as we like, or until we happen to find an 
optimal solution.

To set up a local search algorithm, we need to have the following:
\begin{enumerate}
\item A set of possible solutions, which will be the vertices in our
local search graph.
\item A notion of what the {\it neighbors} of each vertex in the graph 
are. For each vertex $x$, we will call the set of adjacent vertices
$N(x)$. The neighbors must satisfy several properties: $N(x)$ must be
easy to compute from $x$ (since if we try to move from $x$ we will
need to compute the neighbors), if $y \in N(x)$ then $x \in N(y)$ (so
it makes sense to represent neighbors as undirected edges), and $N(x)$ 
cannot be too big, or more than polynomial in the input size (so that
the neighbors of a node are easy to search through).
\item A cost function, from possible solutions to the real
numbers. For example, $f(s^*): {{\cal R}^N} \rightarrow {\cal R}$.
\end{enumerate}

%% The most basic local search algorithm (say to minimize the cost
%% function) is easily described:
%%
%% \begin{enumerate}
%% \item Pick a starting point $x$ in the search space.
%% \item While there is a neighbor $y$ of $x$ with $f(y) < f(x)$, move to 
%% it; that is, set $x$ to $y$ and continue.
%% \item Return the final solution.
%% \end{enumerate}

\subsection{The Reasoning Behind Local Search}
The idea behind local search is clear; if the solution keeps
getting better and better, we should end up with a good
one. Pictorially, if we ``project'' the state space down to a two
dimensional curve, we are hoping that the picture has a sink, or a
{\it global optimum}, and that we will quickly move toward it. See
Figure~\ref{local-search-1}.

%% \vspace{0.1cm}
\begin{figure}[tbp]
\begin{center}
\begin{picture}(370,250)
\psfig{figure=state-space.eps,height=250pt,width=370pt}
\end{picture}
\end{center}
\caption{A very nice state space.}
\label{local-search-1}
\end{figure}

There are two possible problems with this line of thinking. First,
even if the space does look this way, we might not move quickly enough
toward the right solution. Also, for any reasonably large scale
optimization problem, such as scheduling, if we start with a bad
solution (i.e. something with a very large cost), it will take a lot
of moves to reach the minimum. Generally, however, this is not much of
a problem, as long as the cost function is reasonably simple.

The more important problem is that the solution space might not look
at all the way as shown in Figure~\ref{local-search-1}. For example,
our cost function might not change smoothly when we move from a state
to its neighbor. Also, it may be that there are several {\it local
optima}, in which case our local search algorithm will home in to a local 
optimum and get stuck. See Figure~\ref{local-search-2}.

\begin{figure}[tbp]
\begin{center}
\begin{picture}(360,200)
\psfig{figure=local-optima.eps,height=200pt,width=360pt}
\end{picture}
\end{center}
\caption{A state space with many local optima; it will be hard to find 
the best solution. The global optimum ($x^*$) is at the dark circle,
while open circles represent local optima.}
\label{local-search-2}
\end{figure}

The second problem, that the solution space might not ``look nice'',
is crucial, and it underscores {\it the importance of setting up the
problem}. When we choose the possible moves between solutions --- that 
is, when we construct the mapping that gives us the neighborhood of
each node --- we are setting up how local search will behave,
including how the cost function will change between neighbors, and how 
many local optima there are. How well local search will work depends
tremendously on how smart one is in setting up the right
neighborhoods, so that the solution space really does look the way we
would like it to.

\subsection{Examples of neighborhoods}
\begin{itemize}
\item Course Scheduling~\cite{EFC:course, EFC:academic}: A possible
neighborhood structure is two assignments of a set of classes to a set
of rooms over a give set of time slots, if the two assignments differ
only in one class assignment. That is in the first assignment, class
(A) is assigned to room (B) and class (C) is assigned to room (D);
while in the second assignment, class (A) is assigned to room (D) and
class (C) to room (B).

%%---------this probably can be included....
%% \item MAX3SAT~\cite{SY:hard}: A possible neighborhood structure
%% is two truth assignments are neighbors if they differ in only one
%% variable. A more extensive neighborhood could make two truth
%% assignments neighbors if they differ in at most two variables; this
%% trades increased flexibility for increase size in the neighborhood. 

\item Traveling Salesman Problem (TSP)~\cite{JM:traveling}: The k-opt
neighborhood of $x$ is given by all tours that differ in at most $k$
edges from $x$. In practice, using the 3-opt neighborhood seems to
perform better than the 2-opt neighborhood, and using 4-opt or larger
increases the neighborhood size to a point where it is inefficient. 
\end{itemize}

\subsection{Considerations to keep in mind}

There are several aspects of local search algorithms that we can vary, 
and all can have an impact on performance. For example:
\begin{enumerate}
\item What are the neighborhoods $N(x)$?
\item How do we choose an initial starting point?
\item How do we choose a neighbor $y$ to move to? (Do we take the
first one we find, a random neighbor that improves $f$, the neighbor
that improves $f$ the most, or do we use other criteria?)
\end{enumerate}

There are other practical things to consider. Can we re-run the
algorithm several times? Can we try several of the algorithms on
different machines? Issues like these can have a big impact on actual
performance. However, perhaps the most important issue is to think of
the right neighborhood structure to begin with; if this is right, then 
other issues are generally secondary, and if this is wrong, the
likelihood of success is low.

\subsection{Local Search Variations}

There are several approaches that take advantage of search strategies
in which cost-increasing neighbors are accepted. 
In the descriptions of the following search methods, we will
assume we are supplied with a function `FITNESS: $\sum \rightarrow
R$', where $\sum$ is the search landscape or space, which supplies us
with the solution quality. Without loss of generality, we assume
higher fitnesses are better.

\subsubsection{Random Search}

If we don't have enough time to search all possible solutions, we
could just generate solutions randomly for the length of time
available, and retain the best one as our result. 
See Figure~\ref{RS-algorithm} for a sketch of the algorithm.

\begin{figure}[tbp]
{\bf Random Search} ($\Sigma$)
\begin{center}
\begin{enumerate}
\item Pick a random solution $\sigma \in \Sigma$
\item {\bf repeat}
\item $\;\;\;\;$Pick a random solution $\sigma$' $\in \Sigma$
\item $\;\;\;\;$If FITNESS($\sigma$') $>$ FITNESS($\sigma$)
\item $\;\;\;\;\;\;$then $\sigma \leftarrow \sigma$'
\item until No time remains
\item return $\sigma$
\end{enumerate}
\end{center}
\caption{Random Search Algorithm}
\label{RS-algorithm}
\end{figure}

It is quite clear that, unless good solutions are pretty dense in the
search space, a random search will rarely perform
well. However, another use of random search is as a benchmark --- a
standard against which to compare other algorithms and with which
to produce a very simple measure of how difficult a problem is (such
comparisons will never be ideal, however, for at least the reason that
different computer architectures and compilers may have different
levels of performance across different types of computer code).

Choices for termination condition in the random search include time or
solution quality. However since we cannot expect solutions of very
good quality, the only practical condition is on the allowable search
time.

\subsubsection{Hill-climbing}

A simple modification of the random search strategy is to pick
solutions randomly and then examine their neighborhood in the search
space. Viewed graphically, in this method one would move in the search
space to a vertex of lower (or possibly equal) cost. See
Figure~\ref{HC-algorithm} for a sketch of the algorithm.

\begin{figure}[tbp]
{\bf Hill Climbing} ($\Sigma$)
\begin{center}
\begin{enumerate}
\item Pick a random solution $\sigma_{best} \in \Sigma$
\item repeat
\item $\;\;\;\;$Pick a random solution $\sigma \in \Sigma$
\item $\;\;\;\;$repeat
\item $\;\;\;\;\;\;\sigma$' $\leftarrow$ Perturbation($\sigma$)
\item $\;\;\;\;\;\;$ if FITNESS($\sigma$') $>$ FITNESS($\sigma$)
\item $\;\;\;\;\;\;$ then  $\sigma \leftarrow \sigma$'
\item $\;\;\;\;$until No fitter perturbations of $\sigma$ exist
\item $\;\;\;\;$if FITNESS($\sigma$) $>$ FITNESS($\sigma_{best}$)
\item $\;\;\;\;$then $\sigma_{best} \leftarrow \sigma$
\item until No time remains
\item return $\sigma_{best}$
\end{enumerate}
\end{center}
\caption{Hill Climbing Algorithm}
\label{HC-algorithm}
\end{figure}

This algorithm is called hill-climbing\footnote{The term {\it
hill-climbing} implies a maximization problem, but the equivalent {\it 
descent} method is easily envisioned for minimization problems. So for 
convenience, the term hill-climbing will be used here to describe both 
methods without any implied loss of generality.}, because the inner
loop (steps 4-8) moves uphill (not necessarily in the steepest
direction in the basic algorithm) until a summit is reached. The outer
loop (steps 2-11) mean that the algorithm tries to find further hills
if given enough time, and finally returns the highest peak it has
visited when time runs out (this algorithm is sometimes called
`iterated hill climbing' because of the existence of the outer loop).
To use this algorithm we would assume that the perturbation function
is either defined or already given.

There are several weaknesses with hill-climbing algorithms, (assuming 
several rather than a single hill climbing):
\begin{itemize}
\item They usually terminate at solutions that are only locally
optimal.
\item There is no information as to the amount by which the discovered 
local optimum deviates from the global optimum, or perhaps even other
local optima.
\item The optimum that's obtained depends on the initial
configuration.
\item In general, it is not possible to provide an upper bound for the 
computation time.
\end{itemize}

On the other hand, there is one alluring advantage for hill-climbing
techniques: they're very easy to apply. All that's needed is the
representation, the evaluation function, and a measure (i.e. a rule or 
a procedure) that defines the neighborhood around a given solution.

We also can ask whether hill-climbing works well as an optimization
algorithm in terms of an image of a fitness landscape. That is, depending
on the local\footnote{Local being defined by the perturbation
operator.} structure of the landscape. So, if high points 
in the landscape are surrounded by a smooth slopes leading away long
distances in the space, then any points picked on those slopes will
lead to the top of the hill. The set of all such points is known as
the `attracting set' of the peak of the hill. If, on the other hand, tall 
peaks are surrounded by great crevasses then hill climbing will perform poorly. 

Hill-climbing methods, just like all local search methods, use an
iterative improvement techniques, and it is applied to a single point
-- the current point -- in the search space. During each iteration, a
new point is selected from the neighborhood of the current point. If
that new point provides a better value in light of the evaluation
function, the new point becomes the current point. Otherwise, some
other neighbor is selected and tested against the current point. The
method terminates if no further improvement is possible, or we run out
of time or patience.

It's clear that such hill-climbing methods can only provide locally
optimum values, and these values depend on the selection of the
starting points. Moreover, there's no general procedure for bounding
the relative error with respect to the global optimum because it
remains unknown. Given the problem of converging on only locally
optimal solutions, we often have to start hill-climbing methods from a 
large variety of different starting points. The hope is that at least
some of these initial locations will have a path that leads to a
global optimum. We might choose the initial points at random, or on
some grid or regular pattern, or even in the light of other
information that's available, perhaps as a result of some prior search 
(e.g. based on some effort someone else made to solve the same
problem). There are a few versions of hill-climbing algorithms, which
differ mainly in the way a new solution is selected for comparison
with the current solution.

\subsubsection{Simulated Annealing}

Simulated annealing (SA)~\cite{KGV:sim, K:quant} is a method based on the 
{\it Metropolis rule}~\cite{MRRTT:equation} which says: Pick a random neighbor, 
and if the cost is lower, move there. If the cost is higher, move there with
some probability (that is usually set to depend on the cost 
differential). The idea is that possibly moving to a worse state helps
avoid getting trapped at local minima.

With simulated annealing, the difference is that the probability of 
going to a higher cost neighbor varies with time and is gradually
decreased in the course of the algorithm's execution. Lowering the
{\it acceptance probability} is controlled by a set of parameters
whose values are determined by a {\it cooling schedule}. Like most
local search algorithms, simulated annealing is normally used as an
approximation algorithm, for which much faster convergence rates are
achievable \cite{AK:anneal}. 

SA at constant temperature is called the 
{\it Metropolis algorithm}~\cite{MRRTT:equation},
and the stochastic process 
(actually a Markov chain~\cite{F:prob, IM:markov, S:matrices}) on which it is
based is the {\it Metropolis process}. For more details, see chapter~\ref{ch:SA}
on simulated annealing.

\subsubsection{Tabu Search}

Tabu Search (TS)~\cite{GM:tabu, Glover:tabuI, Glover:tabuII,
Glover:tutorial} is based on procedures designed to cross boundaries of
feasibility or local optimality, which were usually treated as
barriers. It is often referred to as a meta-heuristic, and usually
used in conjunction with traditional search techniques to enhance
their performance. It guides a local heuristic search procedure to
explore the solution space beyond local optimality.

Also, TS combines the deterministic iterative improvement algorithm
with a possibility to accept cost-increasing solutions. In this way
the search is directed away from local minima, such that other parts
of the search space can be explored. The next solution visited is
always chosen to be a {\it legal neighbor} of the current solution
with the best cost, even if the cost is worse than that of the current
solution. The set of legal neighbors is restricted by a {\it tabu
list} designed to prevent us going back to recently visited
solutions. The tabu list is dynamically updated during the execution
of the algorithm, and defines solutions that are not
acceptable in the next few iterations. However, a solution on the tabu
list may be accepted if its quality is in some sense good enough, in
which case it is said to attain a certain {\it aspiration level}. See
Figure \ref{TS-algorithm} for sketch of the algorithm.

\begin{figure}[tbp]
\begin{center}
\begin{enumerate}
\item {\bf begin TABU}
\item $\;\;$select an initial solution $i \in S$;
\item $\;\;$initialize tabu list $T$ and aspiration function $A$;
\item $\;\;${\bf while} the {\it stopping condition is not met} {\bf do}
\item $\;\;\;\;$compute the best $i^{'}$ in $N(i)$
\item $\;\;\;\;\;\;$subject to tabu list $T$ and aspiration function $A$;
\item $\;\;\;\;$$i \leftarrow i^{'}$;
\item $\;\;\;\;$update tabu list $T$;
\item $\;\;\;\;$update aspiration function $A$;
\item $\;\;${\bf end while}
\item {\bf end TABU}
\end{enumerate}
\end{center}
\caption{Tabu search paradigm}
\label{TS-algorithm}
\end{figure}

\subsubsection{Genetic Algorithms}

This search strategy, see Figure \ref{GA-algorithm}, is based on a
theme borrowed from Holland's {\it genetic algorithms}
approach~\cite{Hol:adapt, Goldberg:genetic}. Holland uses concepts
from population genetics and evolution theory to construct algorithms
that try to optimize the {\it fitness} of a {\it population} of
elements through {\it recombination} and {\it mutation} 
of their genes. There are many variations known in the literature of
algorithms that follow these concepts. One example is {\it genetic
local search}. The general idea is as follow (see
Figure~\ref{GA-algorithm} for sketch of the algorithm): 
\begin{itemize}
\item Step 1, {\it initialize}. Construct an initial population of $n$ 
solutions.
\item Step 2, {\it improve}. Use local search to replace the $n$
solutions in the population by $n$ local optima.
\item Step 3, {\it recombine}. Augment the population by adding $m$
offspring solutions; the population size now equals $n+m$.
\item Step 4, {\it improve}. Use local search to replace the $m$
offspring solutions by $m$ local optima.
\item Step 5, {\it select}. Reduce the population to its original size 
by selecting $n$ solutions from the current population.
\item Step 6, {\it evolute}. Repeat Step 3 through 5 until a stop
criterion is satisfied.
\end{itemize}
Evidently, {\it recombination} is an important step, since here one
must try to take advantage of the fact that more than local optimum is 
available, i.e., one most exploit the structure present in the
available local optima.

\begin{figure}[tbp]
{\bf Genetic Algorithm} ($\Sigma$)
\begin{center}
\begin{enumerate}
\item Pick a population $P = \{\sigma_1,\ldots,\sigma_n\}$ drawn
  randomly from $\Sigma$
\item repeat
\item $\;\;\;\;$Form a selection:
\item $\;\;\;\;\;$ $S \leftarrow$ Selection($P$, Fitness())
\item $\;\;\;\;$$P \leftarrow \emptyset$
\item $\;\;\;\;$repeat
\item $\;\;\;\;\;\;$Pick a pair $\sigma_a$,$\sigma_b$ from $S$
\item $\;\;\;\;\;\;$Form the offspring:
\item $\;\;\;\;\;\;\;\;$ $\sigma_{ab,1}$,$\sigma_{ab,2}$ $\leftarrow$
  Crossover($\sigma_{a}$,$\sigma_{b}$)
\item $\;\;\;\;\;\;$ $P \leftarrow P \cup
  \{\sigma_{ab,1}$,$\sigma_{ab,2}\}$
\item $\;\;\;\;$until Population is full: $|P| = n$
\item until $P \approx$ converged to a single solution
\item return $\sigma =$ arg $max_{\sigma \in \Sigma}$
  $\{$Fitness($\sigma$)$\}$
\end{enumerate}
\end{center}
\caption{Genetic Algorithm}
\label{GA-algorithm}
\end{figure}

Generally, genetic algorithms depend greatly on the power of
recombination of partial solutions. This begins with a randomly
generated population of feasible solutions, then all tested against
the cost function, and the solutions are kept and used to generate a
new population by reproduction. The reproduction process typically
involves combining features from two or more parent solutions to
produce a child solution. Mutations of individual solutions are
allowed. The key to a good genetic algorithm lies in the design of
good reproduction rules. With effective rules, the next generation
will typically contain some solutions better than the previous one. The
best of these solutions then reproduce to form a new generation, and
so on, until a solution of acceptable quality is found, or successive
generations no longer show significant improvements.

\subsubsection{Artificial Neural Networks}

These consist of networks of elementary nodes (neurons) that are linked
through weighted connections. The nodes represent computational units,
which are capable of performing a simple computation, consisting of a
summation of the weighted inputs, followed by the addition of a
constant called the threshold or bias, and the application of a
nonlinear response function. The result of the computation of a unit
constitutes its output. This output is used as an input for the nodes
to which it is linked through an outgoing connection (see introduction to 
chapter~\ref{ch:ON} for more details). The overall task
of the network is to achieve a certain network configuration, for
instance a required input-output relation, by means of the collective
computation of the nodes. This process is often called {\it
self-organization}. Over the years a large variety of neural network
models have been proposed, which differ in the network architecture and
the computational model used for self-organization. In many models,
the self-organization of the network tries to find a stable network
configuration. For models such as the {\it Hopfield network}
\cite{HT:neural, TH:neural} or the {\it Boltzmann machine}
\cite{AK:anneal}, the self-organization can be modeled in terms  
of local search. Here the issue of escaping from local optima is again
of prime importance. In a number of cases it is resolved by applying
probabilistic methods, as in simulated annealing. This takes us to the
mean field annealing model outlined in chapter~\ref{ch:ON}.

\section{Algorithms, Landscapes, and Problem Classes}

There is much to be learned by examining the interaction between
optimization algorithms and landscapes, both in terms of understanding 
the structure of landscapes, and towards improving the algorithms we
use: as well as phase transitions in problem difficulty, there are
many other robust and interesting structural properties which deserve
further research. One useful approach to the understanding of
algorithms in that context can be obtained by generating landscapes
according to certain rules, and studying the statistical properties of 
the ensemble. So, for example, given a set of statistical properties
of landscapes, one can begin to determine which of these properties
the algorithms would require to perform well.

It is not at all clear on which problem classes these algorithms are
expected to perform well. If we are presented with a new problem
demanding a solution we would like to be able to know a priori which
of these algorithms is expected to perform best. To do this, we need a
formal interpretation of their dynamics, motion in search space and
convergence properties. From these we can derive a set of tests or
summary of inherent advantages and disadvantages which will allow us to
pick the best algorithm for a given purpose. Given that our search
problem is difficult, it is unlikely that a first guess approach will
yield sufficiently good answers (for whatever purpose we had in mind),
so we cannot be happy with that status quo. Somehow the structure of
the search space (the enormous set of possible perturbation
operators and the generated fitness landscapes) is vital in
dictating how the space should be searched efficiently.

In more direct terms, we must think about a process for generating or
transforming solutions in a manner which we intuitively feel takes
into account the deep structure of the problem. In short, without an
understanding of the manner in which optimization algorithms operate,
for every new case we need to invent a new heuristic, or rule of
thumb, which seems particularly relevant. Clearly, this poses great
difficulties for the unfortunate algorithm designer.

%% \section{Combinatorial Optimization}
%% Combinatorial optimization refers to the problem of minimizing a
%% function of a large but finite set of variables. The cost function or
%% energy function $E(\vec{x})$ assigns a real number to each possible
%% state $\vec{x}$ of the system. The configuration space $X$ is given by
%% the finite set of all possible system configurations
%% $\{\vec{x}\}$. The problem is then that of finding the global minimum 
%% of $E(\vec{x})$ over all $\vec{x}$ in $X$.
%%
%% The existence of a large number of local but not global minima of
%% $E(\vec{x})$ in configuration space conspires against the success of
%% heuristic optimization methods. Algorithms such as simulated annealing
%% is an improvement upon downhill algorithms in that it provides a
%% mechanism for getting out of such local minima. It should be noted
%% that while the notion of global minima is an absolute one that depends
%% only on the cost function $E(\vec{x})$, the concept of local minima is
%% relative to the topology since it implies comparing the value of
%% $E(\vec{x})$ with that of $E(\vec{x}^{'})$ for those $\vec{x}^{'}$
%% which are neighbors of $\vec{x}$.
%%
%% The topology of configuration space is defined by the neighbor
%% relation. A natural definition of neighborhood for optimization
%% problems is given by the move set: a small rearrangement of the system
%% that produces a new trial configuration from the present one. Distance
%% $d(\vec{x}, \vec{x}^{'})$ between two states is then defined as the
%% minimum number of moves needed to turn one into other; and the
%% neighborhood of a given state $\vec{x}$ is the set of all states
%% $\vec{x}^{'}$ which can be reached from $\vec{x}$ with one move,
%% i.e. $d(\vec{x}, \vec{x}^{'}) = 1$.

\section{Runtime Estimation of Algorithms}

% An algorithm is a step-by-step procedure for solving a problem.
% A problem can be viewed as a domain of problem instances, with a
% question that can be asked about any of the instances. A problem can
% be described as a generic instances together with a question that can
% be asked about this generic formulation.
% An algorithm $A$ solves a problem $P$ if, given any instance $I$ of
% $P$ as input data, it will generate the answer to $P$'s question. It
% is known that for some problems no algorithm exists (i.e. an algorithm 
% that will generate an answer to the problem's question for all
% instances). In problems like the TSP however, at least one algorithm
% does exist, that of complete enumeration.

When estimating the running time of an algorithm A, `time' is
expressed as a function of the problem size (in the case of the TSP
this is the number of cities $n$), and measures 'steps' rather than the
actual time taken to run the algorithm. Order notation (or O-notation) 
is used to express this running time. If A has a running time of
$O(f(n))$ then there is some constant $c$ such that the algorithm's
running time for all instances is bounded by $c f(n)$, for example, 
complete enumeration for problems such as TSP takes time $O(n!)$. 
For more on order notation, see Cormen et al.~\cite{CLR:algorithms}.

An algorithm may or may not be well behaved. It is well behaved if the 
number of computational steps required can be accurately predicted for 
a given problem instance, and this prediction does not vary from one 
instance to another with the same size. Some algorithms however are not 
well behaved and the number of steps required to solve problem instances of 
the same size can vary widely. Assigning a complexity function to a
problem requires a unique 'time' value for each problem size. There
are two approaches in measuring how long an algorithm takes. Either
the average or the maximum number of steps can be counted over all
instances of the same size. The second form of measurement,
worst-case-analysis, has the disadvantage that bad performances might
be very rare in practice. Average-case analysis involves choosing a
probability function for the instances of the same size, a potentially 
difficult task. Another difficulty of average-case analysis is the
dependence between the stages of many algorithms, making statistical
analysis complicated. Generally, when evaluating a problem instance
the average running time is not really an issue, but through
worst-case analysis there is at least guarantee of how long it will
take. The worst-case approach leads to the theory of 
NP-completeness~\cite{GJ:candi}.

\subsection{Polynomial Time}

An algorithm is considered `good' when it is efficient enough to use
in practice. Here efficiency is defined as having worst-case
complexity bounded by a polynomial function of the problem size
$n$. This splits algorithms into two distinct classes, polynomial and
non-polynomial. Although exponential algorithms may do better than
polynomial algorithms for small $n$, exponential algorithms will
perform much worse than polynomial algorithms as the problem size
increases. 

The precise definition of problem size can have a large bearing on the 
function derived for the worst-case complexity. But as long as the
size is a measurement in some sense of the problem dimension, a
polynomial algorithm will remain polynomial and an exponential
algorithm will remain exponential, regardless of the choice of the
definition\footnote{The theory requires that the measure of input size 
must reflect (to within a polynomial) the actual length of a concise
encoding of the problem instance as a sequence of symbols (i.e. as it
would be stored in a computer)~\cite{PS:combopt}.}.

%% \section{Computational Complexity}\label{sec:NP}
%%
%% Computational complexity was developed largely in the 1970s to
%% evaluate whether algorithms should be classified as `easy' or
%% `hard'. Parker and Rardin \cite{PR:discrete} define the goal of
%% complexity theory as:
%%
%% ``$\ldots$seeking to classify problems in terms of the mathematical
%% order of the computational resources required to solve the problems
%% via digital computer algorithms.''
%%
%% Combinatorial optimization has given computational complexity many
%% motivations and insights and has served as a test-bed for many new
%% algorithmic ideas. 
%%
%% \subsection{The Classes P and NP}
%% Let P (stands for polynomial-time) be the collection of all problems 
%% for which there is a solution that runs in time bounded by a 
%% {\it polynomial} function of the size of the problem. For example, 
%% you can determine whether an item is
%% in a list in time proportional to the size of the list (simply by
%% examining each element in the list to determine whether it is the
%% correct one), and you can sort all items in a list into ascending
%% order in time bounded by the square of the number of elements in the
%% list (using, for example, the well-known bubble sort algorithm.) There
%% may also be faster solutions; that is not important here. Both the
%% searching problem and the sorting problem are in P because they
%% can be solved in time $n$ and $n^2$, respectively.
%%
%% For most problems, polynomial time algorithms are about the
%% limit of feasible complexity. Any problem that could be solved in time
%% $n^{1,000,000,000}$ would be in P, even though for large values
%% of $n$, the time to perform such an algorithm might be
%% prohibitive. Notice also that we do not have to know an explicit
%% algorithm, we just have to be able to say that such an algorithm
%% exists.
%%
%% By contrast, let NP (the initials stand for nondeterministic 
%% polynomial-time) be the set of all problems that can be solved in 
%% time bounded by a polynomial function of the size of the problem, 
%% {\it assuming the ability to guess perfectly} 
%% (in the literature, this ``guess function'' is called an oracle machine
%% or a nondeterministic Turing machine.) This guessing is called
%% nondeterminism. For more background on this concept, see~\cite{GJ:candi}.
%%
%% Of course, no one can guess perfectly. Guessing is simulated by
%% cloning an algorithm and applying one version of it to each possible
%% outcome of the guess. Essentially, the idea is equivalent to a
%% computer programming language in which IF statements could be replaced
%% by GUESS statements: instead of testing a known condition and
%% branching depending on the outcome of the test, the GUESS statements
%% would cause the program to fork, following two or more paths
%% concurrently.
%%
%% The ability to guess can be useful. For example, instead of deciding
%% whether to assign the value TRUE or FALSE to variable $v_1$, the
%% nondeterministic algorithm can proceed in two directions: one assuming
%% TRUE had been assigned to $v_1$, and the other assuming FALSE. As the
%% number of variables increases so does the number of possible paths to
%% be pursued concurrently.
%%
%% Certainly every problem in P is also in NP because the
%% guess function does not have to be invoked. There is also a class
%% EXP, which consists of problems for which a deterministic
%% solution exists in exponential time, $c^n$ for some constant $c$. As
%% noted earlier, every NP-complete problem has such a solution. Every
%% problem in NP is also in EXP so P $\subseteq$ NP $\subseteq$ EXP.
%%
%% \subsection{The Meaning of NP-Completeness}
%%
%% The notion of NP-completeness tries to capture the ``hardest''
%% problems in the class NP. In other words, the way the class of
%% NP-completeness is defined, if ever we were able to find a
%% polynomial time algorithm for Q, an NP-complete problem, we can
%% then find a polynomial time algorithm for any problem X that is in the 
%% class NP (and hence for every NP-complete problem). This
%% follows by the definition of NP-completeness.
%%
%% Stephen Cook~\cite{C:complexity} showed that the satisfiability
%% problem is NP-complete, meaning that it can represent the entire
%% class NP. His important conclusion was that if there is a
%% deterministic, polynomial time algorithm (one without guesses)
%% for the satisfiability problem, then there is a deterministic,
%% polynomial time algorithm for every problem in NP; that
%% is, P = NP.
%%
%% Richard Karp~\cite{K:reduce} extended Cook's
%% result~\cite{C:complexity} by identifying several other problems, all
%% of which shared the property that if any one of them could be
%% solved in a deterministic manner in polynomial time, then all of them
%% could. The knapsack and clique problems were identified by Karp. The
%% results of Cook and Karp included the converse: if for even one
%% of these problems (or any NP-complete problem) it could be shown that
%% there was no deterministic algorithm that ran in polynomial
%% time, then no deterministic algorithm could exist for any of
%% them.
%% 
%% Be careful to distinguish between a problem and an instance of a
%% problem. An instance is a specific case: one formula, one
%% specific graph, or one particular set S. Certain simple graphs or
%% simple formulas may have solutions that are very easy and fast to
%% identify. A problem is more general; it is the description of
%% all instances of a given type. For example, the formal statements of
%% the satisfiability, knapsack, and clique sections are statements of
%% problems because they tell what each specific instance of that problem
%% must look like. Solving a problem requires finding one general
%% algorithm that will solve every instance of that problem.
%%
%% There are problems known to be solvable deterministically in
%% polynomial time (P), and there are problems known not to
%% have a polynomial time solution (EXP and beyond), so that P
%% $\subseteq$ EXP and P $\neq$ EXP, meaning P $\subset$ EXP. The class
%% NP fits somewhere between P and EXP: P $\subseteq$ NP $\subset$
%% EXP. It may be that P = NP, or that P $\neq$ NP.
%%
%% The significance of Cook's result is that NP-complete problems have
%% been studied for a long time by many different groups of people:
%% logicians, operations research specialists, electrical engineers,
%% number theorists, operating systems specialists, and communications
%% engineers. If there were a practical (polynomial time) solution to any
%% one of these problems, you would hope that someone would have found it
%% by now. See Garey and Johnson's N-completeness catalog~\cite{GJ:candi}.
%%
%% \subsubsection{Polynomial-time Reduction}
%%
%% Let $\Pi$ and $\Pi^{'}$ be two problems and let $A$ be an
%% algorithm. We say that $A$ is a {\it polynomial-time reduction} of
%% $\Pi^{'}$ to $\Pi$ if $A$ is a polynomial-time algorithm (`solving'
%% $\Sigma^{*}$), so that any allowed sequence starting with $w$ and
%% ending with $v$ one has: $w \in \Pi^{'}$ if and if $v \in \Pi$. A
%% problem $\Pi$ is called NP-complete, if $\Pi \in$ NP and for each
%% problem $\Pi^{'}$ in NP there exists a polynomial-time reduction of
%% $\Pi^{'}$ to $\Pi$. It is not difficult to see that if $\Pi$ belongs
%% to P and there exists a polynomial-time reduction of $\Pi^{'}$ to
%% $\Pi$, then also $\Pi^{'}$ belongs to P. It implies that if one
%% NP-complete problem can be solved in polynomial time, then each
%% problem in NP can be solved in polynomial time. Moreover, if $\Pi$
%% belongs to NP, $\Pi^{'}$ is NP-complete and there exists a
%% polynomial-time reduction of $\Pi^{'}$ to $\Pi$, then also $\Pi$ is
%% NP-complete.
%%
%% \section{Approximation Algorithms}
%%
%% When facing an NP-complete optimization, we may want to consider
%% algorithms that do not produce optimum solutions, but solutions {\it
%%   guaranteed to be close to the optimum}. Suppose that we wish to
%% obtain such solutions for an optimization problem, maximization or
%% minimization. For each instance $x$ of this problem, there is an
%% optimum solution with value $opt(x)$; let us assume that $opt(x)$ is
%% always a positive integer.
%%
%% Suppose now that we have a polynomial algorithm $A$ which, when
%% presented with instance $x$ of the optimization problem, returns some
%% solution with value $A(x)$. Since the problem is NP-complete and
%% $A$ is polynomial, we cannot realistically hope that $A(x)$ is always
%% the optimum value. But suppose that we know that the following
%% inequality hold:
%%
%% \be{appr}
%% {{|opt(x) - A(x)|} \over {opt(x)}} \leq \epsilon
%% \ee
%%
%% where $\epsilon$ is some positive real number, hopefully very small,
%% that bounds from above the worst-case relative error of algorithm $A$.
%% (The absolute value in this inequality allows us to treat both
%% minimization and maximization problems within the same framework.) If
%% algorithm $A$ satisfies this inequality for all instances $x$ of the
%% problem, then it is called an $\epsilon$-approximation algorithm.
%%
%% Once an optimization problem has been shown to be NP-complete,
%% the following question becomes most important: Are there
%% $\epsilon$-approximation algorithms for this problem? And if so, how
%% small can $\epsilon$ be? Let us observe at the outset that such
%% questions are meaningful only if we assume that P $\neq$ NP,
%% because, if P = NP, then the problem can be solved exactly, with
%% $\epsilon = 0$.
%%
%% \subsection{Characteristic of NP-Complete Problems}
%% 
%% If we pick three different and known NP-complete problems, let say
%% {\bf Satisfiability}~\cite{GJ:candi}, {\bf Knapsack}~\cite{GJ:candi}, and 
%% {\bf Clique}~\cite{GJ:candi}, we would notice the following characteristics 
%% about them. 
%% \begin{itemize}
%% \item Each is solvable, and a relatively {\it simple} approach solves
%%  it (although the approach may be time-consuming). For each of them,
%%  we can simply enumerate all the possibilities: all ways of assigning
%%  the logical values of $n$ variables, all subsets of the set $S$, all
%%  subsets of $n$ vertices in $G$. If there is a solution, it will
%%  appear in the enumeration of all possibilities; if there is no
%%  solution, testing all possibilities will demonstrate that.
%%
%% \item There are $2^n$ cases to consider if we use the approach of
%%  enumerating all possibilities (where $n$ depends on the
%%  problem). Each possibility can be tested in a relatively small
%%  amount of time, so the time to test all possibilities and answer
%%  {\it yes} or {\it no} is proportional to $2^n$.
%%
%% \item If it were possible to guess perfectly, we could solve each
%%  problem in relatively little time. For example, if someone could
%%  guess the correct assignment or the correct subset, we could simply
%%  verify that the formula had been satisfied or a correct sum had been
%%  determined, or a clique had been identified, etc. The verification
%%  process could be done in time bounded by a polynomial of the size of
%%  the problem.
%% \end{itemize}

\section{More on Design of Heuristics}

How in general do we go about designing or just applying an existing
algorithm for a particular purpose? Looking at the algorithms
previously outlined in this chapter, we see that they are derived from
a wide array of fields of knowledge \cite{AL:local} but share the same
design goals.

For example, simulated annealing and tabu search are both designed for
the purpose of escaping local optima, but differ in the methods used
for achieving this goal. Tabu search usually makes uphill moves only
when it is stuck in local optima, whereas simulated annealing can make
uphill moves at any time. Also, SA is stochastic whereas tabu search
is deterministic.

In comparison to classic algorithms such as for example greedy, divide 
and conquer, simplex method, and dynamic programming, both SA and TS work
on complete solutions. In addition, SA and TS have more parameters to
worry about, such as temperature, rate of reduction, size of memory,
etc. than those classic methods. When dealing with methods such as SA,
one would have to think not only whether the algorithm makes sense for
the given problem but also how to choose the parameters of the
algorithm so that it performs optimally. This is quite pervasive issue
that accompanies the vast majority of algorithms that can escape local
optima.

In addition to these general purpose optimization methods there are
also specific heuristics, such as the Kernighan-Lin
method~\cite{JM:traveling, LK:heuristic, KL:heuristic} used to tackle
problems such as TSP and graph partitioning. 

It is not at all clear on which problem classes these algorithms are
expected to perform well. If we are presented with a new problem
demanding a solution, we would like to be able to know a priori which
of these algorithms is expected to perform best. To do this, we need a 
formal interpretation of their dynamics, motion in search space and
convergence properties. From these we can derive a set of tests or
summary of inherent advantages and disadvantages which will hopefully
help us in picking the best algorithm for a given purpose.

It is known that effective search techniques provide a mechanism for
balancing two apparently conflicting objectives: {\it exploiting} the
best solutions found so far and at the same time {\it exploring} the
search space.\footnote{This balance between exploration and
exploitation was noted as early  as the 1950s by the famous
statistician G.E.P. Box~\cite{BV:exp}.} Hill-climbing methods exploit
the best available solution for possible improvement but neglect
exploring a large portion of the search space S. In contrast, a random
search -- where points are sampled from S with equal probabilities --
explore the search space thoroughly but foregoes exploiting promising
regions of the space. Each search space is different and even
identical spaces can appear very different under different
representations and evaluation functions. So there is no way to
choose a single search method that can serve well in every case. 

Getting stuck in local optima is a serious problem. It is one of the
main deficiencies that plague industrial applications of numerical
optimization. Almost every solution to real-world problems in factory
scheduling, academic scheduling, airline scheduling, demand
forecasting, land management, and so forth, is at best only locally
optimal. 

What can we do? How can we design a search algorithm that has a chance 
to escape local optima, to balance exploration and exploitation, and
to make the search independent from the initial configuration? There
are a few possibilities, and we will discuss our approaches in the upcoming
chapters, but keep in mind that the proper choices are always problem
dependent. One option is to execute the chosen search algorithm for a
large number of initial configurations of the problem. Moreover, it is
often possible to use the results of previous trials to improve the
choice of the initial configuration for the next trial. It might also
be worthwhile to introduce a more complex means for generating new
solutions, or enlarge the neighborhood size. It is also possible to
modify the criteria for accepting transitions to new points that
correspond with a negative change in the evaluation function. That is, 
we might want to accept a worse solution from the local neighborhood
in the hope that it will eventually lead to something better. 

%% For more interesting ideas on problem solving heuristics,
%% see~\cite{MF:heuristics}. 

%% \section{Algorithmic paradigms}
%%
%% Heuristic algorithms seek good solutions to problems without providing 
%% any guarantee of optimality. Also, they generally fall into one three 
%% classes: construction algorithms, (partial) enumeration techniques,
%% and iterative improvement methods. Construction algorithms operate by
%% starting with an initial partial solution\footnote{A partial solution
%% to a problem requires that a full solution be composed of a number of
%% separate components. Taking a subset of these solution components
%% results in a partial solution which can become a full solution to the
%% problem if it is extended or enlarged in a suitable manner.},
%% iteratively augmenting it in an appropriate way to finally produce a
%% full solution to the problem at hand. Enumeration techniques apply a
%% more brute force approach to achieve their goals, searching through a
%% list of solutions to find the best solution to the problem. Although
%% the size of the solution space for most interesting combinatorial
%% optimization problems prevents full enumeration from being a viable
%% option, by excluding regions of the solution space, the list of
%% enumerated solutions can be greatly reduced making such a partial
%% enumeration algorithms more manageable. Iterative improvement
%% algorithms begin with an initial solution to the problem and
%% iteratively attempt to find a better solution by altering the current
%% solution in some manner while (generally) maintaining feasibility. The 
%% iterative process generally terminates when no better solution can
%% easily be obtained.
%%
%% Each of the above algorithmic paradigms has strengths and weaknesses
%% largely depending on the problem to which the technique is
%% applied. For example there are some optimization problems where
%% iterative improvement algorithms are hopelessly inadequate, and yet
%% other problems where the reverse holds true.
%%
%% For both exact and heuristic algorithms the distinction can be made
%% between general and tailored algorithms. A tailored algorithm uses
%% problem-specific information and can only be applied to a small set of 
%% problems, requiring the development of a new algorithm for each type
%% of combinatorial optimization problem. Conversely, general algorithms
%% are largely problem independent and will work for any number of
%% different problem types. As with exact and heuristic algorithms, trade 
%% off is generally encountered. Either a tailored algorithm can be used, 
%% which makes use of problem structure and is comparatively quick but
%% has limited applicability, or a general algorithm can be used, which
%% is usually slower but has a wide potential for application. In this
%% thesis, the emphasis is on generally applicable heuristic algorithms,
%% particularly, annealing-based methods.

\section{Conventional Methods}

Despite the negative news from the computational complexity front
regarding problems such as TSP, a variety of approaches has been
developed which usually offer a trade-off between solution quality and 
running time for practical problems. This reflects the fact that the
complexity results just discussed are {\it worst-case} results, which
may, of course be unrelated to the average-case behavior. This section 
briefly sketches a few of the approaches commonly cited in the
operations research literature for tackling problems such as
scheduling and TSP. 

\subsection{Cutting plane techniques}

Exact approaches to combinatorial optimization divide into two main
classes. First, there are {\it cutting plane} techniques, originally
due to Gomory~\cite{GOM:outline}. From an integer linear programming
perspective, the idea behind this method is to successively add extra
constraints which reduce the size of the constraint polytope, without
excluding any feasible integer points. After each new constraint (or
{\it cut}) has been added, the LP-relaxation solution is found using
the simplex algorithm. At each step, either the LP-relaxation is an
integer, at which point the problem is solved, or else the
LP-relaxation solution is used to generate a new cut. Cutting plane
algorithms describe how to generate cuts so that no feasible points
are excluded at each cut, and so that the algorithm converges in a
finite (exponentially bounded) number of steps. For more details on
these algorithms, see for example~\cite{PS:combopt}.

\subsection{Branch-and-bound}

In addition to cutting plane techniques, there are the {\it
enumerative} methods, based on intelligent enumeration of all feasible 
solutions. The most common enumerative procedure is {\it
branch-and-bound}, well surveyed up to 1966 in~\cite{LW:branch}. At
each stage of the branch-and-bound procedure, the set of possible
solutions is partitioned into ever smaller mutually exclusive sets:
this is the {\it branch} operation. An efficient algorithm is then
used to compute a lower bound on the cost of any solution in each set: 
this is the {\it bound} operation. As the sets become smaller, and
clearly in the limit of the sets containing only a single solution, it 
becomes possible to identify the best feasible solution in a set: at
this point exploration of this set can cease. Also, exploration of a
set can be halted if the lower bound is inferior to any feasible
solution found so far. Eventually it is possible to stop exploring all 
the remaining solution sets, for one of the above two reasons. At this 
point the problem is solved, since the best feasible solution found
must be the optimal solution to the problem. The branch-and-bound
algorithm provides a way of enumerating all feasible solutions without 
having to consider each and every one. However, this can still take
some time, and it is often necessary to terminate the
branch-and-bound algorithm before optimality is reached. In such a
situation a lower bound on the optimal solution is available, as well
as the best solution found so far, so the maximum error from the
optimum can be bounded.

\subsection{Dynamic programming}

Another enumerative technique is {\it dynamic programming}, which is
comprehensively surveyed in~\cite{Dreyfus:art}. Before the method can
be applied, the problem must be posed as a multi-stage decision
process: a process in which a sequence of decisions is made, the
choices available being dependent on the previous decisions. Dynamic
programming exploits the {\it principle of optimality}: An optimal
sequence of decisions has the property that whatever the initial state 
and initial decision are, the remaining decisions must be an optimal
sequence of decisions with regard to the state resulting from the
first decision~\cite{RND:combalg}.
Essentially, this means that solutions to subproblems can be used to
prune the search for solutions to larger subproblems, and finally to
the problem itself. Dynamic programming works well with many common
problems, providing, for example, a pseudo-polynomial time algorithm
for the knapsack problem~\cite{GJ:candi}. 

In practice, enumerative methods have found many more applications than 
cutting plane methods. Full descriptions of all these approaches can
be found in integer programming texts~\cite{Hu:integer, GN:integer,
Sh:linear, SM:foundations}, or more general combinatorial optimization 
texts~\cite{NW:icopt, RND:combalg, PS:combopt}.
