%% LATEX TWICE TO GET THE REFERENCES RIGHT
%%
%% \documentstyle[11pt,psfig]{article}        
%%
\documentstyle[12pt,epsf,psfig]{article}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% macro for postscript figures - the easy way.
%% See directory ftp.cis.ufl.edu/tech report by fishwick@cis.ufl.edu 
%% This will help to control the size of the figure.
%%
\newcommand{\postscript}[2]
 {\setlength{\epsfxsize}{#2\hsize}
  \centerline{\epsfbox{#1}}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newtheorem{theorem}{Theorem}
\newtheorem{itlemma}{Lemma}[section] %number by section (set in \em by default)
%%%same numbering counter as itlemmas:
\newtheorem{itproposition}[itlemma]{Proposition}
\newtheorem{itcorollary}[itlemma]{Corollary}
\newtheorem{itremark}[itlemma]{Remark}
\newtheorem{itnote}[itlemma]{Note}
\newtheorem{itobservation}[itlemma]{Observation}
\newtheorem{itdefinition}[itlemma]{Definition}
\newtheorem{itexercise}[itlemma]{Exercise}
\newtheorem{itexample}[itlemma]{Example}

\newenvironment{lemma}{\begin{itlemma}\rm}{\end{itlemma}} %no-italics
\newenvironment{remark}{\begin{itremark}\rm}{\end{itremark}} %no-italics
\newenvironment{observation}{\begin{itobservation}\rm}{\end{itobservation}} %no-italics
\newenvironment{corollary}{\begin{itcorollary}\rm}{\end{itcorollary}}
\newenvironment{proposition}{\begin{itproposition}\rm}{\end{itproposition}}
\newenvironment{definition}{\begin{itdefinition}\rm}{\end{itdefinition}}
\newenvironment{exercise}{\begin{itexercise}\rm}{\end{itexercise}}
\newenvironment{example}{\begin{itexample}\rm}{\end{itexample}}

\tolerance=1600 %allow some tolerance in extending after line.
\parskip=3pt plus 1pt minus 1pt
\overfullrule=0pt %no dark lines if overfull

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% This are for choices.  They take 4 or 6 args
%% (carriage returns allowed in between)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\twoif}[4]{
\left\{ \begin{array}{ll}#1&#2\\#3&#4\end{array}\right.
}
\newcommand{\threeif}[6]{
\left\{ \begin{array}{ll}#1&#2\\#3&#4\\#5&#6\end{array}\right.
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\partmlab#1#2#3#4#5#6#7#8{\bordermatrix{&#1&#2\cr#3&#5&#6\cr
					\noalign{\medskip}#4&#7&#8\cr}}
%% For 2by2 partitioned matrices; arguments are: two labels of top, side,
%% 4 entries (row by row).  If entries are themselves matrix or pmatrix,
%% better for readability of source to define first: \def\matrix1{...} etc.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\bigframebox}[1]{\framebox{\parbox{\smallerwidth}{#1}}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Warning: use \noindent before!
% AND IN TEXT, after begin doc, do:
% \newlength{\smallerwidth}  %for bigboxes
% \setlength{\smallerwidth}{\textwidth}
% \addtolength{\smallerwidth}{-8pt}        %MUST BE DONE AFTER begin doc
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def \beq {\begin{eqnarray}}
\def \eeq {\end{eqnarray}}
\def \beqn {\begin{eqnarray*}}
\def \eeqn {\end{eqnarray*}}

\newcommand{\rf}[1]{[\ref{#1}]}            %bibliographical references

\newcommand{\text}[1]{\hbox{\rm \ #1\ \/}}
\newcommand{\be}[1]{\begin{equation}\label{#1}}
\newcommand{\ee}{\end{equation}}
\newcommand{\bl}[1]{\begin{lemma}\label{#1}}
\newcommand{\ble}[1]{\begin{lemmaex}\label{#1}}
\newcommand{\br}[1]{\begin{remark}\label{#1}}
\newcommand{\bn}[1]{\begin{note}\label{#1}}
\newcommand{\bo}[1]{\begin{observation}\label{#1}}
\newcommand{\bt}[1]{\begin{theorem}\label{#1}}
\newcommand{\bd}[1]{\begin{definition}\label{#1}}
\newcommand{\bp}[1]{\begin{proposition}\label{#1}}
\newcommand{\bc}[1]{\begin{corollary}\label{#1}}
\newcommand{\bfact}[1]{\begin{fact}\label{#1}}
\newcommand{\ber}[1]{\begin{exercise}\label{#1}}
\newcommand{\bex}[1]{\begin{example}\label{#1}}
\newcommand{\bem}[1]{\begin{example}\label{#1}}    %Yes, 2 different ones...
\newcommand{\ec}{\mybox\end{corollary}}
\newcommand{\efact}{\mybox\end{fact}}
\newcommand{\eer}{\mybox\end{exercise}}
\newcommand{\eex}{\mybox\end{example}}
\newcommand{\eem}{\mybox\end{example}}
\newcommand{\el}{\mybox\end{lemma}}
\newcommand{\ele}{\mybox\end{lemmaex}}
\newcommand{\er}{\mybox\end{remark}}
\newcommand{\en}{\mybox\end{note}}
\newcommand{\eo}{\mybox\end{observation}}
\newcommand{\et}{\qed\end{theorem}}
\newcommand{\ed}{\mybox\end{definition}}
\newcommand{\ep}{\mybox\end{proposition}}
\newcommand{\epr}{\end{proof}}
\newcommand{\bpr}{\begin{proof}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%  These are just for statements, no "qed" box is put in.
%%  (Also for when I have to finish something after a displayed equation
%%        or itemized.)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\ecs}{\end{corollary}}
\newcommand{\eers}{\end{exercise}}
\newcommand{\eexs}{\end{example}}
\newcommand{\eems}{\end{example}}
\newcommand{\els}{\end{lemma}}
\newcommand{\eles}{\end{lemmaex}}
\newcommand{\ers}{\end{remark}}
\newcommand{\ens}{\end{note}}
\newcommand{\eos}{\end{observation}}
\newcommand{\ets}{\end{theorem}}
\newcommand{\eds}{\end{definition}}
\newcommand{\eps}{\end{proposition}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\qed}{\hfill \halmos} %put \qed at right margin
\newcommand{\mybox}{\hfill $\Box$} %put \qed at right margin (white square)

%%%\newcommand{\pmat}[2]{\left( \begin{array}{#1} #2 \end{array} \right) }
%%%use as e.g. \pmat{cc}{ a&b\\ a &c }  Note 'cc' for 2 Centered cols
%%%can also use \pmatrix{ a&b\cr a &c \cr} for plainTeX standard construct
%%%\setcounter{page}{27} should set the CURRENT page to 27

\def \R {\bb R} % reals
\def \C {\bb C} % complexes
\def \Z {\bb Z} % integers
\def \X {\bb X} % for this paper only!
\def \inter {{\rm int \,}}
\def \rank {{\rm rank \,}}

%%%\def \inf {{\rm inf \,}}  %better in Latex -- subscripts OK!
%%%\def \min {{\rm min \,}}

\def \im {{\rm im \,}}
\def \ker {{\rm ker \,}}
\def \norm #1{\Vert #1 \Vert}
\def \ip #1\by #2{\langle #1 , #2 \rangle}
\def \Sone {{\bf S}^1} % circle
\def \wigglearrow {\sim \mkern -6mu >}

\def \today {\ifcase \month \or January\or February\or  
  March\or April\or May\or June\or July\or August\or 
  September\or October\or November\or December\fi\   
  \number \day, \number \year}                       
\newcommand{\comment}[1]{}
\newcommand{\halmos}{\rule{1ex}{1.4ex}}
%%%alternative to \qed (see below)
\newenvironment{proof}{\noindent {\em Proof}.\ }{\hspace*{\fill}$\halmos$\medskip}

%%%\def\qed{\kern 1em \vrule height .5em width .5em depth 0em}
%%%(I now use new qed: in right margin)

\def\vbar{\mathchoice{\vrule height6.3ptdepth-.5ptwidth.8pt\kern-.8pt}
   {\vrule height6.3ptdepth-.5ptwidth.8pt\kern-.8pt}
   {\vrule height4.1ptdepth-.35ptwidth.6pt\kern-.6pt}
   {\vrule height3.1ptdepth-.25ptwidth.5pt\kern-.5pt}}
\def\fudge{\mathchoice{}{}{\mkern.5mu}{\mkern.8mu}}
\def\bbc#1#2{{\rm \mkern#2mu\vbar\mkern-#2mu#1}}
\def\bbb#1{{\rm I\mkern-3.5mu #1}}
\def\bba#1#2{{\rm #1\mkern-#2mu\fudge #1}}
\def\bb#1{{\count4=`#1 \advance\count4by-64 \ifcase\count4\or\bba A{11.5}\or
   \bbb B\or\bbc C{5}\or\bbb D\or\bbb E\or\bbb F \or\bbc G{5}\or\bbb H\or
   \bbb I\or\bbc J{3}\or\bbb K\or\bbb L \or\bbb M\or\bbb N\or\bbc O{5} \or
   \bbb P\or\bbc Q{5}\or\bbb R\or\bbc S{4.2}\or\bba T{10.5}\or\bbc U{5}\or

%%%   \bbb P\or\bbc Q{5}\or\bbb R\or\bba S{8}\or\bba T{10.5}\or\bbc
%%%   U{5}\or
   \bba V{12}\or\bba W{16.5}\or\bba X{11}\or\bba Y{11.7}\or\bba Z{7.5}\fi}}
%
%
\renewcommand{\thefootnote}{\fnsymbol{footnote}}

%%% read as: theFOOTNOTE (i.e. the command  executed when doing a footnote) is
%%% now to be set as a FOOTNOTESYMBOL (type of number) value of counter
%%% FOOTNOTE (Instead of roman).  See LaTeX manual pp.91-92 as well as
%%% 175.

\def\bi{\begin{itemize}}
\def\ei{\end{itemize}}
\def\ben{\begin{enumerate}}
\def\een{\end{enumerate}}
\def\st{\, | \,}

\newcommand{\myboxineq}{\eqno\Box} %put \qed at margin (white square) in eqn
\newcommand{\qedineq}{\eqno\halmos} %put \qed at margin in eqn

\topmargin -0.5in %default is 0.0, i.e. 1 inch from top.  Now it is 0.5
\textheight 9in
\oddsidemargin 0.25in %more reasonable margins!  (This is 1.25; can use <0 too)
\evensidemargin 0.25in %(same as above)
\textwidth 6.25in %(could use also -.5,-.5,7.5 for instance)
\tolerance=1600 %allow some tolerance in extending after line.
\parskip=3pt plus 1pt minus 1pt
\overfullrule=0pt %no dark lines if overfull

%%%%%%%%%%%%%%% FROM HERE, macros special for paper %%%%%%%%
\def\mm{m}
\def\pp{p}
\def\proj{\pi _1}     %%%% projection on first group of coordinates
\def\x{u}  % vector argument
\def\SEC{(SEC)}
\def\SECo{(SEC$^0$)}
\def\INV{(INV)}
\def\Fp{{\cal F}_\pp}
\def\Fpm{{\cal F}_\pp^\mm}  %%%% there is a 3,3 and a 2,1 in text

\def\Rm{\R^m}
\def\Rn{\R^n}
\newcommand{\ball}[2]{{\bb B}(#1,#2)}
\newcommand{\cball}[2]{\overline {\bb B} (#1,#2)}
\def\Fnm{{\cal F}_n^\mm}
\def\clos{{\rm clos\,}}
\def\inter{{\rm int\,}}

\def\CCF{compatible class of functions}
\begin{document}

\bibliographystyle{plain}

\pagestyle{empty}
\begin{flushright}
{\sl Roadmap Report}
\end{flushright}
\vfill

\small
\begin{center}
\thicklines
\setlength{\unitlength}{0.3cm}
\begin{picture}(14.5,12)(-7.25,-6)
\multiput(-5.5,-1.45)(0,1.75){2}{\framebox(11,1.15){}}  %%original
\multiput(-1.45,-5.5)(1.75,0){2}{\framebox(1.15,11){}}  %%original

\multiput(-5.5, -3.75)(1.75,6.35){2}{\framebox(11,4.7){}}  
\multiput(-3.75, -5.5)(6.35,1.75){2}{\framebox(4.7,11){}}  

%%\multiput(-4.5, -2.75)(0.75,5.35){2}{\framebox(10,3.7){}}  
%%\multiput(-2.75, -4.5)(5.35,0.75){2}{\framebox(3.7,10){}}  
 
%%\multiput(-3.75,-2.35)(6.35,0){2}{\framebox(1.15,4.7){}}  %%original
%%\multiput(-2.35,-3.75)(0,6.35){2}{\framebox(4.7,1.15){}}  %%original

\multiput(-2.75,-1.35)(5.35,-1.0){2}{\framebox(0.15,3.7){}}  %%original
\multiput(-1.35,-2.75)(-1.0,5.35){2}{\framebox(3.7,0.15){}}  %%original

\multiput(-2.9,0)(2.9,-2.9){2}{\line(1,1){2.9}}  %%original
\multiput(-2.9,0)(2.9,2.9){2}{\line(1,-1){2.9}}  %%original
\end{picture}
\end{center}

\begin{center} 
\hrule
\hrule
\vspace{.05cm}
\hrule
\vspace{.25cm}
{\bf 
A Review of Optimization Methods
}
\vspace{.25cm}
\hrule
\vspace{.05cm}
\hrule
\hrule
\vspace{1cm}
Saleh Elmohamed\\
Paul Coddington\\
Geoffrey Fox\\
CST Bldg., NPAC,\\
Syracuse University,\\
Syracuse, NY 13244-4100\\
\{saleh, paulc, gcf\}@npac.syr.edu .\\   
\end{center}

\vspace{1.5cm}
\centerline{ABSTRACT}

We present a roadmap of discrete optimization with an emphasis on those 
most widely used optimization methods or techniques for tackling some
well-known combinatorial optimization problems.

%% \vfill
%% \noindent{\bf Key words : Integer and Linear Programming,
%% Combinatorial Optimization, Branch-and-cut, Simulated Annealing, etc.}

\vfill
\centerline{Version (5), November 96}
\vfill

\newpage
\pagestyle{empty}
\tableofcontents
\newpage
\listoffigures
\listoftables

\newpage

\pagestyle{plain}

\section{Introduction}
\setcounter{page}{1}
Optimization tasks are common and often very difficult. In most areas
of science and engineering, from free energy minimization in physics
to profit maximization in economics, the need to optimize is
ubiquitous. From these optimization tasks comes a class of problems
termed ``combinatorial optimization'' which is among the hardest of 
common computational problems: the solution time can grow
exponentially with the size of the problem. Examples arise in
scheduling and circuit layout design, to name a few areas. For
instance, in course scheduling, we attempt to find an assignment of 
rooms, time slots, students and faculty to each class to satisfy
restrictions (or constraints) such that no two classes are in the same
room at the same time. Similar scheduling problems arise in assigning
tasks to machines in a manufacturing environment or experiments on
spacecraft with constraints on power use. Fundamentally, these kind of
problems consist of finding those combinations or subsets of a
discrete set of items that satisfy specified constraints. These
satisfactory subsets are the possible solutions to the overall
problem. In the course scheduling problem, for instance, the discrete
set could consist of all possible ways to assign classes to rooms,
time slots, etc. and the task then viewed as selecting a subset of
these possibilities that satisfies the constraints of the
schedule. These problems are thus conceptually very simple to solve
but can be extremely time consuming to derive an optimal solution in
practice. This is because the number of possible combination to
consider grows very rapidly with the number of items, leading to
potentially lengthy solution times and severely limiting the feasible
size of such problems.

In light of the importance and difficulty of combinatorial search,
much effort has gone into developing effective algorithms for finding
good optima. The methods of simulated annealing (SA), genetic
algorithms (GA), and tabu search (TS) are three of the most popular
methods, inspired by ideas from statistical mechanics, evolutionary
biology, and artificial intelligence respectively. All of these
techniques rely in part on constructing improved solutions by applying
a local operator to a population of candidate solutions. Good
solutions result from the accumulation of many beneficial local
modifications applied one after another. Other not so widely used
algorithms to tackle the abovementioned problems are those of neural
networks (NN) and Lagrangean relaxation (LR), inspired by ideas from
neurobiology and integer (or mixed-integer) programming
respectively. Among the most well-known conventional methods are 
those of Lin-Kernighan (LK) and linear programming (LP), which are widely used
very effectively in this domain. As a side note, since most of the
published work we are aware of on these methods involve tackling the
traveling salesman problem (TSP), we will make a reference to this
problem whenever is needed throughout this roadmap. 

Our focus in this roadmap is on discrete optimization and
its associated optimization methods. Figure \ref{tree} shows an 
overview of the entire map. 

\begin{figure}[htb]
\psfig{figure=opt-tree.ps}
\caption{The discrete optimization roadmap.}
\label{tree}
\end{figure}

%% \section{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 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 scaler and we assume that an $x$ to be found
%% minimizing 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 is then restated as 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. 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. For example, the problem 
%% minimize $p_1 + p_2 x + p_3 e^{p_4 x}$  with  $p_2 x + p_4 x^3 -
%% p_5 \geq 0$ and $p_6 x + p_7 x^2 - p_8 \leq 0$  involves 8 data values
%% $p_i$, $i= 1,\ldots,8$. 
%%
%% There are many ideas and methods of optimization which can be
%% considered to be very general, e.g., 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{Combinatorial Optimization}
Combinbatorial optimization (CO) problems \cite{56, 69} are the type of
optimization problems with the property that the set of feasible
solutions corresponds to a finite set, and the user is asked to find
an optimal solution in this large, but finite set. In addition,
combinatorial optimization problems are related to two optimization
models: linear programming and integer (mixed) linear programming,
therefore as either minimization or maximization problems consisting
of a set of problem instances. 

%% A schematic view of the relationship
%% between the class of heuristics mentioned above and the relaxation
%% methods \cite{2} is shown in Figure \ref{connection-sketch}.

It is worth noting that many of those CO problems are mappable onto
other CO problems, that are relatively easier to tackle and perhaps may
have a more intuitive and clearer representation. For example, the
problem of class scheduling can be mapped onto a graph coloring
problem (specifically, some variant of the vertex coloring), then
solving graph coloring in terms of scheduling. Here, not only graph coloring
have a clearer representation than that of scheduling but also there
are a number of coloring methods/algorithms that can be applied to
this problem. For more on this, see the section on graph coloring and 
course scheduling.

%% \begin{figure}[htb]
%% \centerline{\psfig{figure=minimize-sketch.eps,width=350pt,height=290pt}}
%% \caption{A high-level sketch of the concept of minimization. The
%% vertical line shows the {\it value} direction of increase and
%% somewhere (not exactly where) on this line is the optimal solution we
%% are seeking for the problem.}
%% \label{minimize-sketch}
%% \end{figure}

%% \begin{figure}[htb]
%% \centerline{\psfig{figure=connection-sketch.eps,width=325pt,height=290pt}}
%% \caption{Roughly shows the relationship between the class of
%% heuristics and the relaxation methods. The specific techniques used
%% for relaxation are enclosed inside parenthesis.}
%% \label{connection-sketch}
%% \end{figure}

Given a combinatorial optimization problem instance, our objective is
to find a set of solutions with the minimal cost. These kind of
problems are usually tackled using what is referred to as {\it local
search} or {\it local optimization} algorithms such as SA.
These approximation algorithms operate by repeatedly
replacing a solution with a neighboring solution. It starts off 
with an initial solution constructed by some algorithm or heuristics
(e.g. expert system), then the algorithm repeatedly tries to
improve the current solution by replacing it with a neighbor with a
lower cost. If a solution has been reached that has no neighbors with
lower cost, a local minimum has been found. In summary, using the work
of Johnson \cite{71, 72}, the concept of local search can be stated
succinctly as follows (see Figure \ref{local-search}):

A local search algorithm typically consists of two routines: first, an
algorithm that given a problem instance $P$, will construct an initial
solution $S_0$ to it. Second, an algorithm that given $P$ and any
solution $S$, will determine if there is a neighboring solution of
lower cost, and if so will return one such solution $S^{'}$. If no
such solution exists, $S$ is called ``locally optimal.'' Also, these
two routines can either be randomized or deterministic, as we later
will see when outlining the $2$-Opt, $3$-Opt, and Lin-Kernighan
algorithms.

\begin{figure}[htb]
\vspace{0.25cm}
\begin{center}
\begin{enumerate}
\item Activate routine $A$ on input instance $P$ to obtain initial
solution $S = S_0$.
\item Do the following two steps until obtaining a locally optimal
$S$: 
\begin{enumerate}
\item Activate routine $B$ on input $P$ and solution $S$.
\item If $B$ returns a solution $S^{'}$ of lower cost, set $S =
S^{'}$.
\end{enumerate}
\item Return $S$.
\end{enumerate}
\end{center}
\caption{Local search for an optimization problem}
\label{local-search}
\vspace{0.25cm}
\end{figure}

\section{Graph Coloring and Course Scheduling}
Given a fixed time and space constraints an example of mapping a university 
course scheduling onto vertex coloring is presented.

\subsection{Graph Coloring}
Many practical constraint satisfaction problems, such as timetabling
problems, can be mapped onto graph coloring problems.  The problem of
graph coloring can be described as follows.  Suppose a graph exists
with vertex set V and edge set E, where the ordered pair (R,S) is in E
if and only if an edge exists between the vertices R and S.  Two
vertices in a graph are said to be adjacent if an edge exists between
them.  The problem of graph coloring is to partition the vertices into
a minimum number of sets in such a way that no two adjacent vertices
are placed in the same set.  Then, a different color is assigned to
each set of vertices, as shown in Figure ~\ref{fig.colored_graph_1}.
This is known as a proper graph coloring.

\begin{figure}[htb]
\large
   \centerline{\psfig{figure=colored_graph_1.eps,width=5in}}
   \caption{A proper graph coloring using three colors.}
   \label{fig.colored_graph_1}
\end{figure}

\subsection{Course Scheduling}
The scheduling of courses at a university is a practical example of
the timetabling problem.  In this example, the resources involved,
which may be required by no more than one course at any particular
time, are instructors, classrooms, and students.  This problem can be
addressed from different angles.  For example, one could assume that a
particular set of courses will be offered during a term by particular
instructors, and first assign them times and rooms, and then allow
students to register only for courses whose times do not conflict.  A
second approach would be to decide which courses would be offered,
allow students to register for them, and then assign times and rooms
to each course, so that the number of students who have course
conflicts is minimized. Here we will briefly look at the problem from the first 
of  these two points of view.  The restrictions involved in creating 
a schedule of courses from this point of view may
be divided into two categories, ``hard'' and ``soft'' constraints.

Hard constraints are those which must be satisfied in order to have a
legitimate or {\em legal} schedule.  For example, courses may only be
offered during a fixed set of days and times during the week, and each
course must meet a particular number of hours per week.  No instructor
may be scheduled to teach two courses during the same time slot.
Similarly, courses which enroll the same set of students, such as a
physics lecture course and the accompanying laboratory course, may not
be scheduled in the same time slot, since there is an overlap of
students in the two classes.  Each of these hard constraints deals
with time-related, or temporal, issues.

In addition to temporal constraints, there are other hard constraints
which deal with meeting space assigned to each course.  These
spatial constraints arise from the fact that a fixed number of rooms
exist on a given campus, and any courses held during the same time
slot may not be held in the same room.  In addition, since rooms have
a fixed size, course size must not exceed the capacity of the room it
is assigned.  Furthermore, each room is of a particular type, such as
auditorium, laboratory, or seminar room.  Similarly, each course
requires one of these types of rooms, so room type must be a
consideration in the assignment of rooms.

Soft constraints associated with creating a course schedule are
requests that should be fulfilled, if possible.  However, if soft
constraints are not fulfilled, the schedule is still considered legal
provided that all hard constraints have been satisfied.  For example,
an instructor may request a particular time slot free during the week,
or may want a lecture hall in the same building as his or her office.
All instructors may prefer that, if they teach two courses in
contiguous time slots, the courses are not in different buildings.
These types of constraints are reasonable, but it may not be possible
to fulfill each of these in addition to all of the hard constraints.

\subsection{Methods}
In order to find an optimal solution to the problem of scheduling
courses, one attempts to find a schedule which satisfies all of the
hard constraints and maximizes the number of soft constraints
satisfied. To achieve this we use graph coloring to 
find a complete schedule which satisfied all of the hard constraints. 
Local search methods such as simulated annealing can be used to
satisfy the soft  constraints.

\subsection{Temporal Hard Constraints}

Temporal hard constraints can be mapped onto the graph coloring
problem as follows.  Let each course be represented by a vertex.
Attach two vertices by an edge if and only if there is a reason that
the courses they represent may not be offered at the same time.
Initially, there are two such reasons for vertices to be linked:
either they are taught by the same instructor, or they are required by
the same set of students.  Upon adding in the links, color the graph.
Each color represents a different time slot, so every vertex with the
same color will be offered at the same time.

For example, suppose four physics courses must be scheduled: PHY 101,
PHY 234, PHY 300, and PHY 300 LAB.  The same instructor teaches all
three lectures, and a second instructor teaches PHY 300 LAB.
Additionally, students enrolled in PHY 300 are required to enroll in
PHY 300 LAB concurrently, and vice versa.  The graph shown in
Figure~\ref{fig.temporal_constraints_2} represents these temporal
hard constraints.  An edge exists between each of the pairs of courses
taught by the same instructor, since these courses may not be offered
at the same time.  An edge exists between PHY 300 and PHY 300 LAB,
because the same set of students must enroll in both courses.
Figure~\ref{fig.temporal_constraints_2} also shows a proper coloring
of the graph.  Each color represents a different time slot, so only
three different time slots are needed to properly schedule these four
courses.  PHY 101 and PHY 300 LAB will be offered during the same time
slot, PHY 234 will be in a second time slot, and PHY 300 in a third
time slot.  Note that this system only partitions the courses into
groups which will be offered at the same time; it does not assign the
actual time of day.

\begin{figure}[htb]
\large
   \centerline{\psfig{figure=temporal_constraints_2.eps,width=5in}}
   \caption{A graph representing temporal hard constraints.}
   \label{fig.temporal_constraints_2}
\end{figure}

\section{Simulated Annealing}
Simulated annealing, see Figure \ref{SA-algorithm}, has been
widely used for tackling different combinatorial optimization
problems \cite{39}. The results obtained depend heavily on the cooling
schedule as well as on the initial configuration of the problem.

A comprehensive discussion of the theoretical and practical details of
SA is given in \cite{17, 57}. The elementary operation in the
Metropolis method for a combinatorial problem such as scheduling is
the generation of some new candidate configuration, which is then
automatically accepted if it lowers the cost ($C$), or 
accepted with probability $\exp(-\Delta C /T)$, where $T$ is the
temperature, if it would increase the cost by $\Delta (C)$. Thus the
technique is essentially a generalization of the local optimization
strategy, where, at non-zero temperatures, thermal excitations can
facilitate escape from local minima. Table \ref{table.0} shows a few
high level relationships between some of the main components of the
physical annealing systems and optimization problems. 

\vspace{0.1cm}
\begin{table}[htb]
$$
\begin{tabular}{||ccc||ccc||}
\hline
 &  Physical System    && Optimization Problem   &&\\ \hline\hline\hline
 &  System State         &&  Feasible Solution     &&\\ \hline
 &  Change of State    &&  Neighboring Solution  &&\\ \hline
 &  Energy                   &&  Cost                  &&\\ \hline
 &  Ground State        &&  Optimal Solution      &&\\ \hline
 &  Rapid Quenching  &&  Local Search          &&\\ \hline
 &  Careful Annealing &&  Simulated Annealing   &&\\ \hline
 &  Temperature         &&  Control Parameter     &&\\ \hline\hline
\end{tabular}
$$
\caption{The analogy between physical systems and optimization problems.}
\label{table.0}
\end{table}
\vspace{0.5cm}

The SA algorithm has some advantages as well as some 
disadvantages. Among its advantages are the relative ease of
implementation, the applicability to almost any combinatorial
optimization problem, depending on the cooling schedule(s) used it
usually provides reasonable solutions, and it can easily be combined
with other heuristics, forming quite useful hybrid methods for tackling 
a range of complex problems.
Its major drawback is the requirement for long run times.

In summary, SA appears competitive with many of the best local
optimization methods. However, the inherently serial nature of the
approach in general precludes any obvious parallel implementation,
though several attempts have been made to overcome this problem such
as the recent work by Frost \cite{16}, Boissin and Lutton \cite{55},
and Verhoeven and Aarts \cite{56}. The most promising approach to 
parallelizing SA is to distribute the execution of the various parts
of the algorithm over a number of communicating parallel processors
which may contribute to a significant speedup in the overall runtime
of the method. 

\begin{figure}[htb]
\vspace{0.25cm}
\begin{center}
\begin{enumerate}
\item Generate an initial solution (i.e. schedule) $s$ .
\item Set the initial best solution $s^{*} = s$.
\item Compute cost of $s$ :  $C(s)$.
\item Compute initial temperature $T_0$.
\item Set the temperature $T\; =\; T_0$.
\item While {\em stop criterion} is not satisfied do:
\begin{enumerate}
\item Repeat {\em Markov chain length} (M) times:
\begin{enumerate}
\item Select a random neighbor $s^{'}$ to the current solution, 
$( s^{'} \subset {\cal N}_{s} )\;$.
\item Set $\Delta(C) = C(s^{'}) - C(s)\;$.
\item If ($\Delta(C) \leq 0$ $\{$downhill move$\}$):
\begin{itemize}
\item Set $s = s^{'}\;$.
\item If $C(s) < C(s^{*})$ then set $s^{*} = s$.
\end{itemize}
\item If ($\Delta(C) > 0$ $\{$uphill move$\}$):
\begin{itemize}
\item Choose a random number $r$ uniformly from $[0,1]$.
\item If $r < e^{-\Delta(C) /T}\;$ then set $s = s^{'}$.
\end{itemize}
\end{enumerate}
\item Reduce (or update) temperature $T$.
\end{enumerate}
\item Return the solution  $s^{*}$.
\end{enumerate}
\end{center}
\caption{The Simulated Annealing Algorithm}
\label{SA-algorithm}
\vspace{0.25cm}
\end{figure}

\subsection{The Annealing Schedules}

The most popular and widely used cooling schedule is the
geometric cooling. It computes the new temperature ($T^{'}$) of
the SA algorithm as follows: Let $\alpha$ ($0 < \alpha < 1$) denotes
the cooling factor, then

\be{cooling}
T^{'}\; =\; \alpha\; T\;.
\ee

Typically the value of $\alpha$ is chosen from the range of $0.90 \ldots 0.99$. 
This schedule has three main advantages: it is based on a sound
theoretical foundation, is well understood by all researchers working
on annealing, and is the most widely used cooling schedule. Because of
these advantages it is used as a base line for comparison with other
scheduling schemes. Of course, there are other non-adaptive (or
geometric) type schedules as well as the adaptive ones as we outline
few below. The greatest difference between these schedules are in the
temperature decrements and time spent at each temperature. From
experimentations and other sources, we would like to state that
neither the temperature changes, nor the time spent at a given
temperature, taken alone, are of any significant; all that 
is important is their combination. 


\subsubsection{White cooling schedule}
This schedule was due to Steve White \cite{61} and probably the first
significant study of cooling schedules. Much of the analysis there is
on the expected energy in equilibrium at temperature $T$. Briefly, for
temperatures approaching infinity or zero, the expected energy is
limited by the energy of a randomly-chosen state or that of the global
minimum, respectively. White's ideas proved to be seminal in the field
and influenced the work of other researchers such as that of Otten and
van Ginneken \cite{62}, in which they elaborated  on the
characterization of equilibrium quantities. Others, e.g. Lam and 
Delsome \cite{63}, have adapted to their schedules White's ideas of
matching the move set to the temperature. 

\subsubsection{Lundy-Mees Schedule}
Lundy and Mees schedule \cite{64} was one of the first schedules based
on the concept of changing $T$ by small values and one move at the new
temperature should be enough to restore equilibrium. One of the
implementation that we are aware of using this schedule and the
inverse of it is the examination timetabling of Dowsland and Thompson
\cite{65}. 

\subsubsection{Huang-Romeo-Sangiovanni schedule}
Huang, Romeo, and Sangiovanni's \cite{66} is an adaptive schedule
in which the temperature decrements is done effectively by exploiting
the relationship ${dE_T(f) \over dT} = {\sigma^{2}_T(f) \over T^2}$,
where $f$ is the energy function.

\subsection{Applications}
Using SA in a multi-stage approach, we have tackled a large instance
of the course scheduling problem. As reported in \cite{79}, our
results depend highly on the cooling schedule as well as on the
strategy of swaps (or moves) between courses, rooms, etc. This
application and our results reported in \cite{79} show that SA is a
viable method in dealing with complex problems such as scheduling.

In a series of articles \cite{18, 19, 72}, David Johnson and colleagues
present a top-quality, extensive experimental survey of SA. In the
first article, annealing is compared with the Kernighan-Lin algorithm
for graph partitioning on a number of problems varying in size and
structure. Briefly, annealing did better on sparse random graphs,
especially as size increased, but did worse on geometrically
structured graphs. Many factors were taken into account: One was the
number of runs of a given algorithm needed to find a solution of a
given quality. Another was the construction of an appropriate penalty
cost term, which keeps the two partitions approximately the same
size. Many runs were made for every experiment to properly account for
the randomized nature of the algorithms. Johnson's seems to be the
only study in the literature to make use of a starting temperature
significantly lower than that at which the expected energy begins to
decline, validating this technique through observations about typical
states at higher temperatures, as well as by direct comparison between
schedules with high and low starting temperatures.

The second article by Johnson et al. explores the behavior of
annealing on two problems, graph coloring and number
partitioning. These were chosen because they were both problems to
which it was generally believed annealing was not suited.

For graph coloring, three different move sets were tried for the
annealing, and were compared with three different heuristics, as well
as with a modification (``XRLF'') of one of the heuristics. Like
annealing, XRLF allows a tradeoff between run time and solution
quality. To make a long story short, different algorithms were best on
different size graphs and on different types of graphs (for example,
controlling the edge probability for a random graph). None of the
annealing move sets dominated the others. For almost all cases, either
XRLF or a version of annealing worked best, the more conventional
heuristics were not generally competitive. 

For the number partitioning problem the situation is quite
different. A key property of the problem is that, at least with the
natural move set used by Johnson, there are many states of quite low
energy, separated by tall energy barriers. The situation is really
terrible for SA, for the reasons: a low temperature does not allow the
barriers to be crossed, and a high temperature does not distinguish
between the minima. So Johnson's experiments showed this to be one
case where annealing was actually no better than repeated descent, or
annealing at temperature $0$. Also, it was observed that during
annealing for this problem, the last state seen was often not the best
state ever seen, pretty strange!

After reading Johnson's studies the impression we left with was that
the question of whether annealing was better or worse than standard (or
conventional) heuristics was not a simple one. Perhaps, the answers
change depending on a wide variety of factors, including details of
the heuristic algorithms, the choice of the annealing move set, and
the exact nature of the problem instances to be solved.

\section{Genetic Algorithms (GAs)}
A genetic algorithm can be understood as a {\it smart} probabilistic
search algorithm which can be applied to variety of combinatorial
optimization problems \cite{2}. The idea of GAs is based on
the evolutionary process of biological systems. Throughout natural
selection, nature has developed a robust and powerful technique for
maximizing the {\it fitness} of populations. GAs mimic this by
evolving a population of solutions, generating new solutions by a
{\it matting} procedure in which parents are chosen probabilistically
according to their fitness, i.e. solution cost. The offspring
incorporate elements of their parents' solutions, and so after many
generations the solutions in the population tend to improve. To
maintain diversity in the population, a low level of random
{\it mutation} is also incorporated. 

To be more precise, given a combinatorial optimization problem and an
initial population of individuals {\it solutions}, each individual in
the population is encoded into a string of {\it chromosome} which
represents a possible {\it solution} to a given problem. The fitness
of an individual is evaluated with respect to a given objective
function. Highly fit individuals or {\it solutions} are given
opportunities to reproduce by exchanging pieces of their genetic
information, in a {\it crossover} operation (see Figure
\ref{crossover-sketch} and Holland \cite{76}), with other highly fit
individuals. This produces new offspring solutions (children), which
share some characteristics taken from both parents. The operation of
{\it mutation} is often applied after {\it crossover} by altering some 
genes in the strings. The offspring can either replace the whole
population (generational approach) or replace less fit individuals
(steady-state approach). This evaluation-selection-reproduction cycle
is repeated until a satisfactory solution is found.
For an overall view of the GA steps, see Figure \ref{GA-pseudo-steps}.
Goldberg \cite{} outlined the main differences between genetic
algorithms and the more traditional optimization methods in the
following four points:

\begin{itemize}
\item GAs work with a problem coding, not the actual variables, making
them largely problem independent. A solution is represented as a
finite length string over some binary alphabet. 

\item GAs search from a population of solutions, not a single
point. This implies that the algorithm is less likely to become
trapped in a local optimum that is far from optimal. 

\item GAs are guided in their search only by fitness scores, not
derivatives or other information. Many methods make assumptions about
the existence of such auxiliary information which can often
misleading. GAs make no such assumptions, so are applicable to a wide
variety of problems, unfortunately at the expense of algorithm runtime.

\item GAs use stochastic rules rather than deterministic choices when
searching for the optimum. Random choice is used as a tool to guide
the algorithm towards areas in the search space of likely improvement.
\end{itemize}

When implementing the algorithm, the following important techniques
need to be considered:
\begin{itemize}
\item A suitable coding (or representation) of the problem.
\item A fitness function to compare the solutions which are being
optimized (i.e. the objective function).
\item A reproductive plan for redistributing genetic material
contained in the population. This is composed of three parts:
\begin{itemize}
\item Reproduction: a selection process for choosing parents for
mating purposes.
\item Crossover: recombines genetic information from two parents to
produce offspring with characteristics from both.
\item Mutation: makes random changes to the offspring to ensure
variety is maintained in the population.
\end{itemize}
\item A method to determine population convergence.
\end{itemize}

\begin{figure}[htb]
\vspace{0.25cm}
\begin{center}
\begin{itemize}
\item Generate an initial population.
\item Evaluate fitness of individuals in the population.
\item {\bf Repeat}
\begin{itemize}
\item Select parents from the population.
\item Recombine (mate) parents to produce children.
\item Evaluate fitness of the children.
\item Replace some or all of the population by the children.
\end{itemize}
\item {\bf Until} a satisfactory solution has been found.
\end{itemize}
\end{center}
\caption{A ``pseudo'' Genetic Algorithm.}
\label{GA-pseudo-steps}
\vspace{0.25cm}
\end{figure}

\begin{figure}[htb]
\centerline{\psfig{figure=crossover-sketch.eps,width=375pt,height=245pt}}
\caption{An example figure showing a crossover operation, which is a
fundamental mechanism of genetic rearrangement.}
\label{crossover-sketch}
\end{figure}

A general and basic scheme of GAs that can be used as an approach to
tackle problems such as the TSP and scheduling is shown in Figure
\ref{GA-general-scheme}, where each performance of the loop consisting
of steps 3.1 through 3.5 can be viewed as the processing of 
a single {\it generation} in the evolutionary process. Also, note that
the operations on different solutions can be performed in parallel if
desired, and so this is sometimes called the ``parallel genetic
algorithm''. Before adapting the scheme of Figure
\ref{GA-general-scheme} to a specific TSP or a timetabling problem, we
need to specify $k$ and $k^{'}$, the methods for generating starting
solutions (tours or timetables), the local optimization algorithm
${\bf A}$, the mating strategy, the nature of the crossover and
mutations operators, the selection strategy, and the criterion for
convergence.

Even without the local optimization steps of Figure
\ref{GA-general-scheme}, a GA can be classified as a variant on local
search. For one thing, it has an ``implicit'' neighborhood structure
in which the neighbors of a solution are those solutions that can be
reached by a single mutation or mating operation.

\begin{figure}[htb] 
\vspace{0.25cm}
\begin{center}
\begin{enumerate}
\item Generate a {\it population} of $k$ starting solutions ${\bf S} =
\{S_1, \ldots, S_k\}$.
\item Apply a given local optimization algorithm ${\bf A}$ to each
solution $S$ in ${\bf S}$, letting the resulting locally optimal
solution replace $S$ in ${\bf S}$.
\item While not yet {\it converged} do the following:
\begin{enumerate}
\item Select $k^{'}$ distinct subsets of ${\bf S}$ of size 1 or 2 as
parents (the {\it mating} strategy).
\item For each 1-element subset, perform a randomized {\it mutation}
operation to obtain a new solution.
\item For each 2-element subset, perform a (possibly randomized) {\it
crossover} operation to obtain a new solution that reflects aspects of
both parents.
\item Apply local optimization algorithm ${\bf A}$ to each of the
$k^{'}$ solutions produced in the previous step, and let ${\bf S}^{'}$
be the set of resulting solutions.
\item Using a {\it selection strategy}, choose $k$ {\it survivors}
from ${\bf S} \cup {\bf S}^{'}$, and replace the contents of ${\bf S}$
by these survivors.
\end{enumerate}
\item Return the best solution in ${\bf S}$.
\end{enumerate}
\end{center}
\caption{A general schema for a genetic optimization algorithm.}
\label{GA-general-scheme}
\vspace{0.25cm}
\end{figure}

\section{Tabu Search}

TS, originally due to Glover \cite{59, 60}, is a metaheuristic
\cite{12} designed for getting a global optimum to a combinatorial
optimization problem, and like SA, is motivated by the observation
that not all locally optimal solutions need be good solutions. Thus it
might be desirable to modify a pure local optimization algorithm by
providing some mechanism that helps the user escape local optima and
continue the search further. One such mechanism would simply be to
perform repeated runs of a local optimization algorithm, using a
randomized starting heuristic to provide different starting
solutions. A sketch of the basic ideas of the method follows.

An objective function $f$ has to be minimized on a set $X$ of feasible
solutions. A neighborhood $N(s)$ is defined for each solution $s$ in
$X$. The set $X$ and the definition of the neighborhood $N(s)$ is
defined for each solution $s$ in $X$. The set $X$ and the definition
of the neighborhood induce a state-space graph $G$ (possibly
infinite). TS is basically an iterative procedure which starts from an
initial feasible solution and tries to reach an optimal solution by
moving step by step in the state-space graph $G$. Each step consists
of first generating a collection $V^{*}$ of solutions in the
neighborhood $N(s)$ of the current solution $s$, and then moving to
the best solution $s^{'}$ in $V^{*}$, even if $f(s^{'}) > f(s)$. Let
$s^{'} = s \oplus m$ to denote that $s^{'}$ is obtained by applying
modification $m$ to solution $s$. The solutions consecutively visited
in the iterative process induce an oriented path in $G$. Finding the
best solution in $V^{*}$ may sometimes be a nontrivial matter. It may
be necessary to solve the optimization problem $min\{f(s_j) | s_j \in
V^{*} \}$ by some heuristic procedure.

A risk of cycling exists as soon as a solution $s^{'}$ worse than $s$
is accepted. In order to prevent cycling , modifications which would
bring us back to a previously visited solution should be
forbidden. Although, sometimes it may be useful to come back to an already
visited solution and continue the search in another direction from
there. This is done in TS by keeping a list $T$ containing the last
$k$ modifications ($k$ can be fixed or variable). Whenever a
modification $m$ is made for moving from $s$ to $s^{'}$, $m$ is
introduced in $T$ and its reverse is considered as a tabu.

In regard to tabu moves, it is shown in \cite{58} that moves to
solutions which have not been visited may be tabu. For this reason it
should be possible to cancel the tabu status of a move if it seems
desirable to do so. Here is how it is done. Let $s$ be the current
solution and $m$ a modification which we want to apply to $s$. Next, 
the penalty value or ``penalization'' $a(s,m)$ and a threshold value
$A(s,m)$ are computed as follows: if $a(s,m) < A(s,m)$, then the 
tabu status of $m$ at $s$ is canceled. We can for example define
$a(s,m) = f(s \oplus m)$ and $A(s,m) = f(s^{*})$ where $s^{*}$  is the
best solution encountered so far: that is, the tabu status of $m$ is
canceled if the solution $s^{'} = s \oplus m$ is better than previous
best solution $s^{*}$. Reference \cite{58} referred to function $A$ as
an {\it aspiration function}.

In addition, stopping rules have to be defined. If a lower bound
$f^{*}$ of the minimum value of $f$ is known then the process may be
interrupted when the value of the current solution is close enough to
$f^{*}$. Moreover, the procedure is terminated if no improvement of
the best solution $s^{*}$ found so far has been made during a given
number $nmax$ of iterations. Figure \ref{TS-general-description} shows
a general description of this technique.

\begin{figure}[htb]
\vspace{0.25cm}
\begin{center}
\begin{itemize}
\item {\bf Initialization}
\begin{itemize}
\item $s$ = initial solution in $X$.
\item $NBiter = 0$.   /* current iteration */
\item $BESTiter = 0$. /* iteration when the best solution has been
found */
\item $s^{*} = s$.    /* best solution */
\item $T = \emptyset$.  /* a list or a set to keep modifications */
\item Initialize the aspiration function $A$.
\end{itemize}
\item {\bf while} ($f(s) > f^{*}$) {\bf and} (($NBiter - BESTiter$) $<
nmax$) {\bf do}
\item {\bf begin}
\begin{enumerate}
\item $NBiter = NBiter + 1\,$.
\item generate a set $V^{*}$ of solutions $s_j = s \oplus m_i$ in
$N(s)$ such that either $m_i \not\in T$ or else $a(s,m_i) < A(s,m_i)\,$.
\item choose a best solution $s^{'}$ in $V^{*}\,$.
\item update the tabu list (set) $T$ and the aspiration function
$A\,$.
\item {\bf if} $f(s^{'}) < f(s^{*})$ {\bf then} $s^{*} = s^{'}\,$,
$BESTiter = NBiter\,$.
\item $s = s^{'}\,$.
\end{enumerate}
\item {\bf end}
\end{itemize}
\end{center}
\caption{A general schema for the tabu search technique.}
\label{TS-general-description}
\vspace{0.25cm}
\end{figure}

In summary, the general idea of TS is always to make the best move
found, even if that move makes the current solution worse, i.e., is an
{\em uphill} move. Thus, assuming that all neighbors of the current
solution are examined at each step, TS alternates between looking for
a local optimum and, once one has been found, identifying the best
neighboring solution which is then used as the starting point for a
new local optimization phase. If one did just this, however, there
would be a risk that the best move from this ``best neighboring''
would take us right back to the local optimum we just left or some
other recently visited solution. This is where the {\it tabu} in TS
comes in. Information about the most recently made moves is kept in
one or more {\it tabu list}, and this information is used to
disqualify new moves that would undo the work of those recent
moves. There are a number of other factors involved with the
full-blown TS algorithm such as {\it aspiration-level} conditions,
{\it diversification} rules, and {\it intensification} rules. For more
details on the algorithm see \cite{58, 59, 60, 80}. From the
application side, TS has been applied to a number of rather difficult
optimization problems such as operational timetabling \cite{81}
yielding very satisfactory results.

\subsection{References}
Links to relevant work in this area:
 ---
 
\section{Neural Network Algorithms}

In general these algorithms have been shown to be not very competitive
with the aforementioned methods or other classical approaches when
tackling combinatorial optimization problems. For the TSP, the first
neural network approach was due to Hopfield and Tank (HT) (please see
\cite{1} for more details about the model). Their approach was based
on the {\it integer programming} formulation of the TSP shown in
Figure \ref{IP-TSP.nnets}. Here $x_{i,k} = 1$ is taken to mean that
city $c_i$ is the $k$th city in the tour, in which case the sum being
minimized is the tour length. The first constraint says that each
position contains precisely one city and the second says that each
city is in precisely one position on the tour.

\begin{figure}[htb]
\vspace{0.25cm}
\begin{center}
\begin{itemize}
\item {\em Minimize} ${\displaystyle \sum_{i=1}^N\sum_{j=1}^N} d(c_i,c_j)
{\displaystyle [ x_{i,N} x_{j,1} + {\displaystyle \sum_{k=1}^{N-1}}
x_{i,k} x_{j,k+1} ]}$
\item {\em Subject to} the following three constraints:
\begin{enumerate}
\item ${\displaystyle \sum_{i=1}^N} x_{i,k} = 1\,,\,\,\,\, 1 \leq k
\leq N$
\item ${\displaystyle \sum_{k=1}^N} x_{i,k} = 1\,,\,\,\,\, 1 \leq i
\leq N$
\item $x_{i,k} \in \{0, 1\}\,,\,\,\,\, 1 \leq i,k \leq N$
\end{enumerate}
 \end{itemize}
\end{center}
\caption{An integer programming formulation for the TSP.}
\label{IP-TSP.nnets}
\vspace{0.25cm}
\end{figure}

Hopfield and Tank's algorithm attempted to find a good feasible
solution to the formulation of Figure \ref{IP-TSP.nnets} by viewing
the $x_{i,j}$ as {\it neurons} that could take arbitrary values in
the interval $[0,1]$. The neurons were connected up with an inhibitory
network that tried simultaneously to impose the constraints and to
lower the cost of an energy function. Local optima for this
energy function were found using a local optimization method where
individual neurons changed state so as to lower their contribution to
the total energy. Multiple random starts were allowed. 

In comparison to other methods summarized in this paper and tried on
problems such as the TSP, Hopfield and Tank's results were not at all
promising. The main reason for this is the inability of the algorithm
to constrain the network into valid solutions, that is, the network's
partition function sums over a vast number of configurations which are
nothing like valid tours, and even though these offenders have small
Boltzmann weights their large number inevitably affects the thermal
average quantities.

Next, we would like to summarize the overall Hopfield continuous
model.

\subsection{The Hopfield Net}
For a schematic view of the network, see Figure \ref{HN-schematic}.

\begin{figure}[htb]
\centerline{\psfig{figure=hopfield_net.eps,height=288pt,width=300pt}}
\caption{A schematic view of the Hopfield network}
\label{HN-schematic}
\end{figure}

\begin{itemize}
\item The network is built by connecting a large number of neurons to
each other to form a dense, parallel array.

\item In general, any $i^{th}$ neuron in the net is described by two
state variables: its current input $u_i$ and its output $v_i$.

\item The output is related to the input by a monotonically increasing
transfer function: 
\be{Hop1}
v_i = g_{\lambda}(u_i)\,.
\ee

\item The net's dynamics are governed by the first order differential
equation:
\be{Hop2}
{du \over dt} = - \eta u + Wv + I^b\,.
\ee

\item
\be{Hop3}
g_{\lambda}(u_i) = {1 \over {1 + e^{-2\lambda u_i}}}\,, 
\ee
for large $\lambda$, this function approximates a {\it step function},
forcing $v_i$ to $[0,1]\;\Longrightarrow\;$ (the output of the net
lies on the unit hypercube).

\item $W_{ij}$ is the connection strength between neuron $i$ and neuron
$j$. 
\item $I_i^b$ is an input bias to neuron $i$.
\item Neurons may be updated individually at random (asynchronously)
or all in parallel (synchronously).
\end{itemize}

\subsubsection{Operation and Update of the State Neurons}
The network's dynamics are governed by a set of nonlinear coupled
differential equations of the form:
\be{net-dynamics.1}
{{du_i} \over {dt}} = - u_i + \displaystyle\sum_{j=1}^{n} W_{ij} v_j +
I_{i}^{b}\,,
\ee
or in a general form:
\be{net-dynamics.2}
{{du} \over {dt}} = - \eta u + Wv + I^b\,,
\ee
where the $I_{i}^b$ corresponds to an input bias to neuron $i$, and 
the $\eta$ term introduces an element of decay into the network's
dynamics, which can be used to ensure that $u$ variables remain
bounded in magnitude.

To make sure that stability of the of the net is guaranteed, $u_i$ is
updated continuously by evaluating ${d \over dt}u_i$ as a function of
the total input to the $i^{th}$ neuron.

\be{update.1}
\dot{u} = 
-\eta u + Wv + I^b\,,
\ee

where

\be{update.2}
v = g(u)
\ee

So, the overall dynamics of the network is governed by equations
(\ref{update.1}) and (\ref{update.2}).

\subsubsection{Stability of the network}

Given that $W$ is symmetric, Hopfield proved stability for the
network by showing that with the abovementioned equations
(\ref{update.1} and \ref{update.2}), the network output $v$
evolves so as to minimize the {\it Liapunov function}:

\be{liapunov-func}
E^{liap}(v) = 
\left( -{1 \over 2} \sum_{ij} W_{ij} v_i v_j -\sum_i I_{i}^b v_i
\right) + \eta{\displaystyle \sum_i} {\displaystyle \int_{0}^{v_i}}
g^{-1}(V) dV
\ee

where $v = (v_1 \ldots v_n)$ denotes the network state. Therefore we
have an energy function defined throughout $v \in [0,1]^n$ and
dynamics which guarantee convergence to minima. Also, for a suitable
$W$, the minima of the first term lie at the hypercube vertices. The
second term is minimized at the hypercube center but has negligible
impact at low $\eta$.

In regard to updating the states of the net (or the output of the
neurons), it is carried out either asynchronously or
synchronously. From a simulation point of view, we found that
asynchronous updating is a bit more efficient than synchronous
updating since the later gave more limit cycles, hence, worse
convergence. From a theoretical point of view, it makes not much of a
difference on the operation of the net as to which updating mode is
used. 

\subsubsection{Mapping the problem onto the network}

We believe that this is probably the most important phase when dealing
with computational models such as neural nets. Suppose we are given an
optimization problem then we need to consider the following steps:
\begin{enumerate}
\item A representation of the problem is needed in which the feasible
solutions lie at hypercube\footnote{For more details see \cite{3}}
vertices.
\item Each hypercube vertex is regarded as a configuration of the
problem, with an associated energy (or cost) function.
\item The partition function is then formed by summing the Boltzmann
factors of the admissible configurations. 
\item A quadratic energy function (to be mapped onto the first term of
equation (\ref{liapunov-func})) for which the minima correspond to solutions
and the depth of each minimum reflects the solution quality.
\end{enumerate}

Hopfield and Tank mapped the TSP onto their model using a permutation
matrix representation of the TSP tours. Other likewise problems can be
mapped using a similar representation.

\subsection{Mean Field Annealing}

\subsubsection{Brief Background}
One possible way to rectify the shortcoming of the aforementioned HT
model is to reduce the computational burden being placed on the
network. This can be done by constraining each city (in the TSP case)
to be ``on'' only once, that is by enforcing the constraint $\sum_a
\sum_k x_{i,k} = 1\; \forall i$, rather than relying on an energy
penalty term to try to hopefully achieve it, as it is done in the HT
original algorithm. This idea was first used and analyzed for the TSP
case, among others, by Peterson and S$\ddot{o}$derberg
\cite{7}. Essentially, their approach is to replace the $N$ neurons
representing  $x_{i,k}\,, 1 \leq k \leq N$ by a single $N$-dimensional
{\it Potts neuron} using what is referred to as the {\it mean field
annealing} (MFA) approach. This generally yields the same final
network equations as the ``neuronal circuit'' approach of \cite{70},
but the exposition is a little bit clearer, as it is laid out in a
statistical mechanics framework\footnote{This equivalence was also noted in
\cite{1}. M. Simmen and P. Simic brought this point to our
attention.}. As stated in the above mapping subsection, one need to
compute all admissible configurations of the problem at hand. For
example, when mapping the TSP onto the HT model, all of the $2^{N^2}$
configurations are admissible, whereas if each city is
restricted to being visited only once, then only $N^N$ vertices are
admissible. After taking a mean field  approximation, saddlepoint 
equations are derived, the solutions of which pick
out the dominant states of the network at the current temperature
$T$.

This approach was not only an improvement over the Hopfield and Tank
model but also gave more feasible (and valid) solutions. 
For a brief overview of the generic ``black box'' MFA algorithm using
the Potts neurons, take a look at Figure \ref{MFA-general-algorithm}. 

In addition to the TSP implementation, Peterson and colleagues
extended the technique and applied it to a case of high school
scheduling \cite{8, 9}. We also have used the same model for class
scheduling \cite{10} with, unfortunately, not very impressive
results. 

\subsubsection{MFA variables: from Ising to the Potts model}
The Ising model describes a magnetic system in terms of binary spins 
$s_i \in \{-1 , 1\}$. The system is governed by the energy function

\be{ising-energy-func}
E = - {J \over 2} {\displaystyle \sum_{i}}\, s_i s_{i+1}
\ee

where nearest neighbors interact pairwise with a constant attractive
(if $J > 0$) coupling of strength $J$. The lowest energy state is
reached by iterative updating of 

\be{Ising-update}
s_i = sgn[J(s_{i-1} + s_{i+1})]
\ee

which leads to a state where all spins point in one of two possible
directions.

As mentioned above, in the Potts model we restrict the state space of
the neurons such that exactly {\it one neuron} at every site is
allowed to be on and represented as follows:

\be{Potts-neuron}
\forall i {\displaystyle \sum_{a \in A}} s_{ia} = 1\,.
\ee

Thus for every $i$, $s_{ia}$ should be 1 for only one value of $a$ in
the set of states $A$, and $0$ for the rest of the states. 
In general, lets assume that the states of the Potts neuron can be
represented by a $k$-dimensional vector. Now, we could say that the
$a^{th}$ possible state of the neuron vector $\vec{s}_i$ associated
with neuron $i$ is represented by the unit vector in the direction of
$a$, so we end up with $k$ different states. Also, these states
$(1,0,\ldots,0)$, $(0,1,\ldots,0)$, $\ldots$, $(0,0,\ldots,1)$ are all
normalized and mutually orthogonal. Therefore, the number of states
available at every node is reduced from $2^k$ to $k$. Hence, we now
have a $k$-state Potts model. 
In short, the explicit enforcement shown in equation
(\ref{Potts-neuron}) is known in the MFA algorithm as {\it Neuron
Normalization} and the reason behind it is to reduce the number of
states at each neuron. This concept is really the key to the Potts
model.

Before we introduce the mean field variables, we would like step back
and take a second look at the Hopfield model \cite{70, 1}. In
\cite{70} Hopfield introduced a model with neurons having a graded
response. So given $I_i$ a fixed input bias to neuron $x_i$, $W_{ij}$
the weight of the connection between neurons $x_i$ and $x_j$, and parameter 
$T$ to denote the temperature, the behavior of $x_i$ can be stated as:

\be{form-JH}
x_i =
{1 \over 2} + {1 \over 2} 
\tanh\left(({\displaystyle\sum_{i \neq j}W_{ij}x_j - I_i}) {1 \over T}\right)
\ee

When $T \longrightarrow 0$, function ({\ref{form-JH})'s response takes
on a step-wise form.

Now, to compute the actual mean field variables we do the following:
At a finite $T$, $x_i$ (of eq. \ref{form-JH}) can be replaced by a
mean field theory (MFT) variable $\upsilon_{ia}$, then differentiating
to obtain the Potts MFT equations:

\be{Potts.1}
\upsilon_{ia} =
- {1 \over T} {{\partial E}[{\vec\nu}] \over {\partial \nu_{ia}}}
\ee
\be{Potts.2}
\nu_{ia} =
{e^{\upsilon_{ia}} \over {\sum_b e^{\upsilon_{ib}}}}
\ee

Substituting $\nu_{ia}$ for $s_{ia}$, we find that equations
(\ref{Potts.1},\ref{Potts.2}) clearly satisfy equation
(\ref{Potts-neuron}). Also the $\upsilon_{ia}$ and $\nu_{ia}$ are
referred to as the {\em mean field variables}. 

\begin{figure}[htb]
\vspace{0.25cm}
\begin{center}
\begin{itemize}
\item Choose a problem then properly map it onto the neural network
set of weights: $\{w_{ij}\}$. (See the section on mapping).
\item Find the approximate phase transition temperature by linearizing
equation (\ref{Potts.2}). Also, as part of that compute the critical
temperature $T_c$.
\item Add a self-coupling $\beta$-term if necessary. Neural-wise, this
corresponds to a feedback connection from a neuron to itself.
\item Initialize the neurons 
   $\nu_{ia}$ with ${1 \over N} \pm$ {\em random values}; and set $T(0) = T_c$.
\item Until ($\Sigma \approx {1 \over N}\sum_{ia}\nu^{2}_{ia}\geq 0.99$) do:
\begin{enumerate}
\item At each $T(n)$, update all $\nu_{ia}$ via $\upsilon_{ia}$:
\begin{enumerate}
\item  $\upsilon_{ia} = 
        - {1 \over {{\cal T}(n)}} {{\partial E[\nu]} \over {\partial \nu_{ia}}}.$
\item  $\nu_{ia} = {e^{\upsilon_{ia}} \over {\sum_b
e^{\upsilon_{ia}}}}$.
\end{enumerate}
\item $T(n+1) = 0.9 \times T(n)$.
\end{enumerate}
\item After $\Sigma \geq 0.99$ is reached perform a {\it greedy
heuristics} if needed to account for possible imbalances or rule
violations.
\end{itemize}
\end{center}
\caption{A general schema for the mean field annealing algorithm.}
\label{MFA-general-algorithm}
\vspace{0.25cm}
\end{figure}

\subsubsection{Conclusion}
In conclusion, we would like to briefly state a few interesting points
about neural algorithms. Neural networks differ from most of the other
methods talked about in this paper, in that whereas those other
methods are 
restricted to searching within a finite set of feasible solutions, the
neural techniques explore more or less a continuous search space with
an objective for picking out a solution. Another feature of the neural
networks is that most of them are inherently parallel in
operation. They are made up of a large number of simple elements that
can process their inputs in parallel. Accordingly, they lend
themselves naturally to implementations on parallel computers.  

\subsection{Other Variants and Models of Neural Networks}
One of the modifications to the Hopfield and Tank model for
dealing with optimization problems is the use of simulated annealing
to perform a discretized version of the local optimization as in the
{\it Boltzmann machine} approach of Aarts and Korst \cite{11}. A
key factor holding these variants back is the integer programming
formulation of Figure \ref{IP-TSP.nnets}, which shows that a large
portion of a neural net's work be spent merely getting a feasible
solution.

There are also two variants of neural nets that can be classified as
``geometric'' neural networks. These are the {\it elastic net} of
Durbin and Willshaw \cite{73} and the {self-organizing map} which is
based on ideas of Kohonen \cite{74}. When applied to the TSP, these
network can be viewed as a string connecting a set of points $X =
\{x_1, x_2,\ldots\}$ on the plane, as shown in sketch A of Figure
\ref{geometric-net}, such that $|X| \geq N$ where $N$ is the number of
cities. The idea here is to move these points iteratively toward the
cities, thus deforming the geometric figure shaped by the connecting
string as shown in sketch B of Figure \ref{geometric-net}. The
objective is to continue this process until the geometric shape of the
connecting string and the $X$ points looks like a tour, with each city
matched with one of the $X$ points. See also the work of Durbin,
Szeliski and Yuille \cite{75}} for more details on these networks.

Johnson and colleagues experimented with these geometric models
on the TSP and the best tours they obtained are far worse than
the ``average'' tours obtained using the 2-Opt and Lin-Kernighan
heuristics.

\begin{figure}[htb]
\psfig{figure=geometric-net.eps,width=432pt,height=228pt}
\caption{A geometric-based neural network. The empty circles each
denotes a city. Sketch A shows the start of the execution and sketch B
shows an intermediate stage in the execution.}
\label{geometric-net}
\end{figure}

\subsection{references}

\section{Lagrangean Relaxation Method}
Lagrangean relaxation is a powerful bounding technique that has been
applied with success to many NP-hard combinatorial optimization
problems. The basic idea is to see the problem as an easy-to-solve
problem but complicated by a number of difficult side constraints.
The way this approach deals with these complex constraints is to try
to absorb them into an objective function which is then solved
(exactly) using the Lagrangean heuristics. The three main steps
involved in this technique are:
\begin{itemize}
\item Take an integer (or mixed-integer) programming formulation of
the given problem instance.
\item Attach Lagrange multiplier to some (not all) of the constraints
in this formulation and then relax these constraints into the
objective function.
\item Solve (exactly) the resulting integer (mixed-integer) problem. 
\end{itemize}

For in depth discussion about this method and the various techniques
and heuristics involved, see chapter 6 of \cite{2}.

% \begin{figure}[htb]
% \psfig{figure=2-opt.sketch.eps,width=430pt,height=228pt}
% \caption{A 2-Opt swap: TSP Tour 1 is the original tour and the dotted
% lines are the edges to be deleted. Tour 2 is the resulting tour after
% the swap.}
%\label{2-opt.sketch}
% \end{figure}
% 
%\begin{figure}[htb]
% \psfig{figure=3-opt.sketch.eps,width=430pt,height=228pt}
% \caption{A 3-Opt swap: TSP Tour 1 is the original tour and those edges
% to be deleted are denoted with dotted lines. Tour 2 is the resulting
% tour after the swap. This figure shows only one possible swap but we
% could form others.} 
% \label{3-opt.sketch}
% \end{figure}

\section{Lin-Kernighan heuristics (LK)}
This algorithm is due to Lin and Kernighan \cite{78} and share some of
the search strategies with aforementioned Tabu search technique. For
example, the LK method uses uses lists that are very similar to the
tabu lists but in a way that is a bit more complicated than explained
above. At each iteration of the iterative process, LK decides how many
edges to exchange producing generally high quality solutions at the
expense of using significant amounts of computational time in
comparison with other edge exchange algorithms. 


\section{Graphs and Combinatorial Optimization}
\subsection{Graphs and Digraphs}
--- definitions of graphs and digraphs (directed) ---

\subsubsection{Computer Representation of Graphs and Digraphs}
\begin{enumerate}
\item Adjacency matrix.
\item Adjacency matrix of a digraph.
\item Vertex incidence list and edge incidence list of a graph.
\begin{itemize}
\item Sparse graphs.
\item Complete graphs.
\end{itemize}
\end{enumerate}

\subsection{Shortest Path Problems}
\begin{itemize}
\item Analyze the complexity.
\item Shortest path ?

Shortest path if all edges have length 1
(1) Breath first search (BFS)   (2) Depth first search (DFS)

{\it Example}:
(1) Moore's BFS algorithm for shortest path.

--- Complexity of an algorithm --- 
Issues involved in complexity:
\begin{itemize}
\item Symbol ``O'' (or big O).
\item Efficiency.
\item Polynomial boundedness.
\end{itemize}

(2) Other examples:
\begin{itemize}
\item Euler graph.
\item Chinese postman problem.
\end{itemize}

\end{itemize}

\subsection{Dijkstra Algorithm for Shortest Path}
--- give an outline of the algorithm ---

\begin{itemize}
\item Complexity of the algorithm.
\item Application of the algorithm.
\end{itemize}

\subsection{Shortest Spanning Trees}
\begin{itemize}
\item Spanning tree.
\item Shortest spanning tree.
\item Kruskal's greedy algorithm for shortest spanning trees.
 --- give an outline ---
\item Application of Kruskal's algorithm.
 --- give an outline ---
\item General properties of trees.
\end{itemize}

\subsection{Prim's Algorithm for Shortest Spanning Trees}
--- give a summary ---
\subsubsection{Application of Prim's Algorithm}
--- give a summary ---

\subsection{Networks}
\begin{itemize}
\item Define network, capacity, source, target, sink, forward/backward edgs, etc.
\item Flow augmenting paths. --- give a definition ---
\item Cut sets.
\begin{itemize}
\item Definition.
\item Theorem (net flow in cut sets).
\item Theorem (upper bound for flows).
\item Main Theorem (augmenting path for flows).
\item Theorem (max-flow min-cut theorem).
\end{itemize}
\end{itemize}

\subsection{Ford-Fulkerson algorithm for Max Flow}
--- summary and application of the algorithm ---

\subsection{Assignment Problems}
---Bipartite Matching--- define bipartite graph.
\begin{itemize}
\item Matching.  --- give an outline ---
\item Max cardinality matching. --- Algorithm: bipartite maximum cardinality matching.
Example: Maximum cardinality matching.
\item Alternating path.
\item Augmenting path. --- Theorem: augmenting path for bipartite matching ---
\end{itemize}

{\underline{Timetabling and Matching}} {\it example (1)}:
Let $x1$, $x2$, and $x3$ represent 3 teachers teaching 4 classes $y_1$, $y_2$, $y_3$,
and $y_4$ for these time periods:

\begin{table}[htb]
\vspace{0.25cm}
$$
\begin{tabular}{|l||c|c|c|c||}
\hline
        &  $y_1$  &  $y_2$  &  $y_3$  &  $y_4$ \\
        &         &         &         &         \\ \hline\hline
x1  &   1     &   0     &    1    &    1   \\ \hline
x2  &   1     &   1     &    1    &    1   \\ \hline
x3  &   0     &   1     &    1    &    1   \\ \hline
\end{tabular}
$$
\label{table.1}
\end{table}

A teaching schedule with the smallest possible number of periods can be set up as follows:

\begin{table}[htb]
\vspace{0.25cm}
$$
\begin{tabular}{|l||c|c|c|c||}
\hline
        &   1     &   2    &   3   &  4   \\
        &         &        &       &       \\ \hline\hline
x1  &  $y_4$  &  $y_3$  &  $y_1$  &  -  \\ \hline
x2  &  $y_1$  &  $y_4$  &  $y_3$  &  $y_2$  \\ \hline
x3  &    -    &  $y_2$  &  $y_4$  &  $y_3$  \\ \hline
\end{tabular}
$$
\label{table.2}
\end{table}

So in general the above teaching schedule can be represented by a 
bipartite graph $G$. A teaching schedule for one period corresponds 
to a ``matching'' in $G$.

{\underline{Timetabling and Matching}} {\it example (2)}:
Suppose we have $n$ classes and $m$ teachers. Let the sign X to
indicate which class to be taught by which teacher(s) (one lesson of
one hour a day).

\begin{table}[htb]
\vspace{0.25cm}
$$
\begin{tabular}{|l|l||c|c|c|c|c|c||}
\hline
Classes  --$>$ &        &   1    &   2   &   3   &   4   &   5  &  6  \\ \hline\hline
Teachers: &  A   &   X    &   X  &        &   X   &       &      \\ \hline
                 &  B   &   X    &       &    X  &   X   &   X  &     \\ \hline
                 &  C   &         &   X   &        &   X   &   X  &     \\ \hline
                 &  D   &         &   X   &        &         &        &  X  \\ \hline
                 &  E    &   X   &         &   X   &        &   X   &  X  \\ \hline
                 &  F    &   X   &        &    X   &   X   &       &   X  \\ \hline
                 &  G   &         &        &    X   &        &    X  &   X \\ \hline
\end{tabular}
$$
\label{table.3}
\end{table}

Next, construct a bipartite graph $G$.  Fixing the time periods, the problem becomes 
a {\it matching} problem. See Figure \ref{fig-2}.
\begin{figure}[htb]
\centerline{\psfig{figure=class_teacher_graph2.eps,height=350pt,width=280pt}}
\vspace{0.75cm}
\caption{Teachers-classes bipartite graph.}
\label{fig-2}
\end{figure}

\subsection{Summary (A)}
\begin{itemize}
\item Graph [ vertices - edges - digraph ].
\item Shortest Path Problem [ Dijkstra's algorithm - Moore's algorithm ].
\item Tree [ shortest spanning tree - Kruskal's  algorithm - Prim's algorithm ].
\item Network [ Ford-Fulkerson algorithm - flow augmenting paths - cut set ].
\item Bipartite Graph [ matching - maximum cardinality matching ].
\end{itemize}

\subsubsection{Matching Algorithms}
--- DFS --- BFS --- summary of simplex algorithm ---

\subsubsection{The Labeling Algorithm}
--- summary ---

\subsubsection{The Transportation Problem}
--- uses costs  instead of capacities ---

\begin{itemize}
\item Transportation algorithm.
\item Optimal assignments.
\item Minimum cost flow.
\item Transshipment problem.
\end{itemize}

\subsection{Summary (B)}
\subsubsection{Linear Programming}
\begin{itemize}
\item Minimize $c x$ with $A x = b$, $x \ge 0$.
\item Extreme points of feasible sets.
\item Inequality constraints.
\end{itemize}

\subsubsection{The Simplex and Karmarkar's Methods}
\begin{itemize}
\item Simplex method --- moving along edges of the feasible set.
\item The algebra of a simplex step --- entering variable and leaving variable.
\item Karmarkar's method --- projection, descent, and rescaling.
\end{itemize}

\subsubsection{Saddle Points (Minimax) and Game Theory}
\begin{itemize}
\item Inequality constraints and competitive equalibrium --- production and prices.
\item Sensitivity analysis.
\item Game theory --- a saddle point for football.
\item Minimax theorem --- maximum for X = minimum for Y.
\item Escape and wedding game --- optimal strategies for matching.
\end{itemize}

\subsection{Optimization and Nonlinear Programming}

\begin{itemize}
\item Convex functions --- second derivative is positive semidefinite.
\item Convexity and duality --- theory of constraint optimization.
\item Conjugate convex functions --- $F^{*}(y) = max[xy - F(x)]$.
\item Applications: minimum norms --- network flows --- distance to a plane , etc.
\end{itemize}

\subsection{References}
\begin{enumerate}
\item G. Strang, Introduction to Applied Mathematics. 1986.
\item E. Kreyszig, Advanced Engineering Mathematics. 1993
\item A. Schrijver, A Course in Combinatorial Optimization. To appear 1996.
\item T. Cormen, C. Leiserson, and R. Rivest, Introduction to Algorithms. 1990.
\end{enumerate}

\section{References on the World Wide Web}
\begin{enumerate}

\item {\underline{http://www.wiwi.uni-frankfurt.de/~stockhei/progs/index.html}} :
This is a demonstration of different heuristics for the TSP tour planning. Choices are: 
     (1) 2opt ... Optimize by a simple two Corner exchange. 
     (2) 3opt ... Optimize by exchanging three Corners. 
     (3) OR-opt ... A restricted 3opt algorithm. 
     (4) Nearest ... Find the nearest free neighbour. 
     (5) Reset ... Repaints the last unchanged tour.
     (6) New ... Generates a new Tour. 

\item{\underline{http://langevin.usc.edu/BST/}} :
Interactive animations of several types of binary search trees.

\item{\underline{http://www.aist.go.jp/NIBH/~b0616/Lab/Links.html}} :
This page contains a list of pointers to various applets to tackle some 
hard problems such as the TSP. These applets implement neural nets and artificial 
life algorithms.

\item{\underline{http://solon.cma.univie.ac.at/~neum/glopt.html}} :
A good site containing various optimization methods. There are also various 
pointers to different optimization code, etc.

\item{\underline{ftp://parcftp.xerox.com/pub/dynamics/constraints.html}} :
This is the main site covering ``phase transitions'' in search. A number of papers 
can be obtained from there.

\item{\underline{http://docker.library.uwa.edu.au/matt/applets/annealing.html}} :
An interesting SA applet with the aim of finding global extrema ... 
The applet shows a plot of the energy terrain where the max or min is shown. 
The plot has a set of parameter control bottons for 
setting the parameters, etc. No source is included there.

\item{\underline{http://www.cs.pace.edu/~carla/graph.html}} :
It describes Dijkstra's well known algorithm to determine the shortest paths in 
a graph from a given startpoint to any other point. The Dijkstra shortest path 
algorithm is decribed in many books, such as Intro to Algorithms by CLR. 
The applet (written by someone at Pace Univ) is interesting; it gives the user 
lots of control over the location of the nodes and the weights between them.
Also allow drawing the nodes and the connections, etc.  Each step in the 
algorithm is explained with a short text shown in a special text area, etc.  
The java source is included.

\item{\underline{http://aleph0.clarku.edu/~djoyce/java/Geometry/Geometry.html}} :
This applet is  used to illustrate Euclid's elements. It also  illustrates 
Euler line of a triangle. Overall, a very nice tool for showing in a clear geometric 
fashion  Euclid's elements. Source is included.

\item{\underline{http://www.on.net/users/zhcchz/central.html}} :
The owner of this page writes ``The impression most people have after their first 
statistics course is that all distributions of random phenomena in the universe are 
of the Normal/Gaussian  variety. While there are plenty of others around, the Normal 
curve explains a remarkable range of biological measurements such as the heights 
of adult humans. The Quincunx is a device which allows a bead to drop through 
an array of pins stuck in a board.'' It is cool and source included.

\item{\underline{http://www.research.ibm.com/people/c/chaitin/lm/}} :
Chaitin demonstrating the limit of mathematics in this page. A java applet is included.

\item{\underline{http://www.physics.carleton.ca/courses/75.502/slides/intro/index.html}} :
This page contains few sets of computational physics slides on chaos, monte carlo, etc.

\item{\underline{http://weber.u.washington.edu/~cvj/animalp.html}} :
Anima-LP allows one to enter constraints using a spread-sheet-like interface 
and see the corresponding graphical representation. Coefficients, right-hand 
side values can all be changed using the spreadsheet like interface. The java 
version doesn't come with source code, only classes.

\item{\underline{http://weber.u.washington.edu/~cvj/tsp/tspnew.html}} :
From the page ``Euclidean traveling salesman problem can be stated as follows:
Given n cities located in the plane, find the shortest route that visits all the 
cities exactly once and returns to the starting city. 
For the Euclidean Traveling Salesman Problem, we consider the question of 
how the optimal solution changes when a city is moved. Of course, cities do 
not move, so this particular problem may be moot. Given the extensive research 
on the traveling salesman problem, results developed for it may be applicable 
to other combinatorial optimization problems. The problem forms one of the 
canonical problems in the field of combinatorial optimization. 
Many new algorithmic techniques first saw application to the traveling salesman 
problem. Hundreds of heuristics have been developed that can produce good, 
but not necessarily optimal routes.'' No source is included with applets  ... 

\item{\underline{http://www.dk-online.dk/users/hagerup/java/tstdk.htm}} :
Another TSP applet (nice) with source code ...

\item{\underline{http://www.cs.utah.edu/~bbachman/gtutor/}} :
A general graphics tutorial ... Teaching how to do graphics in general. (nice)

\item{\underline{http://www-courses.cs.uiuc.edu:80/~c-medina/mp1/}} :
Round-Robin Scheduling in Java: A nice scheduling applet with some 
explanations such as:  (1) What is Round-Robin Scheduling? 
(2) Round-Robin Analysis  (3) How the simulation is implemented 
(4) The display (5) The source code  (6) The Round-Robin Simulation.

\item{\underline{http://alumni.caltech.edu:80/~ingber/}} :
SA archive for papers and code of Ingber's work.

\item{\underline{http://www.taygeta.com/annealing/simanneal.html}} :
Simulated annealing references and software packages written in C and C++.

\item{\underline{http://www.maths.uq.oz.au/~ch/bookmarks.html}} :
A nice collection of optimization and operation research links.

\item{\underline{http://www.maths.mu.oz.au/~worms/digest/digest.html}} :
A nice digest that contain a list of relavent operation research topics.

\item{\underline{http://www.st.rim.or.jp/~kanada/combinatorial.html}} :
Containing some quite useful pointers including one to our work from 2 years ago :-)

\item{\underline{http://www.thep.lu.se/tf2/complex/article.complex.html}} :
A list of publications for Peterson's Potts model.

\item{\underline{http://www.isor.vuw.ac.nz/~grant/Tabu.html}} :
A short and informative description of Tabu Search.

\item{\underline{http://rtm.science.unitn.it/}} :
Battiti's reactive Tabu Search stuff.

\item{\underline{ttp://www.isor.vuw.ac.nz/~grant/research1.html}} :
This page contains a useful summary of various heuristic algorithms as well as 
pointers to:  1. Local Search   2. Simulated Annealing   3. Genetic Algorithms  
4. Threshold  Accepting Methods (i.e. the Great Deluge Algorithm et al.)  
5. Tabu Search .

\item{\underline{http://fi-www.arc.nasa.gov/fia/projects/xfr/papers/benchmark-article.html}} :
Scheduling Benchmarks and Related Resources.

\item{\underline{http://www.mcs.anl.gov/home/otc/otc.html}} :
Homepage of the optimization tech. center at Argonne.

\item{\underline{http://ucsu.colorado.edu/~xu/software.html}} :
From the page ``This list is a collection of codes for optimization and related fields. 
Most codes are in public domain and can be retrieved via anonymous ftp. 
The collection concentrates on codes in network optimization, graph theory and 
other combinatorial optimization problems.''

\item{\underline{http://www-math.cudenver.edu/~hgreenbe/glossary/glossary.html}} :
This contains terms specific to mathematical programming, and some terms from other 
disciplines, notably mathematics, that are directly related.

\item{\underline{http://www.ing.unlp.edu.ar/cetad/mos/}} :
A very extensive collection of software, approaches, and algorithms on the TSP. (very nice)

\item{\underline{http://lancet.mit.edu/galib-2.4/}} :
GAlib is a set of C++ genetic algorithm objects. The library includes tools for using 
genetic algorithms to do optimization in any C++ program.

\item{\underline{http://www.pronex.com/atsp/download.html}} :
A coolection of TSP software, documents, and test problems.

\item{\underline{http://www.research.ibm.com/osl/osl}} :
This page is for IBM optimization subroutine library (OSL).

\item{\underline{ftp://orion.uwaterloo.ca/pub/henry/software/readme.html}} :
Software, papers, and background, related to the research of Wolkowicz is available in fortran
and/or matlab.

\item{\underline{http://pespmc1.vub.ac.be/ASC/OPTIMIZATIO.html}} :
PRINCIPIA CYBERNETICA WEB: contains a good collection of optimization resources.

\item{\underline{http://www.uni-paderborn.de/fachbereich/AG/agmadh/WWW/english/scripts.html}} :
A collection of papers, surveys, and lecture notes .... (slow connection).

\item{\underline{http://www.cs.purdue.edu/homes/cmh/electrobook/intro.html}} :
An Electronic Primer on Geometric Constraint Solving: Theoretical Foundations and 
implementation Issues.

\item{\underline{http://www.ics.uci.edu/~eppstein/gina/constraint.html}} :
Geometry in Action: Constraint Solving - part of the computational geometry work.

\item{\underline{http://gams.nist.gov/}} :
Guide to Available Mathematical Software.


\item{\underline{http://dmawww.epfl.ch/~rochat/$rochat_data$/orms.html}} :
Lots of stuff about operations research.

\item{\underline{http://cfatab.harvard.edu/nr/nronline.html}} :
Those numerical recipes (C and Fortran) books are online.

\item{\underline{http://www.ics.uci.edu/~eppstein/161/glossary.html}} :
A very nice glossary related to design and analysis of various optimization
algorithms.

\item{\underline{ftp://parcftp.xerox.com/pub/dynamics/multiagent.html}}
The page of dynamic computation group at Xeros Parc. Has lots of pointers to
optimization related issues.

\item{\underline{http://www.imada.ou.dk/Research/graphcol.html}} :
Graph coloring archives ...

\item{\underline{http://mat.gsia.cmu.edu/}} :
The main page of operation research. 
\end{enumerate}

\clearpage
\section{Glossary}

\begin{itemize}
\item {\bf\Large Binary partition set:} A binary partition set is one whose
partitions are defined by only two localities at each degree.

\item {\bf\Large Binary string:} A binary or bit string is a string whose
genes can take on a value from the binary alphabet (\{0,1\}).

\item {\bf\Large Branch and bound algorithm:} A branch and bound algorithm
works by partitioning the solution space and ruling out subsets when
they can be judged as worse than others (e.g. are known not to contain
the optimum solution).

\item {\bf\Large Chromosome:} A chromosome (in genetic algorithms) is a
particular data structure of a solution, usually a string.

\item {\bf\Large Coding:} The coding defines the way solutions in an
optimization algorithm are represented and operated on.

\item {\bf\Large Crossover:} Crossover is a genetic operator which, from
two parent solutions, produces two child solutions who have shared the
parents' solution data. In the bit string situation, crossover is
usually achieved by splicing over a single pivot.

\item {\bf\Large Evolution:} Evolution is the process of optimization by
biased selection on a population of genetically coded solutions in
order to produce new generations through the application of various
operators. 

\item {\bf\Large Genetic algorithm:} A genetic algorithm maintains a
population of genetically coded solutions to which is continually
applied a number of operators including: selection, crossover, and
mutation.

\item {\bf\Large Global optimization:} Global optimization is the process of
finding the best (or a high quality) solution over the entire solution
space.

\item {\bf\Large Nonlinear programming:} Nonlinear programming is a general
term for gradient based hillclimbing systems used to try and optimize
nonlinear problems.

\item {\bf\Large Tabu search:} Tabu search is a navigation algorithm which
uses memory structures of varying complexity to control the efficiency
of the search.

\item {\bf\Large Temperature (in SA):} The level of temperature defines the
degree to which detrimental steps are acceptable. As temperature
drops, detrimental steps are less and less acceptable (depending on
their magnitude).
\end{itemize}

...... more to br added ........

\clearpage
%\newpage
\begin{thebibliography}{SEPC}

\bibitem{1}
J. Hopfield and D. Tank, ```Neural' computation of decisions in
optimization problems,'' {\it Biol. Cybern}, 52 (1985), 141-152.

\bibitem{2}
C. Reeves, editor. {\it Modern Heuristic Techniques for Combinatorial
Problems}, chapter 4, John Wiley and Sons, 1993.

\bibitem{3}
A. Schrijver, {\it Theory of Linear and Integer Programming}. John
Wiley and Sons, Chichester, UK (1986).

\bibitem{4}
A. Schrijver, {\it A Course in Combinatorial Optimization}, to appear
1996.

\bibitem{5}
C. Papadimitriou and M. Yannakakis, 
``Note on recognizing integer polyhedra,'' {\it Combinatorica},
10(1):107-109, 1990.

\bibitem{6}
Gerhard Reinelt,
{\it The Traveling Salesman, Computational Solutions for TSP
Applications}, Springer-Verlag (1994).

\bibitem{7}
Peterson, S$\ddot{o}$derberg,
``A New Method for Mapping Optimization Problems onto Neural Nets,''
{\it International Jr. of Neural Systems} 1, 3 (1989).

\bibitem{8}
Gisl$\acute{e}$n, S$\ddot{o}$derberg, Peterson, 
``Teachers and Classes with Neural Nets,'' {\it Inter. Jr. of Neural
Systems} 1, 167 (1989). 

\bibitem{9}
Gisl$\acute{e}$n, S$\ddot{o}$derberg, Peterson, ``Scheduling High
Schools with Neural Nets,'', Lund University Preprint LU-TP-91-9,
Lund, Sweden (1991).

\bibitem{10}
S. Elmohamed, G. Fox, P. Coddington, and H. Yau, ``Mean field
annealing and class scheduling,'', Manuscript, NPAC, Syracuse
University, 1995.

\bibitem{11}
E, Aarts and J. Korst, ``Boltzmann machines for traveling salesman
problems,'' {\it European J. of Operational Research} 39 (1989),
79-95.

\bibitem{12}
Silver, E.A., R.V.V. Vidal and D. de Werra,
``A tutorial on heuristics,'' {\it European J. of Operational
Research} 5 (1980), 153-162.

\bibitem{16}
Forest, Richard,
{\it Ensemble of Simulated Annealing}, SDSC, San Diego, California, 1994.

\bibitem{17}
Van Laarhoven, and Aarts,
Simulated Annealing: Theory and Applications. D. Reidel,
Dordrecht (1987).

\bibitem{18}
D. Johnson, C. Aragon, L. McGeoch, and C. Schevon,
``Optimization by Simulated Annealing: an Experimental Evaluation, Part
I (Graph Partitioning),'' {\it Operations Research} 37, 865-892 (1989).

\bibitem{19}
D. Johnson, C. Aragon, L. McGeoch, and C. Schevon,
``Optimization by Simulated Annealing: an Experimental Evaluation, Part
II (Graph Coloring and number partitioning),'' {\it Operations
Research} 39, No. 3, 865-892 (1991).

\bibitem{39}
Applied Simulated Annealing, Rene Vidal (ed.), Lecture
Notes in Economics and Mathematical Systems no. 396, Springer-Verlag,
1993.

\bibitem{55}
N. Boissin, and J.-L. Lutton, ``A parallel simulated annealing
algorithm,'' {\it Parallel Computing} 19, 859-872, 1993.

\bibitem{56}
M. G. A. Verhoeven, and Emile H. L. Aarts, ``Parallel local search
techniques,'' Manuscript, Philips Research Laboratories, Eindhoven,
The Netherlands, 1995.

\bibitem{57}
Emile Aarts, Jan Korst, and Peter von Laarhoven, ``Simulated
annealing,'' in Local Search in Combinatorial Optimization,
E. H. Aarts and J. K. Lenstra (eds.), John Wiley and Sons, UK (to
appear in 1996).

\bibitem{58}
A. Hertz and D. de Werra, ``The tabu search metaheuristic: how we used
it,'' {\it Annals of Mathematics and Artificial Intelligence}, 1
(1990) 111-121.

\bibitem{59}
F. Glover, ``Tabu search fundamentals and uses,'' Manuscript, School
of Business, University of Colorado, Boulder, CO, May 1994.

\bibitem{60}
F. Glover, ``Multilevel tabu search and embedded search neighborhoods
for traveling salesman problem,'' Manuscript, School of Business,
University of Colorado, Boulder, CO, May 1991.

\bibitem{61}
S. R. White, ``Concepts of scale in simulated annealing,'' In {\it
Proceedings of the IEEE International Conf. on Circuit Design (ICCD)},
pages 646-651, 1984.

\bibitem{62}
R. H. J. Otten and L. P. P. van Ginneken, The Annealing
Algorithm. Kluwer Academic Publishers, 1989.

\bibitem{63}
J. Lam and J.-M. Delosome, ``An efficient simulated annealing
schedule: Derivation,'' TR 8816, Yale University, Dept. of Computer
Science, Sept. 1988.

\bibitem{64}
M. Lundy and A. Mees, ``Convergence of the annealing algorithm,'',
{\it Mathematical Programming}, 34, 111-124, 1986.

\bibitem{65}
J. Thompson and K. Dowsland, ``Examination timetabling by simulated
annealing,'' E.B.M.S, Swansea University, Swansea, UK 1994/95.

\bibitem{66}
M. Huang, F. Romeo, and A. Sangiovanni-Vincentelli, ``An efficient
general cooling schedule for simulated annealing,'' In {\it
Proceedings of the International Conf. on Computer-Aided Design
(ICCAD)}, pp 381-384, 1986.

\bibitem{67}
J. Lam and J.-M. Delosme, ``An efficient simulated annealing schedule:
Implementation and evaluation,'' TR 8817, Yale University, Dept. of
Computer Science, Sept. 1988.

\bibitem{68}
F. Catthoor, H. de Man and J. Vandewalle, ``SAMURAI: a general and
efficient simulated-annealing schedule with fully adaptive annealing
parameters,'' {\it Integration, the VLSI Journal}, 6, 147-178, 1988.

\bibitem{69}
C. H. Papadimitriou and K. Steiglitz, Combinatorial Optimization:
algorithms and complexity. Prentice Hall, 1982.

\bibitem{70}
J. J. Hopfield, ``Neurons with graded response have collective
computational properties like those of two-state neurons,'' {\it
Proceedings of the National Academy of Science, US}, 81, 3088-3092
(1984).

\bibitem{71}
David Johnson,
``Local Optimization and the TSP,'' {\it Springer Lecture Notes in
Computer Science} 443, 446-461, Springer-Verlag, 1990.

\bibitem{72}
D. Johnson and L. McGeoch, ``The Traveling Salesman Problem: A Case
Study in Local Optimization,'' in Local Search in Combinatorial
Optimization, E. H. Aarts and J. K. Lenstra (eds.), John Wiley and
Sons, UK (to appear in 1996).

\bibitem{73}
R. Durbin and D. Willshaw, ``An analogue approach to the traveling
salesman problem using an elastic net method,'' {\it Nature} 326
(April 16, 1987), pp 689-691.

\bibitem{74}
T. Kohonen, Self-Organization and Associative Memory, Springer-Verlag,
Berlin, 1988.

\bibitem{75}
R. Durbin, R. Szeliski, and A. Yuille, ``An analysis of the elastic
net approach to the traveling salesman problem,'' {\it Neural
Computation} 1 (1989), pp. 348-358.

\bibitem{76}
J. Holland, ``Genetic Algorithms,'' {\it Scientific American} 1,
vol. 267, pp 66-72, July 1992.

\bibitem{77}
J. Bentley, ``Experiments on traveling salesman heuristics,'' 1st
annual ACM-SIAM Symposium on Discrete Algorithms, pp. 91-99, San
Francisco, CA \, Jan 1990.

\bibitem{78}
S. Lin and B. Kernighan, ``An effective heuristic algorithm for the
traveling salesman problem,'' {\it Operations Research} 21,
pp. 498-516, 1973.

\bibitem{79}
S. Elmohamed, G. Fox, P. Coddington, and H. Yau, ``Simulated annealing
and class scheduling,'', Manuscript, NPAC, Syracuse University,
January 1996.

\bibitem{80}
A. Hertz, E. Taillard, and D. de Werra, ``Tabu Search,'' 
in Local Search in Combinatorial Optimization, E. H. Aarts and
J. K. Lenstra (eds.), John Wiley and Sons, UK (to appear in 1996).

\bibitem{81}
D. Costa, ``A Tabu Search algorithm for computing an operational
timetable,'' European Journal of Operational Research (EJOR), 76,
(1994), 98-110.

\end{thebibliography}
\end{document}








