\chapter{Combinatorial Optimization and Heuristics}

Combinatorial optimization is a general class of optimizing problems
restricted to a finite, discrete solution space. 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.

\section{Optimization Algorithms}

In order to solve an optimization problem such as the traveling
salesperson problem (TSP)\footnote{The solution of this problem or
some minor variants of it, would be useful to airlines (for routing
their planes at minimal cost), to telecommunication companies (for
routing information at minimal cost through cables, satellites, local
networks, etc.), to computer chip designers (for placing components on 
a chip such that connection distances are minimized for maximum
operating speed).} or scheduling , we design a series of steps,
or a procedure, which we 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\footnote{Usually we can avoid complications due
to the Halting problem, as we address problems of a simpler nature in
which we are really fighting against NP-completeness and are sure that
a solution does exist.}. 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 judges 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. The reason
NP-complete problems\footnote{See section on NP-completeness.} are
considered difficult is that all known algorithms which guarantee the
optimal solution will operate in exponential time in the size of the
problem in the worst case scenario. 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 looking at 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 extremely important 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 phase
transition is approached. Hence, the phase transition results are also
relevant to the search for good (not just optimal) solutions.

\subsection{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 looked at 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.
\item Such perturbations over all relevant parts of the solution space
  (this is usually naturally satisfied).
\end{enumerate}

All of the algorithms discussed in this thesis fall within this
category, although Mean Field annealing adds few minor requirements to 
this list. 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
  were addressed later in greater 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 represent a possible move we can make between solutions.
For an optimization problem such as scheduling, even if we want to,
we could never hope of writing down the graph of the problem search
space.

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
solution to a ``nearby'' possible solution, 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} \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$.
\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 we get 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=370pt,width=250pt,angle=-90}
\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 hone in 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=360pt,width=200pt,angle=-90}
\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 underscore {\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 assignments. 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).
\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 Salesperson (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?)
\item What if there are ties?
\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 not that great.

\subsection{Local Search Variations}

There are several approaches that take advantage of search strategies
in which cost-deteriorating 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. We formalize this as
follows(see Figure \ref{RS-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 almost always not perform
well. However, another use of random search is as a benchmark --- a
standard level from 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}.

\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) move 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, in
general:
\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 that defines
the neighborhood around a given solution.

We also can view whether hill-climbing works well as an optimization
algorithm in terms of an image of 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', or `capture basin' 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 point. 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 the
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, and
differ mainly in the way a new solution is selected for comparison
with the current solution.

\subsubsection{Simulated Annealing}

(See other chapters for more details) This method is based on the
{\it Metropolis rule} 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
acceptable \cite{AK:anneal}.

\subsubsection{Tabu Search}

Tabu Search (TS) 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}.

\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}

(see Figure \ref{GA-algorithm})
This search strategy 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:
\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 better solutions 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}

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. 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} 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 another chapter.


\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 let 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 almost infinite 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{Computational Complexity}

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{Algorithms and Problems}

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 than 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)$ (complete
enumeration for problems such as TSP takes time $O((n-1)!)$). 

An algorithm may or may not be well behaved. It is well behaved if the 
number of 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.

\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
exponential. 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).}.

\subsection{Characteristic of NP-Complete Problems}

If we pick three different and known NP-complete problems, let say
{\bf Satisfiability}, {\bf Knapsack}, and {\bf Clique}, 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 They come from different fields; logic, number theory, and graph
  theory, respectively.

\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}

\subsection{The Classes P and NP}
Let P be the collection of all problems for which there is a
solution that runs in time bounded by a 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 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.

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$.

\section{More on Design of Heuristics}

How in general 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 algorithm.

In comparison to classic algorithms such as 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 Kernighan-Lin method 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's 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's 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 few possibilities, and we'll 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's
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's 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.

\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.



