\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}
\Large
\begin{center}
Saleh Elmohamed
NPAC,  saleh@npac.syr.edu
\end{center}
\end{slide}

\begin{slide}
\subsection{Academic Scheduling at the University Level} 
\Large
{\bf\underline{Definition}}

For a certain school, given $N_p$ teachers, $N_q$ classes, $N_x$
classrooms or lecture halls, and $N_s$ students; it is required
to schedule $N_l$ lessons (defined as teacher-class pairs) within a
time limit of $N_t$ lesson periods (or time slots). 

A suitable schedule needs to be found such that no (teacher, class,
student) is in more than one place at a time, and no lecture hall is
expected to accommodate more than one lesson at a time or more
students than its capacity. 
\end{slide}

\begin{slide}
\subsection{Complexity of Timetabling (TTS)}
\Large

\begin{itemize}
\item $TTS$ is a pure constraint satisfaction problem and it is essentially
an example of a resource-constrained multiprocessor scheduling problem,
which is an NP-complete problem.

\item The problem has been approached by means of linear programming (LP) with
binary variables plus some heuristics. 

\item Using the LP representation, for a set as small as 20 teachers,
30 time-intervals, and 10 classes, the problem would be represented by
6000 variables. This makes the problem intractable.

\item The overall complexity of timetabling is in the order of 
$2^{{(N_c N_x N_t)}^a}$, for some  $a \ge 1$.

\end{itemize}

For a much simpler problem, which is the {\it class allocation} (no
timetabling part included), using LP, the computational load ($n_c$)
scales as follows:

$\;\;\;\;\;\;\;\;n_c \propto N^3_c N^2_x N^3_t\;\;,$
where $N_c$ is the number of room categories (i.e. classroom,
auditorium, etc.).
\end{slide}

\begin{slide}
\subsection{The timetabling constraints}
\Large

In a nutshell, timetabling is the assignment of time slots to a set of
events, {\bf subject to} constraints on these assignments.

These constraints are divided into three types:
\begin{enumerate}
\item Hard.
\item Medium.
\item Soft.
\end{enumerate}

{\bf\underline{Hard Constraints}}
\Large
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. [more on this, shortly]
\end{slide}

\begin{slide} 
{\bf\underline{Examples of hard constraints}}

\begin{itemize}
\item Events ${\bf e_1}$ and ${\bf e_2}$ can be viewed as two classes
taught by the same professor, or one is a class and the other is a
recitation or lab of the same class, etc.

\item Events ${\bf e_1}$ and ${\bf e_2}$ are directly connected if
their associated classes do not overlap in time.

\item A class can not be assigned to a particular room unless {\it
size of the room} $\geq$ {\it the class enrollment}. The smaller the
difference between these two sizes the better the assignment is.

\item If teachers are allocated automatically, specific weekly limits
are enforced, as well as limits of how many times various types of
classes are taught.

\item Other constraints are those directly related to students such as:
\begin{itemize}
\item To sign up for a class or section, it must be open.
\item Eligibility criteria for the section must be met, etc.
\end{itemize}
\end{itemize}
\end{slide}

\begin{slide}
{\bf\underline{Medium Constraints}}

These kinds of constraints do not deal with time conflicts but
do have a high cost attached to them. Also, this cost is not as
high as that associated with the hard constraints. In the final
(legal) schedule the cost of these constraints is minimized and it is 
quite preferable to reduce it to $0$. 

{\bf\underline{Examples of medium constraints}}
\begin{itemize}
\item For each student, balance {\it MWF} and {\it TuTh} sections.
\item Balance or spread out the lectures over the week.
\item Classes may request contiguous time slots.
\item Classes may be grouped with other classes.
\item The overall schedule should have as few ``holes'' as possible;
that is lessons should be glued together, etc.
\end{itemize}
\end{slide}

\begin{slide}
{\bf\underline{Soft Constraints}}

Do not deal with time conflicts and have a low cost associated
with them. Also, in the final schedule, this cost is minimized
but does not often approach zero.

{\bf\underline{Examples of soft constraints}}
\begin{itemize}
\item Balance enrollment in multi-section courses.
\item Lunch and other break times may be specified.
\item Teachers may request periods in which their classes are not taught.
\item Do not enroll athletes in courses that conflict with their sport
practice time, etc.
\end{itemize}
\end{slide}

\begin{slide}
\subsection{Mapping of Timetabling Onto a Graph Coloring Problem}

\Large
{\bf\underline{Graph 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; for example, this upper bound may be the
number of colors used in the initial solution.

{\bf\underline{The Mapping:}}
\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.
\item Additional constraints have to be taken into account and mapped
onto the graph.
\end{enumerate}
\end{slide}

\begin{slide}
\subsection{Interpretation of the Solution Space}
\Large

After setting up or mapping the problem we need to determine the
following: 
\begin{itemize}
\item  {\underline{A feasible solution}} is defined as a schedule that
satisfies a subset ($C^{'}$) of constraints ($C$) : $C^{'} \subseteq C\;$;
provided that all hard constraints are part of $C^{'}\;$.
\item  A neighboring solution is obtained by modifying the current solution
space (i.e. swapping two or more classes in time).
\item  Here are two guidelines in determining whether a given constraint to be
included in $C^{'}$ or not:
\begin{enumerate}
\item  A class should never be assigned to a time period if such an
assignment induces only class schedules that do not satisfy all the
constraints (specifically the hard constraints).
\item  A conflict between two or more classes should not be a
sufficient condition for hindering an assignment.
\item  If all courses last one time period, this is equivalent to changing
the color of a vertex, for example.
\end{enumerate}
\end{itemize}
\end{slide}

\begin{slide}
\subsection{The overall cost function}
\LARGE

The {\it cost function} measures the infeasibility of the current
sloution and may invlove the weighted sum of penalties associated with
different types of feasibility violation.

We consider the following as part of the function:

\begin{itemize}
\item {\underline{Distance cost}}: proportional to the distance between
where the class is assigned and the building which is housing its home
department or school.

\item {\underline{Time period cost}} consisting of : {\bf [1]} class
cost, {\bf [2]} professor cost, {\bf [3]} cost of class spreading over
the week and within each of the weekdays, {\bf [4]} cost of class
glueing and filling in any holes of the timetable, {\bf [5]} room size
cost, and {\bf [6]} students cost which is the sum of various costs
associated with each student, such as eligibility criteria and number
of classes taken by the student.
\end{itemize}
\end{slide}

\begin{slide}
\LARGE
{\bf\underline{The overall cost function} - Continue ... }

\begin{itemize}
\item {\underline{The cost of professor}} is computed from:
{\bf [1]} cost incurred from  assigning more classes than the
maximum number taught by that professor, plus {\bf [2]} cost
from not having a long enough time interval between courses taught by
the same professor, plus {\bf [3]} cost of assigning to the same
professor two or more classes that overlap in time.

\item {\underline{The cost of room size}} is computed in a non-linear
fashion depending on the magnitude of the difference between the class
enrollment and the room size.
\end{itemize}

{\bf Note}: {\em Using summation is not strictly necessary, provided that
the components can be combined in some fashion to reflect the quality
of the solution.}
\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{Physical System - Optimization Problem: An Analogy}
\vspace{0.1cm}
$$
\begin{tabular}{||ccc||ccc||}
\hline
 & Physical System    && Optimization Problem   &&\\ \hline\hline\hline\hline
 &  System State      &&  Feasible Solution     &&\\ \hline
 &  Change of State   &&  Neighbouring 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}
$$
\label{table.0}
\end{slide}

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

{\bf\underline{Geometric Annealing}}
\Large

The new temperature in the above schedule is usually calculated
according to:

\indent
$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;T^{'}\; =\; \alpha\; T\;$ ,

where $\alpha$ is typically in the range $0.95 \ldots 0.99$. 
This schedule is used as a base line for comparison of other
scheduling schemes.

{\bf\underline{Advantages}}
\begin{itemize}
\item Have a good theoretical foundation.
\item Proven history of being good in practice.
\item Well understood by all researchers working on annealing.
\end{itemize}

{\bf\underline{Disadvantages}}

Does not take into account the state of the system in any way, and
thus can not adapt the intensity of the search depending on the
difficulty scale or complexity of the problem.

\end{slide}

\begin{slide}
{\bf\underline{Reheating As a Function of Cost}}
{\bf\underline{Some background}}
\Large

\begin{itemize}
\item In combinatorial optimization problems, 
{\bf 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 type procedure, 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 
{\bf phase transition} occurs, it is necessary to compute the
{\bf specific heat} of the substance. A
{\bf 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{itemize}
\end{slide}

\begin{slide}
\subsection{The Schedule}
\Large

The following is due to Abramson et al. and consists of:

\begin{itemize}
\item Let $C_i$ to denote the cost of configuration $i$, and $k = 1$ (the Boltzmann factor).

\item At $T$, the acceptance prob is: $\;\;\; Pr_i(T) = {e^{-C_i \over {kT}}
\over {\displaystyle \sum_j}{e^{-C_j \over {kT}}}}\;\,.$

\item For a set of configurations ${\cal N}$, the expected cost at $T$:
$\;\;\; <C(T)> = {\displaystyle \sum_{i \in {\cal N}}} C_i Pr_i(T)\,\,.$

\item The expected square cost at $T$: 
$\;\;\; <C^{2}(T)> = {\displaystyle \sum_{i \in {\cal N}}} C_i^2 Pr_i(T)\,\,.$

\item The variance of the cost at temperature $T$ is:
$\;\;\; \sigma^{2}(T) = <C^{2}(T)> - <C(T)>^{2}\,\,.$

\item Now, the maximum specific heat is: $\;\;\; T_{msp} =
{\sigma^{2}(T) \over T^{2}}\,\,$.

\item $T_{new} = P \cdot C_b(s) + T_{msp}\,\,;$

$\;\;\;$ where $T_{new}$ is the reset temperature, P is a constant, and
$C_b(s)$ is the current best cost of the given configuration $s$.
\end{itemize}
\end{slide}

\begin{slide}
\Large
\begin{figure}[h]
\begin{center}
\begin{picture}(370,370)
\psfig{figure=Tmsp.vs.T.ps,height=370pt,width=370pt,angle=-90}
\end{picture}
\end{center}
\vspace{0.25cm}
\centerline{\Large Specific heat ($T_{msp}$) vs. temperature (T).}
\end{figure}
\end{slide}

\begin{slide}
\subsection{Mapping of Timetabling into Annealing Algorithm}
\Large
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.).
\end{itemize}

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

A {\bf swap} which would either decrease or increase the cost of $\Delta E$
is accepted with probability $Pr(\Delta E)$. This probability defines
a Markov chain on $TTS$, and have the distribution in which $Pr(TTS)$
is proportional to $e^{-E(TTS)/T}$. As $T\rightarrow \infty$, the
distribution gives the limiting probability of being at a certain
state of (P, C, S, R, ${\cal I}$).
\end{slide}

\begin{slide}
\subsection{Using a Rule-Based System as a Preprocessor}
{\bf\underline{The System Components}}

This system was developed specifically for the problem of
academic scheduling. The basic data structures system are: 


\begin{itemize}
\item {\bf Distance Matrix} of integer unit values between each
academic department and every other building under use for scheduling.

\item {\bf Course Structure} of each course scheduled anywhere in
campus. These structures are capable of linking with each other.
 
\item {\bf Room Structure} of each room (regardless of type) involved
in the scheduling process. Like courses, rooms are capable of linking.

\item {\bf Time Periods Structure} to keep track of which hour or
time slot is occupied and which is not.

\item {\bf Department-College Structure} many departments belong
to other larger departments or colleges, etc.
\end{itemize}
\end{slide}

\begin{slide}
\subsubsection{The Output of the Rule-Based System}
\Large

The {\it first output} of this system consists of classes, with their
associated professors and students, assigned to various rooms.

The {\it second output} is a list of classes which could not be
assigned due to time/space or other conflict(s).

These two outputs are fed to the main heuristic which can be either a
{\it simulated annealing} or a {\it mean field annealing} to yield a
final legal schedule.

\subsubsection{The Rationale of Using a Preprocessor}
\begin{itemize}
\item It is a good practice when using heuristics such as
simulated annealing, to start at a good point in the search
space or with a partial solution of the problem; regardless of the
difficulty of the problem.

\item A good starting point can only have a positive effect on the
overall solution, and that is improving its quality.

\item A good starting point or a partial solution will also have a
positive effect on the convergence of the system; faster convergence
to the final solution.
\end{itemize}
\end{slide}

\begin{slide}
\begin{figure}[h]
\begin{center}
\begin{picture}(365,365)
\psfig{figure=min_itr.vs.cost.1.ps,height=365pt,width=365pt,angle=-90}
\end{picture}
\end{center}
\vspace{0.25cm}
{\large Using reheating based on cost: This figure shows the cost point when
local minima is encounterd. A local minima occurs if there is no
change at all in cost after a number of iterations.}
\end{figure}
\end{slide}

\begin{slide}
\begin{figure}[h]
\begin{center}
\begin{picture}(365,365)
\psfig{figure=timesteps.vs.profcost.ps,height=365pt,width=365pt,angle=-90}
\end{picture}
\end{center}
\vspace{0.25cm}
{\large Using reheating based on cost: this shows teachers
cost vs. the number of iterations or moves.}
\end{figure}
\end{slide}

\begin{slide}
\begin{figure}[h]
\begin{center}
\begin{picture}(365,365)
\psfig{figure=temp.vs.delta_cost.ps,height=365pt,width=365pt,angle=-90}
\end{picture}
\end{center}
\vspace{0.25cm}
\centerline{\large Using reheating based on cost: This plot shows the
change in cost ($\Delta$ cost) vs number of iterations.}
\end{figure}
\end{slide}

\begin{slide}
\begin{figure}[h]
\begin{center}
\begin{picture}(365,365)
\psfig{figure=roomsize_cost.ps,height=365pt,width=365pt,angle=-90}
\end{picture}
\end{center}
\vspace{0.25cm}
{\large Using reheating based on cost: this figure shows the roomsize
cost resulting from the given enrollments of classes and their
corresponding room sizes.}
\end{figure}
\end{slide}

\begin{slide}
\begin{figure}[h]
\begin{center}
\begin{picture}(365,365)
\psfig{figure=adapt_prof_cost.data.ps,height=365pt,width=365pt,angle=-90}
\end{picture}
\end{center}
\vspace{0.25cm}
{\large Using reheating based on cost: this figure shows the cost
incurred from assigning professor to classes and classes to professors
based on the aforementioned teachers constraints.}
\end{figure}
\end{slide}

\begin{slide}
\begin{figure}[h]
\begin{center}
\begin{picture}(365,365)
\psfig{figure=adapt_delta_cost.data.ps,height=365pt,width=365pt,angle=-90}
\end{picture}
\end{center}
\vspace{0.25cm}
{\large Using geometric annealing: This plot shows the change
in cost while carrying out the simulation. It is timesteps or iterations
vs change in the overall cost.}
\end{figure}
\end{slide}

\begin{slide}
\section{The Hopfield Net - A summary of the continuous model}
\Large
\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
variables: 
\begin{itemize}
\item its current state (input) $u_i$,  and
\item its output $v_i$.
\end{itemize}

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

\item The net's dynamics are governed by the first order differential
equation: 
${{\bf du} \over {\bf dt}} = 
- \eta {\bf u} + {\bf W v} + {\bf I^b}\;$.

\item $g_{\lambda}(u_i) = {1 \over {1 + e^{-2\lambda u_i}}}\;$, for
large $\lambda$, this function approximates a \underline{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 together (synchronously).
\end{itemize}
\end{slide}

\begin{slide}
\subsection{A Schematic View of the Net}
\large
\begin{figure}[h]
\begin{center}
\begin{picture}(320,320)
\psfig{figure=hopfield_net.ps,height=320pt,width=320pt}
\end{picture}
\end{center}
\end{figure}
\end{slide}

\begin{slide}
\subsection{The Operation of the Model}
\begin{itemize}
\item The network's dynamics are governed by a set of nonlinear
coupled differential equations of the form:

${{du_i} \over {dt}} = - u_i + \sum_{j=1}^{n} W_{ij} v_j + I_{i}^{b}\;$.

or the general form of it:

${{\bf du} \over {\bf dt}} = - \eta {\bf u} + {\bf W v} + {\bf I^b}\;$.

\item The $I_{i}^b$ corresponds to an input bias to neuron $i$.
\item The $\eta$ term introduces an element of decay into the
network's dynamics, which can be used to ensure that ${\bf u}$
variables remain bounded in magnitude.
\end{itemize}
\end{slide}


\begin{slide}
\subsection{Update of the Neurons States}

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.

$
{\bf \dot{u}} = 
-\eta{\bf u}+{\bf W v}+{\bf I^{b}}\;\;\;\;\;\;\;\;\ldots\ldots\ldots[1]
$

where 

$
v = g(u)\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\ldots\ldots\ldots[2]
$

Equations [1] and [2] govern the dynamics of the network.
\end{slide}

\begin{slide}
\subsection{Stability of the Net}

Given that {\bf W} is symmetric, Hopfield proved stability for the
network by showing that with the above dynamic equations ([1] and [2])
the network output {\bf v} evolves so as to minimize the {\it Liapunov
function}:

$
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\;\;\;\;\;\;\;\;\;\;\;\;\;\ldots\ldots\ldots[3]
$

\begin{itemize}
\item $v = (v_1 \ldots v_n)$ is denoting the net state, therefore we
have an energy function defined throughout $v \in [0,1]^n$ and
dynamics which guarantee convergence to minima.

\item 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 imapct at low $\eta$.
\end{itemize}
\end{slide}

\begin{slide}
\subsection{Updating the States of the Net}
\begin{enumerate}

\item Updating of the states (or the output of the neurons) is carried
out either asynchronously or synchronously. 
\item From a simulation point of view, we found that synchronous updating
a bit more efficient.
\item 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.
\end{enumerate}
\end{slide}

\begin{slide}
\subsection{Mapping the Problem onto the Network}

\begin{itemize}
\item A representation of the problem is needed in which the feasible
solutions lie at hypercube 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 [3]) for which the minima correspond to solutions and the
depth of each minimum reflects the solution quality.

\item Hopfield and Tank example is the TSP, which they have mapped
onto the net using a permutation matrix representation of the TSP
tours.
\end{itemize}
\end{slide}

\begin{slide}
\subsection{Shortcomings of the Hopfield Model}

\begin{itemize}
\item The net's partition function sums over a vast number of
configurations (e.g. for the TSP, all of the ${2^{N}}^2$ configurations
are admissible). 
\item These configurations, again, for the TSP, are nothing
like valid tours, and even though these offenders have small Boltzmann
weights their large number inevitably affects the thermal average
quantities.
\end{itemize}
\end{slide}

\begin{slide}
\subsection{Mean Field Annealing (MFA)}

\subsubsection{Brief Background}

To get around the difficulties arising from Hopfield-Tank (HT)
algorithm, one way forward is to reduce the computational burden being
placed on the network:
\begin{itemize}
\item Constrain each neuron representing , for example, a
class-professor to be ``on'' only once ({\it each class-professor to take
place only once during a certain time period.})  by enforcing:

$\;\;\;\;{\displaystyle \sum_a} V_{ia} = 1\;\; \forall i$, $V_{ia} = 1/0\;\;;$ 

saying that event $i$ to take place during interval $a$ or $i$ is the $a$-th
event to occur in the schedule, rather than relying
on an energy penalty term to try to do this (as is done in HT).
\end{itemize}
\end{slide}

\begin{slide}
\subsubsection{MFA variables: Ising to the Potts model}

{\bf\underline{The Ising Case}}

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

$\;\;\;\; E = - {J \over 2} {\displaystyle \sum_{i}}\, s_i s_{i+1}\;\;,$ 

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 

$\;\;\;\; s_i = sgn[J(s_{i-1} + s_{i+1})]\;\;,$

which leads to a state where all spins point in one of two possible
directions.
\end{slide}

\begin{slide}
{\bf\underline{The Potts Representation}}
\Large

Restricting the state space of the neurons such that exactly {\it one
neuron} at every site is allowed to be on, can be written as: 

${\displaystyle \sum_{a}} s_{ia} = 1\;\;\;\;\forall i\;\;$.

Thus for every $i$, $s_{ia}$ should be 1 for only one value of $a$,
and $0$ for the rest. 

Choose a $k$-dimensional vector representation of the neuron states:
The $a^{th}$ possible state of the neuron vector $\vec{s}_i$ associated
with the node $i$ is represented by the unit vector in the direction
of $a$, so we end up with $K$ different states, 
$(1,0,\ldots,0)$, $(0,1,\ldots,0)$, $\ldots$, $(0,0,\ldots,1)$ are all
normalized and mutually orthogonal. The number of states available at
every node is thereby reduced from $2^K$ to $K$. Technically, we now have
a $K$-state Potts model.

{\underline{Neuron Normalization}}

Is the explicit enforcement of  

$\;\;\;\;{\displaystyle \sum_{a \in A}} V_{ia} = 1\;\;$ where $A$ is a
set of states, in the MFA algorithm without any need for a penalty term.
\end{slide}

\begin{slide}
\subsubsection{Mapping Timetabling onto the Potts Neural Nets}

{\underline{[I]. The relationship between various entities of TTS}}

Our problem consist of the following sets: teachers ($P$), classes
($C$), students ($S$), rooms ($R$), and time periods (${\cal I}$).
\begin{center}
\begin{picture}(250,250)
\psfig{figure=scheduling-net.eps,height=250pt,width=250pt}
\end{picture}
\end{center}
\end{slide}

\begin{slide}
{\underline{[II]. Neural Mapping}}

Involve mapping the problem onto the Potts model.

\begin{itemize}
\item These multi-state neurons, forming the network, represent different
activaties of the timetabling problem . 

\item Construct the constraints of the problem using these neurons.

\item Derive those MF equations controlling the dynamics of the net:

\begin{itemize}
\item Introduce the MF variables , for example, $V_{pq;xt} =
<S_{pq;xt}>_T\;\;$.

\item Start off with the partition function:
$\;\;\;\; Z = {\displaystyle \sum_{[\vec{s}]}} e^{-E[\vec{s}] / T} \;\;$.

\item Re-write $Z$ in terms of a multidimentional integral
over continuous vectors ($\vec{u}_i, \vec{v}_i$).

\item The MFT approximation to $<\vec{s}_i>$ is given by the value
$\vec{u}_i$ at a saddle-point equations:\\

$\;\;\;\; {{\partial E} \over {\partial v_{ia}}} = 0$  and  
$\;\;\;\; {{\partial E} \over {\partial u_{ia}}} = 0\;$, 
generating a set of self-consistency equations in the MF variables:

$\;\;\;\; u_{ia} = 
        - {1 \over T} {{\partial E[\vec{v}]} \over {\partial v_{ia}}} \;\;$,

$\;\;\;\; v_{ia} = {e^{u_{ia}} \over {{\displaystyle \sum_b} e^{u_{ib}}}} \;\;$.
Where $a$ denotes the vector components.

For events (pq, xt), we get the following MF variables:

$\;\;\; u_{pq,xt} = - {1 \over T} 
        {{\partial E} \over {\partial v_{pq,xt}}} \;\;$,
$\;\;\; v_{pq,xt} = 
        {e^{u_{pq,xt}} \over {{\displaystyle \sum_{x' t'}} e^{u_{pq,x't'}}}} \;\;$.
\end{itemize}

From the later follows, that ${\displaystyle \sum_{a}} v_{ia} = 1\;\;$.
One can think of the mean field $v_{ia}$ as the probability for the
Potts neuron $i$ to be in state $a$.

\item Iterate $v_{pq, xt}$ equation with annealing, i.e. starting at a
high temperature, and successively lowering it in the course of the
process.  A phase transition is passed at $T = T_c$.

\item Estimate the critical temperature $T_c$, which sets the scale of
$T$, by expanding the above $v_{pq,xt}$ equation around the trivial
fix-point : 
$\;\;\;\;$ at $T = 0\;$,$\;\;v^{(0)}_{pq,xt} = {1 \over N_x N_t}\;\;$.

\end{itemize}
\end{slide}


\begin{slide}
\subsection{Definitions}

The event-based mapping is carried out as follows (a sample):
\begin{itemize}
\item professor(p)-class(c) $\longrightarrow$ room(r)-timeslot(i),
represented by the following neuron:

\[
S_{pc;ri} = \left\{\begin{array}{ll}
                         1 & \mbox{if event $(p,c)$ occur in $(r,i)$} \\
                         0 & \mbox{otherwise}
                         \end{array}
                  \right.
\]

\item class(c)-room(r) $\longrightarrow$ room(r)-timeslot(i),

\[
S_{cr;ri} = \left\{\begin{array}{ll}
                         1 & \mbox{if event $(c,r)$ occur in $(r,i)$} \\
                         0 & \mbox{otherwise}
                         \end{array}
                  \right.
\]
\end{itemize}
\end{slide}

\begin{slide}
\subsection{Representation of Some Constraints}

We define a number of {\bf hard constraints}:
\begin{itemize}
\item An event $(p,c)$ should occupy precisely one space-time slot $(x,i)$.
This constraint can be embedded in the neural net in terms of the Potts
normalization condition:

${\displaystyle \sum_{x,i}} S_{pc,xi} = 1\;\;\;\;\;\;\;\;\;\;\;\;\;\;[P.1]$

\item Different events $(p_1,c_1)$ and $(p_2,c_2)$ should not occupy the same
space-time slot $(r,i)$.

$E_{X{\cal I}} =$
${1 \over 2}{\displaystyle \sum_{x,i}\sum_{p_1,c_1}\sum_{p_2,c_2}}S_{p_1c_1;xi}S_{p_2c_2;xi} =$
${1 \over 2}{\displaystyle \sum_{x,i}}{({\displaystyle \sum_{pc}}S_{pc;xi})}^2\;\;\;\;\;\;\;\;\;\;\;\;\;\;[P.2]$
\item A teacher $p$ should have at most one class at a time.

$E_{P{\cal I}} =$
${1 \over 2}{\displaystyle \sum_{p,i}\sum_{q_1,x_1}\sum_{q_2,x_2}}S_{pq_1;x_1i}S_{pq_2;x_2i} =$
${1 \over 2}{\displaystyle \sum_{p,t}}{({\displaystyle \sum_{qx}}S_{pq;xi})}^2\;\;\;\;\;\;\;\;\;\;\;\;\;\;[P.3]$
\item A class $q$ should have at most one teacher at a time.

$E_{Q{\cal I}} =$
${1 \over 2}{\displaystyle \sum_{q,i}\sum_{p_1,x_1}\sum_{p_2,x_2}}S_{p_1q;x_1i}S_{p_2q;x_2i} =$
${1 \over 2}{\displaystyle \sum_{q,i}}{({\displaystyle \sum_{px}}S_{pq;xi})}^2\;\;\;\;\;\;\;\;\;\;\;\;\;\;[P.4]$
\end{itemize}
\end{slide}

\begin{slide}
{\bf\underline{Relative Clamping}}

When revising an existing schedule, sometimes it is desirable to have
a certain cluster of events to stick together \underline{in time} (or
\underline{within some specified period of time}). This amounts to
making the following notational replacement:

$\;\;\;\;\;i \longrightarrow (j,k) \;\;$ ;

where $(j)$ denotes the cluster and $(k)$ an event within $(j)$. In this
situation, one has a common $t$-neuron $(S^{(T)}_{j;t})$ for cluster
$j$ but distinct $x$-neurons $(S^{(X)}_{jk;x})$ for the individual events.
\end{slide}

\begin{slide}
{\bf\underline{Extended Events in Time}}
To deal with this concept, we use the so called \underline{effective
$time$-neurons} $\tilde{S}^{(T)}_{i;t}$, defined as:

$\tilde{S}^{(T)}_{i;t} = \sum_{k=0}^{g_i - 1} S^{(T)}_{i;t-k}\;\;\;\;\;\;\;\;\;\;\;\;\;\;[P.5]$

where $g_i = 1$ for single hours and $= 2$ for double hours. 

Using the above concepts of \underline{relative clamping} and
\underline{extended events in time}, constraints P.2, P.3, and P.4
becomes:

$E_{XT} =
 {1 \over 2}\sum_{x,t}\sum_{i \neq i^{'}}
 S^{(X)}_{i;x}S^{(X)}_{i^{'};x} \tilde{S}^{(T)}_{i;t}
 \tilde{S}^{(T)}_{i^{'};t}\;\;\;\;\;\;\;\;\;\;\;\;\;\;[P.6]$


$E_{PT} =
 {1 \over 2}\sum_{p,t} \sum_{i \neq i^{'}} \delta_{p(i),p(i^{'})}
 \tilde{S}^{(T)}_{i;t} \tilde{S}^{(T)}_{i^{'};t}\;\;\;\;\;\;\;\;\;\;\;\;\;\;[P.7]$


$E_{QT} =
 {1 \over 2}\sum_{q,t} \sum_{i \neq i^{'}} \delta_{q(i),q(i^{'})}
 \tilde{S}^{(T)}_{i;t} \tilde{S}^{(T)}_{i^{'};t}\;\;\;\;\;\;\;\;\;\;\;\;\;\;[P.8]$

\end{slide}

\begin{slide}
{\bf\underline{Spreading of Classes over the Week}}
Classes are spread in a (MWF) and (TuTh) fashion.

\begin{itemize}
\item Let the subject attribute be $s(j,k)$. We define an
effective ``day-neuron'' as follows ($\tilde{S}^{(T)}_{j;dh}$ is
reduced to a $D$-type neuron by summing over all hours of the day):

$S^{(D)}_{i;d} = \sum_h \tilde{S}^{(T)}_{j;dh} = 
g_j \cdot S^{(T)}_{j;dh}\;\;\;\;\;\;\;\;\;\;\;\;\;\;[P.9]$ 

\item The penalty term $E_{QSD}$ that spreads classes $Q$ in a
particular subject $S$ over different week-days $D$ :

$E_{QSD} = 
{1 \over 2} \sum_{qsd}{\left[\sum_{jk}\sum_{h} \delta_{q,q(j,k)} \delta_{s,s(j,k)}
\tilde{S}^{(T)}_{jk;dh}\right]}^2\;\;\;\;\;\;\;\;\;\;\;\;\;\;[P.10]$ 

\item Refining the above form by considering 2 different
clusters $(j)$ and $(\hat{j})$ of classes over $D$ : ($q$ and $s$ are
not used in the summation, since no change occurs to them)

$
E_{QSD} =
{1 \over 2} \sum_{d}\sum_{j \neq \hat{j}}\sum_{kh}\sum_{\hat{k}\hat{h}}
\delta_{q(j,k),q(\hat{j},\hat{k})}\delta_{s(j,k), s(\hat{j},\hat{k})}
\hat{S}^{(T)}_{j;dh}\hat{S}^{(T)}_{j;d\hat{h}}\;\;\;\;\;\;\;\;\;\;\;\;\;\;[P.11]$ 

\item Now for some day $(d)$ of the week:
$
E_{QSD} =
{1 \over 2} \sum_{j \neq \hat{j}} \sum_{k\hat{k}} 
\delta_{q(j,k),q(\hat{j},\hat{k})}\delta_{s(j,k), s(\hat{j},\hat{k})}
\sum_d S^{(D)}_{j,d} S^{(D)}_{\hat{j},d}\;\;\;\;\;\;\;\;\;\;\;\;\;\;[P.12]$ 
\end{itemize}
\end{slide}

\begin{slide}
{\bf\underline{Glueing (or filling in the ``holes'')}}

\begin{itemize}
\item The penalty term that rewards situations where (d,h)-events are
glued to (d,h-1)-events can be defined as follows:

$
E_{QDH} = -\alpha \sum_{q}\sum_{d,h} \left[\sum_{j,k}\delta_{q,q(j,k)}\tilde{S}^{(T)}_{j;dh}\right]
\left[\sum_{\hat{j} \neq j}\Gamma_{q,q(\hat{j},\hat{k})} \tilde{S}^{(T)}_{j;d(h-1)}\right]\;\;\;\;\;\;\;\;\;\;\;\;\;\;[P.13]$ 
\\

The energy term can be summarized to say that: {\it if cluster ($j$)
with events each symbolized by ($k$) occurs on hour ($h$) of day ($d$)
then it would be quite desirable to have another event ($\hat{k}$)
from a different cluster ($\hat{j}$) to occur on hour ($h-1$) of that day.}

\item Next, since ($q$) is fixed we could re-write the above equation
as follows:

$
E_{QDH} = -\alpha\sum_{\hat{j} \neq j}\sum_{k,\hat{k}}\Gamma_{q(j,k),
q(\hat{j},\hat{k})} \sum_{d,h>1}\tilde{S}^{(T)}_{j;dh}\tilde{S}^{(T)}_{\hat{j},d(h-1)}\;\;\;\;\;\;\;\;\;\;\;\;\;\;[P.14]$

\end{itemize}
\end{slide}


\begin{slide}
\subsection{Mean Field Dynamics}
\large
Let $v^{X}_{jk;x}$ and $v^{T}_{j;t}$ corresponding to $s^{x}_{jk;x}$
and $s^{T}_{j;t}$, respectively. Now, substituting $v$ for $s$ in the
energy expressions, the MF equations at finite $T$, are given
in terms of the local fields:
\begin{enumerate}
\item $u^{X}_{jk;x} =
        - {1 \over T} {{\partial E} \over {\partial v^{X}_{jk;x}}} \;\;$,
\item $u^{T}_{j;t} =
        - {1 \over T} {{\partial E} \over {\partial v^{T}_{j;t}}} \;\;$,

As the following:

\item $v^{X}_{jk;x} = 
        {e^{u^{X}_{jk;x}} \over {{\displaystyle \sum_{x'}} e^{u^{X}_{jk;x'}}}} \;\;$.
\item $v^{T}_{j;t} = 
        {e^{u^{T}_{j;t}} \over {{\displaystyle \sum_{t'}} e^{u^{T}_{j;t'}}}} \;\;$.
\end{enumerate}

The MF dynamics consists of iterating the above equations either {\it
synchronously} or {\it serially}. 

{\bf\underline{Synchronuous Updating}}: A sweep consists of first
computing all {\it local fields}, and then updating all the neurons; (1)-(2)
followed by (3)-(4).

{\bf\underline{Serial Updating}}:  For each neuron $s^{X}_{jk;x}$
and/or $s^{T}_{j;t}$, the {\it local field} is computed immediately before
the corresponding {\it neuron state} is updated. That means either do
(1) then (3) and/or (2) then (4). In our simulation we use this method
of updating.
\end{slide}

\begin{slide}
\subsection{Some Experimental Results}

{\bf\underline{Constraints Dealing with Classes [Type I]}}

\begin{itemize}
\item Those dealing with class capacity/enrollment.
\item A professor can not teach more than a class at a time.
\item A class should have at most one teacher assigned to it.
\item A class and its recitation and/or lab can not be assigned at the
same time.
\item A limit on the teaching hours per week for a teacher.
\item Spreading out classes over the week.
\item Filling in the large wholes in the schedule.
\item Observing the various distances between buildings.
\end{itemize}
\end{slide}

\begin{slide}
{\bf\underline{Constraints Dealing with Students [Type II]}}
\begin{itemize}
\item To sign up for a class or a section, it must be open.
\item Eligibility criteria for the section must be met.
\item Balance {\it MWF} and {\it TuTh} sections.
\item Observe maximum limit of classes per student.
\item Athlets are not enrolled in courses that conflict with their
sport pratice time, etc.
\end{itemize}
\end{slide}

\begin{slide}
{\bf\underline{Tabulated Results from the Rule-Based System}}

{\bf\underline{Using class constraints}}
\vspace{0.25cm}
$$
\begin{tabular}{|l||c|c|c|c||}
\hline
            & Total Courses & Scheduled & Not Scheduled & \% Scheduled\\ \hline\hline
First Term  &     4400      &   3168    &      1232     &     72.00   \\ \hline
Second Term &     4082      &   3189    &      893      &     78.12   \\ \hline
Third Term  &     709       &   631     &      78       &     89.00   \\ \hline
\end{tabular}
$$
\label{table.1}
\end{slide}

\begin{slide}
{\bf\underline{Tabulated Results from the Rule-Based System}}

{\bf\underline{Using class and student constraints}}
\vspace{0.25cm}
$$
\begin{tabular}{|l||c|c|c|c||}
\hline
            & Total Courses & Scheduled & Not Scheduled & \% Scheduled\\ \hline\hline
First Term  &     4400      &   2992    &      1408     &     68.00   \\ \hline
Second Term &     4082      &   2881    &      1201     &     70.57   \\ \hline
Third Term  &     709       &   569     &      140      &     80.25   \\ \hline
\end{tabular}
$$
\label{table.1}
\end{slide}

\begin{slide}
{\bf\underline{Using class and student constraints - First Term Data}}

{\bf\underline{No Pre-processor Used}}
\vspace{0.25cm}
$$
\begin{tabular}{|l||c|c|c||}
\hline
                & Scheduled & Not Scheduled & \% Scheduled\\ \hline\hline
SA (geometric)  &   2627    &      1773     &     59.70   \\ \hline
SA (cost-based) &   2914    &      1486     &     66.22   \\ \hline
Mean Field      &   2151    &      2249     &     48.88   \\ \hline
\end{tabular}
$$
\label{table.1}

{\bf \underline{NOTE}: [1] Annealing is carried out on space AND
time. [2] All shown data is averaged over 10 runs.}
\end{slide}

\begin{slide}
{\bf\underline{Using class and student constraints - First Term Data}}

{\bf\underline{Rule-based system is used a pre-processor}}
\vspace{0.25cm}
$$
\begin{tabular}{|l||c|c|c||}
\hline
                & Scheduled & Not Scheduled & \% Scheduled\\ \hline\hline
SA (geometric)  &   4280    &      120      &     97.27   \\ \hline
SA (cost-based) &   4333    &      67       &     98.47   \\ \hline
Mean Field      &   3985    &      415      &     90.56   \\ \hline
\end{tabular}
$$
\label{table.1}

{\bf \underline{NOTE}: [1] Annealing is carried out on space AND
time. [2] All shown data is averaged over 10 runs.}
\end{slide}

\begin{slide}
\begin{thebibliography}{HT}
\large
\bibitem[GJ-79]{GJ-79}
Gary and Johnson,
{\it Computers and Intractability: A guide to the theory of
NP-completeness}. Freeman, San Francisco (1979).

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

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

\bibitem[HT-85]{Hop-85}
J. J. Hopfield and D. W. Tank, 
``Neural Computation of Decisions in Optimization Problems'',
Biological Cybernetics 52, 141 (1985).

\bibitem[GT-86]{GT-86}
Gosselin, K. and Truchon, M. ``Allocation of Classrooms by Linear
Programming'', J. Operational Research Society 37, No. 6, 1986,
561-569. 

\bibitem[CHdW-87]{CHdW-87}
M. Chams, A. Hertz and D. de Werra, ``Some Experiments with Simulated
Annealing for Coloring Graphs'', European Jr. of Operations Research
32 (1987), 260-266.

\bibitem[TD-94]{TD-94}
J. Thompson, and K. Dowsland, ``Variants of Simulated Annealing for
the Examination Timetabling Problem'', Working Paper, Statistics and
OR Group, European Business Management School, Swansea SA2 8PP, UK. (1994)

\bibitem[Abramson-94]{Abramson-94}
Abramson, Dang, and Krishnamoorthy,
``An Empirical Study of Simulated Annealing Cooling Schedules'',
Griffith Univ. report, Nathan, Qld, Aus. (1994).

\bibitem[Lister-93]{Lister93}
R. Lister,''Annealing Networks and Fractal Landscapes'', Proc. IEEE
Int. Conf. on Neural Nets, March 1993, Vol. I, pp 257-262.
\end{thebibliography}
\end{slide}
