\begin{slide}
\small
\begin{center}
\thicklines
\setlength{\unitlength}{0.7cm}
\begin{picture}(14.5,12)(-7.25,-6)

\multiput(-5.5,-1.45)(0,1.75){2}{\framebox(11,1.15){}}

\multiput(-1.45,-5.5)(1.75,0){2}{\framebox(1.15,11){}}

\multiput(-3.75,-2.35)(6.35,0){2}{\framebox(1.15,4.7){}}

\multiput(-2.35,-3.75)(0,6.35){2}{\framebox(4.7,1.15){}}

\multiput(-2.9,0)(2.9,-2.9){2}{\line(1,1){2.9}}

\multiput(-2.9,0)(2.9,2.9){2}{\line(1,-1){2.9}}

\end{picture}
\end{center}

\Huge
\begin{center}
Saleh Elmohamed\\
saleh@npac.syr.edu\\
\end{center}

\begin{center}
Approximation Algorithms and Heuristics
\end{center}
\end{slide}


\begin{slide}
{\bf\underline{Hard Constraints of Timetabling}}

The most common and important hard constraint is what is sometimes
referred to as an {\it edge} constraint between two events. This
reference is due to the similarity of any {\bf simple} timetabling
problem with {\it vertex coloring} in graph theory; which simply
states that any given pair of events ${\bf e_1}$ and ${\bf e_2}$ must
not overlap in time.
\end{slide}


\begin{slide}
{\bf\underline{Graph Coloring and Timetabling}}

{\underline{Edge coloring of bipartite graphs}}

For any graph $G = (V, E)$, an edge coloring is a partition $\Pi = \{M_1,
\ldots, M_p\}$ of the set of edges of E, where each $M_i$ is
matching. Also, each of these matchings is called a color.

The edge coloring number is $\chi(G) = min \{|\Pi| | \Pi$ is an
edge coloring of G$\}$. So, if we let $\Delta(G)$ be the maximum degree (
of the vertices) of $G$, clearly, $\chi(G) \geq \Delta(G)$ since
at each v, the edges incident with v should have different colors.

{\underline{Theorem 1}}:

 (due to K\"{o}nig 1916) For any bipartite graph $G = (V,E)$, one has
$ \chi(G) = \Delta(G)\;$. That is, the edge coloring number of
a bipartite graph is equal to its maximum degree.
\end{slide}

\begin{slide}
{\bf\underline{Graph Coloring and Scheduling}}

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{figure}[ht]
\begin{center}
\begin{picture}(305,300)
\psfig{figure=class_teacher.ps,height=305pt,width=300pt,angle=-90}
\end{picture}
\end{center}
\end{figure}
\end{slide}

\begin{slide}
{\bf\underline{Bipartite Graph G}}

Fixing the time periods, the problem becomes a {\it matching} problem
in the above graph.

\begin{figure}[ht]
\begin{center}
\begin{picture}(305,250)
\psfig{figure=class_teacher_graph.ps,height=305pt,width=250pt,angle=-90}
\end{picture}
\end{center}
\end{figure}
\end{slide}

\begin{slide}
{\underline{The question is}}: What is the minimum timespan in which
all classes can be scheduled?
\begin{itemize}
\item Theorem 1 tells us that all classes can be scheduled within
a timespan of 4 hours.
\item Make a bipartite graph $G$ with color classes T = set of teachers
and C = set of classes, where $t \in T$ and $c \in C$ are connected
iff teacher $t$ should teach class $c$; that is if there is an X in slot
$(t,c)$ in the above scheme.
\item $G$ will have a maximum degree $\Delta(G) = 4$, hence according to
Theorem 1, the edge coloring number $\chi(G)$ of $G$ is also $= 4$.
\item The edges of G are colored by 4 colors so that no two edges of
the same color have a vertex in common. That is, we can color the X's
in the above scheme by 4 colors so that there are no two X's of the
same color in any row or column.
\end{itemize}
\end{slide}

\begin{slide}
{\bf\underline{Vertex Coloring}}

Briefly, given a graph $G=(V,E)$ we have to find a coloring of its vertices
with as few colors as possible. The main constraint is that two vertices
linked by an edge should not receive the same color (such coloring are
called feasible coloring). One could define the set $S$ of feasible
solutions as the set of feasible coloring which do not use more than a
given number of colors;.

{\bf\underline{Mapping of Timetabling onto Vertex Coloring}}

\begin{enumerate}
\item The courses are the vertices of a graph.
\item The time periods correspond to the colors.
\item Two vertices are linked by an edge if the corresponding courses
cannot be given at the same time.
\end{enumerate}
\end{slide}

\begin{slide}
{\bf\underline{Vertex Coloring Methods}}

We have looked at three algorithms:
\begin{enumerate}
\item {\bf Saturation} (due to Br\'{e}laz \cite{1}) a successive augmentation
method, referred to as DSATUR.
$\Theta(m)$ implementation was obtained by \cite{4}, where $m$ is the
number of edges in the graph.

\item {\bf RLF} (due to Leighton \cite{2}) a recursive largest first and also a
successive augmentation algorithm. 
The most efficient implementation obtained by \cite{4} in $O(km)$,
where $k$ is the number of colors needed to properly color the graph,
and $m$ is the number of edges.

\item {\bf XRLF} (due to Johnson \cite{3}) which is essentially a
semi-exhaustive version of RLF. Much more complex than the above two.
\end{enumerate}
\end{slide}

\begin{slide}
{\bf\underline{DSATUR Algorithm - exact for bipartite graphs}}

So called because it uses saturation degree.
\begin{enumerate}
\item Arrange the vertices by decreasing order of degrees.
\item Color a vertex of maximal degree with color 1.
\item Choose a vertex with a maximal saturation degree. If there is
a tie, choose any vertex with a maximal degree in the uncolored
subgraph.
\item Color the chosen vertex with the least possible (lowest
numbered) color.
\item If all the vertices are colored, stop. Otherwise, return to step
3.
\end{enumerate}
\end{slide}

\begin{slide}
{\bf\underline{DSATUR - some comments and analysis}}

This algorithm is in average is the most efficient among the
others. The order is constructed as follows:
\begin{itemize}
\item Initially, take any node with the largest possible number of
neighbors and color it with the smallest possible color.
\item Generally, for each node $x$ there is a set $F(x)$ of forbidden
colors (these may be colors which have already been assigned to
neighbors of $x$).
\item At each step we choose a node $y$ for which $|F(y)|$ is maximum
and color it with the smallest possible color.
\end{itemize}

Dsatur is an example of a heuristic procedure for general graphs which
is derived from an exact method for coloring bipartite graphs (for
these graphs, we have $|F(x)| \leq 1$ at each step).
\end{slide}


\begin{slide}
\subsection{Simulated Annealing}
\Large
Let ${\cal N}_{s}$ be the neighborhood of configuration $s$. $k$ is
the Boltzmann constant $=$ 1.
\begin{enumerate}
\item Generate an initial solution (configuration) $s$ .
\item Compute cost of $s$ :  $C(s)$.
\item Compute initial temperature $T_0$.
\item Set the temperature $T\; =\; T_0$.
\item While \underline{stop criterion} is not satisfied do:
\begin{enumerate}
\item Repeat \underline{Markov chain length} (M) times:
\begin{enumerate}
\item Select a configuration $s^{'} \subset {\cal N}_{s}\;$.
\item Let $\Delta = C(s^{'}) - C(s)\;$.
\item If ($\Delta \leq 0$ $\{$downhill move$\}$), set $s = s^{'}\;$.
\item If ($\Delta > 0$ $\{$uphill move$\}$), set $s = s^{'}$ with a
probability $= e^{-\Delta /(k T)}\;$.
\end{enumerate}
\item Reduce (or update) temperature $T$.
\end{enumerate}
\item Return the solution  $s$.
\end{enumerate}
\end{slide}


\begin{slide}
\subsection{The Annealing Schedules}

{\underline{Some background}}

\begin{enumerate}
\item In combinatorial optimization problems, 
\underline{phase transitions} can be observed as sub-parts of the
problem are resolved. Our observations are that: [1]  At high
temperatures, the gross structure of the solution is resolved. [2]
At low temperatures, the minute details of the solution are resolved.

\item Applying a reheating (or an adaptive) type schedule, depending
on the phase, would allow the algorithm to spend more time in the low
temperature phases, thus reducing the total amount of time required to
solve a given problem.

\item To calculate the temperature at which a phase transition occurs,
it is necessary to compute what is called the \underline{specific
heat} of the substance. A \underline{phase transition} occurs at a
temperature $T_{msp}$, when the specific heat is maximal, and this
triggers the change in the state ordering.

\item If the best solution found to date is poor (i.e. has a high
energy or cost) then the super-structure may require
re-arrangement. This can be done by raising the temperature to a level
which is higher than the phase transition temperature
($T_{msp}$). Generally, the higher the best cost so far, the higher
the temperature which is required to escape the local minimum.
\end{enumerate}
\end{slide}

\begin{slide}
\subsection{Mapping of Timetabling into Annealing Algorithm}

The most obvious mapping of timetabling (TTS) involves the following:
Let $Max_p$ = maximum number of classes assigned to any professor.
\begin{enumerate}
\item a {\bf state} is a timetable containing the following sets:
\begin{itemize}
\item P: a set of professors.
\item C: a set of classes.
\item S: a set of students.
\item R: a set of classrooms.
\item ${\cal I}$: a set of time periods.
\end{itemize}
\item a {\bf cost} or ``energy'' E(P, C, S, R, ${\cal I}$) such that:
\begin{itemize}
\item E(P): is the cost of assigning more than $Max_p$ classes to the
same professor, plus scheduling one or more courses that causes a conflict
in the professor's schedule.

\item E(C): is the cost of scheduling certain classes within the
same time period in violation of the exclusion constraint, for
example.

\item E(S): is the cost of having two or more classes conflict in
time; plus cost of having in the schedule one or more classes that
really don't meet the student's major, class requested, or course
requirements; plus the cost of not having the courses evenly spread
over the week, etc. 

\item E(R): is the cost resulting from assigning room(s) of the wrong
size and/or type to a certain class.

\item E(${\cal I}$): is the cost of having more or less time periods than
required, plus cost of an imbalanced class assignments (a certain
period will have more classes assigned to than others, etc.).

\item a {\bf swap} (or exchange) of classes : 
class $c_i$ with class $c_j$ in the set $C$ with respect to time
periods ${\cal I}_i$ and ${\cal I}_j$, and/or with respect to
classroom $R_i$ and $R_j$, respectively.
\end{itemize}
\end{enumerate}
\end{slide}

\begin{slide}
{\bf\underline{Some notes on SA implementation}}

\begin{itemize}
\item Depending on the given problem, SA appears competitive
with many of the best local optimization methods.
\item 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.
\item 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. 
\end{itemize}
\end{slide}

\begin{slide}
\begin{thebibliography}
\large
\bibitem{1}
Br\'{e}laz, D. ``New Methods to Color the Vertices of a Graph'', 
{\it Communications of the ACM}, 1979, {\bf 22}(4), 251-6.

\bibitem{2}
Leighton, F.T. ``A Graph Coloring Algorithm for Large Scheduling Problems,''
{\it Journal of Research of the National Bureau of Standards}, 1979, 
{\bf 84}(6), 489-506.

\bibitem{3}
Johnson, D.S., et al.  ``Optimization by Simulated Annealing: An
Experimental Evaluation; Part II, Graph Coloring and Number
Partitioning,'' {\it Operations Research}, 1991, {\bf 39}(3), 378-406.

\bibitem{4}
C. Morgenstern and H. Shapiro, ``Improved implementations of dynamic
sequential coloring algorithms,'' TR CoSo-1991-4, TCU, Fort Worth,
Texas, 1991.

\bibitem{5}
S. Kirkpatrick, C. D. Gelatt, Jr., and M. P. Vecchi, ``Optimization by
Simulated Annealing,'' {\it Science} 220 (13 May 1983), 671-680.

\bibitem{6}
Elmohamed, S., et al. ``Mean field annealing, simulated annealing, and
non-Euclidean combinatorial optimization problems: The case of
academic course scheduling, (Part I: algorithms, Part II:
implementations),'' NPAC preprint.

\end{thebibliography}
\end{slide}



