%% LATEX TWICE TO GET THE REFERENCES RIGHT
%%\documentstyle[12pt]{article}
\documentstyle[12pt,epsf,psfig]{article}

\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{alpha}
\newpage
\begin{flushright}
{\sl CPS615.report}
\end{flushright}
\vspace{.5cm}
\begin{center} 
\hrule
\vspace{.05cm}
\hrule
\hrule
\hrule
\hrule
\hrule
\hrule
\hrule
\hrule
\hrule
\hrule
\vspace{.25cm}
{\bf 
Simulated Annealing, and non-Euclidean Combinatorial Optimization
Problems: The case of Academic Course Scheduling, Theory and
Implementation.\footnote{This is part of an onging joint work with
Geoffrey, Paul Coddington, and Hon Yau.}
}
\vspace{.25cm}
\hrule
\vspace{.05cm}
\hrule
\hrule
\hrule
\hrule
\hrule
\vspace{1cm}

Saleh Elmohamed\\
Northeast Parallel Architectures Center,\\
Syracuse University\\
Syracuse, NY 13244\\
saleh@npac.syr.edu\\
\end{center}

\vspace{1.5cm}
\centerline{Abstract}

In this study we tackle a complex problem of academic course 
scheduling (or timetabling) at the university level. The method
used is that of simulated annealing using two different annealing
schedules. A rule-based system is used as a pre-processor in both
approaches.

\vfill
\noindent{\bf Key words : stochastic updating, annealing, simulated
annealing, cost functions, temperature, annealing schedule, phase
transition, rule-based system.}

\vfill
\centerline{\today}
\vfill

\newpage
\pagestyle{empty}
\tableofcontents

\newpage

\pagestyle{plain}
\pagestyle{myheadings}
\markright{\sl SA/TTS.report}
\section{Introduction}
\setcounter{page}{1}

The prime objective of this study is to derive an approximate solution
to a high-dimensional and non-geometric combinatorial optimization (CO)
problem, which is academic scheduling at the university level. 
 
Our method for tackling the aforementioned problem is simulated
annealing using two different cooling schedules: the standard
geometric cooling, and the geometric re-heating as a function of cost.

\section{Background and Motivation}

The problem of academic scheduling or timetabling has been tackled 
by many researchers \cite{47}, mostly in the field of operations
research. This is a very difficult problem due to its nature as a
multi-constraint (or a constraint-satisfaction) non-Euclidean
combinatorial optimization problem for which no ``good'' solution has
previously been found.

Lately, there have been a number of {\it non-conventional} (or novel)
methods utilized to tackle this problem from different angles. Chief 
among them are neural networks \cite{32}, simulated annealing
\cite{39} and \cite{2}, genetic algorithms \cite{37}, tabu search
\cite{38}, and various combinations of two or more of these
techniques. In this paper, we shall confine ourselves to simulated 
annealing using the cooling schedules of geometric annealing and
re-heating as a function of cost. In addition, a rule-based system is
used as a pre-processor in the application of each of these schedules.

\section{The Timetabling Problem - description and solution methods}
One of the problems that does not have a well-defined objective
function (as in the Traveling Salesperson Problem) to optimize and
belongs to the class of constraint satisfaction problems is the
$NP$-complete {\it teachers and classes} timetabling problem studied
in \cite{2, 3, 27}. Briefly, the problem is defined as follows: 

\bd{general-TTS}\ \
For a certain school with $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 legal schedule needs to be found such that no teacher, class,
or 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.
\ed

%% \br{remark.1}
%% From this point on, we will refer to academic scheduling or
%% timetabling as $TTS$ (short for a timetabling system).
%% \er

\br{remark.2}
Some authors notably Hertz \cite{38} and Eiselt and Laporte \cite{49}
refer only to hard constraints as ``constraints'' while the medium and
soft are considered as objectives. We don't make such a distinction
in this paper.
\er

\subsection{The Constraint Satisfaction Problem}

We now briefly describe the general  constraint satisfaction problem
(CSP) which has been widely studied in the Artificial Intelligence
community \cite{9, 10, 11}.

\bd{CSP}\ \
{\it An instance} of a constraint satisfaction problem {\it consists
of}:

\begin{itemize}
\item {\it A finite set of variables, $N_i$, where $i = 1, 2,\ldots,n\;$}.
\item {\it A domain of D of possible values of $N_i$}$\;$.
\item {\it A set of constraints} $\{C(S_1), C(S_2),\ldots, C(S_c)\}\;$.

{\it Each $S_i$ is an ordered subset of the variables, and each
constraint $C(S_i)$ is a set of tuples indicating the mutually
consistent values for the variables in $S_i$}$\;$.

\end{itemize}
\ed

The length of the tuples in a given constraint will be called the
{\it arity} of that constraint\footnote{Strictly speaking we also need
to associate an arity with an empty set of tuples, but we will neglect
this special case, in order to simplify the presentation.}. In
particular, unary constraints specify the allowed values for a single
variable, and binary constraints specify the allowed combinations of
values for a pair of variables.

A {\it solution} to a constraint satisfaction problem is an assignment
of values to the variables which is consistent with all of the
constraints. Deciding whether or not a given problem instance has a 
solution is NP-complete in general \cite{11}, even when the
constraints are restricted to binary constraints.

\subsection{Constraints of the Timetabling System}

In a nutshell, timetabling is the assignment of time slots to a set of
events, {\bf subject to} constraints on these assignments. Generally,
a constraint places a restriction on when and where classes may be
scheduled. Also as alluded to in \cite{49}, a constraint can be hard,
medium or soft. The medium and soft constraints have an associated
cost and if they are not satisfied, the goal is to minimize this
cost. In regard to the hard constraints, one must derive their
associated cost (or penalty) to zero.

In short, the three types of constraints used are:
\begin{enumerate}
\item Hard - These constraints that must be satisfied.
\item Medium - These constraints should be satisfied, if possible, but
are not required for a valid solution. 
\item Soft - These constraints have a lower priority but always the
preference is to minimize them.
\end{enumerate}

\subsubsection{Hard Constraints}

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. See section 5 for more details.

Those events that must not overlap in time include:

\begin{itemize}
\item two classes taught by the same professor,
\item a class and a recitation or a lab of the same class,
\item classes with students in common.
\end{itemize}

Other general hard constraints include:

\begin{itemize}
\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.
\item A limit on how many classes taught by each instructor is enforced.
\end{itemize}

Also, there are other constraints of relevance 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.
\item Do not enroll athletes in courses that conflict with their sport
practice time, etc.
\end{itemize}
These constraints have to be respected at all costs.

\subsubsection{Medium Constraints}

These kinds of constraints fall into, so to speak, the shaded region
between the {\it hard} and {\it soft} constraints in the sense that
they do not directly deal with time conflicts as do the hard type but
have a high penalty attached to them. Also, this penalty is not as
high as that associated with the hard constraints. In the final
(legal) schedule the penalty of these constraints is minimized and it
is quite preferable to reduce it to $0$.

In short, these kind of constraints should be satisfied but are
nevertheless relaxable. Some 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}

\subsubsection{Soft Constraints}

Like medium constraints, they also do not deal with time conflicts at
all but unlike the medium constraints, have a low penalty (or cost)
associated with them. Furthermore, this cost is lower than that of the
medium constraints and much lower than that of the hard ones. In
addition, in the final schedule, this cost is minimized but does not
often approach zero. Here are few 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.
\end{itemize}

\subsection{The overall cost function}

The {\it cost function} measures the infeasibility of the current
solution and may involve the weighted sum of penalties associated with
different types of feasibility violation. Our reference to
``feasibility'' here means that a timetabling schedule is feasible if
it satisfies all of the hard constraints. (See definition in section 5.3)

We consider the following as part of the function:
\begin{itemize}

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

\item {\it Time period cost} consisting of :
\begin{enumerate}
\item class cost, 
\item professor cost, 
\item cost of class spreading over the week and within each of the
weekdays,
\item cost of class glueing and filling in any holes of the timetable,
\item room size cost, and 
\item 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{enumerate}

\item {\it Professor cost} is computed from:
\begin{enumerate}
\item cost incurred from  assigning more classes than the maximum
number taught by that professor, plus
\item cost from not having a long enough time interval between courses
taught by the same professor, and
\item cost of assigning to the same professor two or more classes that
overlap in time. 
\end{enumerate}

\item {\it 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}

\br{remark.3}
Using summation is not strictly necessary, provided that
the components can be combined in some fashion to reflect the quality
of the solution.
\er


\subsection{Complexity of Timetabling}

\bd{resources}
Resources are physical entities that are referred to by TTS, for
example: students, rooms, overhead projectors, etc. Also time periods
can be thought of as resources.
\ed

Timetabling belongs to the class of constraint satisfaction problems
and it is essentially an example of a resource-constrained scheduling
problem, which is an NP-complete problem \cite{12} and \cite{25}.

The problem has been approached by means of linear programming (LP)
with binary variables plus some heuristics. For example, if $i$
identifies a teacher, $j$ identifies a time-interval and $k$
identifies a class then the binary variable $X_{ijk}$ $=$ $1$ if
teacher $i$ has class $k$ at time-interval $j$; $X_{ijk}$ $=$ $0$ ,
otherwise.

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

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

\bd{complexity-df2}
For a much simpler problem, which is the {\it class allocation} (no
timetabling part included), using linear programming \cite{5} \cite{28}, the
computational load ($n_c$) scales as follows:

\be{complexity}
n_c \propto N_c N_x N_t\;\;,
\ee

where $N_c$ is the number of room categories (i.e. classroom,
auditorium, etc.).
\ed

\section{Some Methods of Tackling Timetabling}

\subsection{Some Relevant Definitions}

\bd{polytope-polyhedron}\ \

Let $\R^n$ be the set of all n-tuples $(x_1,\ldots,x_n)$ with real
entries $x_i$, and $\R$ is the associated set of scalars. Likewise for
$\R^m$, where $m\neq n$.
\begin{itemize}

\item A subset $P$ of $\R^n$ is a polyhedron if and only if there
exists an ${\it m}$ by ${\it n}$ matrix A and a vector $b \in \R^m$ such
that:  $P = \{ x\in\R^n \mid A x \leq b\}\;\;$. Here, $A x \leq b$
means: $a_1x \leq b_1,\ldots, a_mx \leq b_m$, where $a_1,\ldots, a_m$
are the rows of A. The matrix A may have zero rows, i.e. $m = 0$. In
this case $P = \R^n\;\;$.

\item A subset $P$ of $\R^n$ is called a polytope if $P$ is the convex
hull of a finite number of vectors. That is, there exist vectors
$x_1\ldots\x_t \in \R^n$ such that: $P = conv.hull\{x_1 \ldots x_t\}$.
Also, a subset $P$ of $\R^n$ is a polytope iff it is a bounded
polyhedron. For more information, see references \cite{14} and
\cite{15}.

\item A polytope $P$ is called integral if each of its vertices is an
integer vector. Clearly, if a polytope $P = \{x | Ax \leq b\}$ is
integral, then the LP-problem $max\{c^Tx| Ax \leq b\}$ has an integer
optimum solution. So in that case,

\be{max-max}
max\{c^{T}x | Ax \leq b ,\;x\;\text{integer} \} = 
max\{c^{T}x | Ax \leq b \}\;.
\ee
\end{itemize}
\ed


\begin{figure}[htb]
\centerline{\psfig{figure=polytopes-2.ps,width=6in,angle=-90}}
\caption{An integral polytope has all its vertices at integral points
(points whose coordinates are all integers). It follows that an
integral polytope within the unit hypercube has all its vertices at
$[0-1]$ points.}
\label{poly}
\end{figure}

The timetabling problem has no cost function, only constraints (hard,
medium and soft) each with their associated penalty (or cost); all we
have to do is find any integral vertex within the constraint polytope
$P$ (see Figure \ref{poly}). To elaborate a bit on this, using the 
work of  Schrijver \cite{14, 15}: we think of each constraint as a
hyperplane in the solution space. The set of constraints define a
polytope or (a bounded polyhedron) within which the state vector must
remain if it is not to violate any constraints. The $0$ or $1$
solution points will lie at some of the vertices of this polytope, and
whatever annealing method is used, it must force convergence to one of
these points. The problem with annealing (of course, depending on the
schedule used) is that the best one can expect is convergence to a
vertex, not necessarily a 0 or 1 vertex. 

Polytopes like the one for the permutation matrix mapping for the TSP
are integral, so there is no problem finding valid TSP solutions
(though the tour length is another question altogether). Class
scheduling polytopes are a totally different story: Gee \cite{45} and
some of his colleagues at Cambridge University have done some
experiments on them and found that for timetabling problems as small
as five teachers, five classrooms, five classes, and five time-slots,
the proportion of 0-1 vertices is only about $1\%$. This mean that on
average one has to run a descent procedure about 100 times to find a
valid solution! Some of our experiments with sets of teachers,
classes, classrooms, students and time-slots of various sizes confirm
some of Gee's results and conclusions. 

Timetabling problems can be characterized by their {\it sparseness}.
After all the required lessons have been scheduled, there will be $N_s
= (N_x N_t - N_l)$ spare space-time slots, hence, the sparseness of
the problem is defined as the ratio $N_s / (N_x N_t)$. The sparseness
decreases as  $N_s / (N_x N_t)$ goes to zero or as $N_s$ becomes
smaller and smaller. Furthermore, \cite{45} notes that for sparse
problems, the probability of an arbitrary descent procedure converging
to an integral vertex is near one, though this falls off rapidly for
less sparse problems. For dense problems, there is an additional
correlation involving the problem size: as the problem gets larger
(more classes, teachers, rooms, students, etc.), the proportion of
integral vertices gets smaller. From this we could deduce that a
one-shot descent procedure, operating on an arbitrary ``objective
function'', is not likely to be very successful with difficult
constraint satisfaction problems, most probably converging to a
non-integral vertex of $P$, for example. On the other hand, any
``partial'' or ``imperfect'' solution to a timetabling problem found
by methods such as simulated annealing (using some good adaptive
schedules) is likely to be of some use. Since simulated annealing does
not search over the interior of the unit hypercube, but only over its
vertices, the solution it finds will be a unique timetable, possibly
-as it is the case in our experiments- violating as few as one or two 
constraints. As part of the post-processing operation, we could at 
least remove some lessons to obtain a valid (or legal) timetable which
fulfills most of the teaching requirements. Furthermore, we could do
few more swaps (or moves) of classes around to arrive at a timetable
meeting all the original requirements.

\section{Mapping Timetabling to a Graph Coloring Problem}

\subsection{Graph Coloring}

\bd{graph-coloring}
Let $G=(V,E)$ be some graph with $V$ nodes and $E$ edges.
A {\it coloring} of $G$ is an assignment of colors to the nodes of $G$
such that no two  adjacent  nodes share the same color. More formally,
a {\it k-coloring} of $G$ is a mapping $f: V \longrightarrow \{1,
2,\ldots, k\}$ such that $f(u) = f(v)$ only if $(u,v) \not\in E$. The
{\it chromatic number} of $G$, denoted $\chi(G)$, is the minimal
number of colors necessary to color $G$. An {\it optimal coloring} of
$G$ is one which uses exactly $\chi(G)$ colors.
\ed

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

\subsection{Interpretation of the Solution Space}

After setting up or mapping the problem we need to determine the
following: 
\begin{itemize}
\item {\em 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}


\section{Our approach in Tackling the Problem}

\subsection{The Problem}

Given data sets of courses and their days, hours, enrollments, and
instructors; rooms and their capacities, specification, and locations;
distances between buildings; priorities of each building; students and
their courses: the problem is to construct legal school timetable(s)
satisfying all the hard constraints and minimizing the medium and soft
constraints.

Courses that are not assigned to rooms due to conflict in time or size
are left out of the final timetable for the user to handle manually. 

\subsection{The Preprocessing Phase}

The technique used is a rule-based system with lots of heuristics and
conventional recursion to assist in carrying out course
assignments. A feasible, albeit partial solution is found satisfying
all of the hard constraints and if possible all or at least some of
the medium ones.

\subsection{The Processing Phase}
In this phase soft and medium constraints along with the hard ones are
used to improve the current solution by satisfying more constraints
without any violation of the hard ones, or at least no violation of
the ones that are already satisfied in the previous phase.

\section{The Preprocessing System}

Here are few examples of some of the implemented rules
dealing with {\bf space and hours}, {\bf type of room}, and {\bf
priority of room}:

\subsection{Space and Hours}

{\it IF [room(capacity) $>$ course(space-requested)] and [no time
conflict in this room]
THEN
   assign the room to the course:}

[If more than a room having an identical availability time are present
in the database, then choose the one with the minimal magnitude of the
difference between room(capacity) and course(space-requested)].

{\bf\underline{Input:}}
CPS-615 requests space for 75 students and meeting hours of 
[MWF 10:40 - 11:35 am].

In the database we have, for example, the following rooms:

\begin{itemize}
\item room: 1-218 CST, capacity: 45 students, and pre-occupied hours:
none.
\item room: 207 HL, capacity 120 students, and pre-occupied hours: [MW
09:45 - 11:10 am]. 
\item room: Kitt-Aud HBC, capacity: 127 students, and pre-occupied
hours: [TTH 10:40 - 12:00 am].
\end{itemize}

{\bf\underline{Output:}}
Room Kitt-Aud is assigned to CPS-615. \ \

\subsection{Type of Room}

{\it IF [room(capacity) $>$ course(space-requested)] and [no time
conflict in assigning this room] and 
[type(room) matches type(requested)] 

THEN
   assign the room to the course:}
[If identical rooms in type are present in the database, then choose
the one with the minimal magnitude of the difference between
room(capacity) and course(space-requested)].

{\bf\underline{Input:}}
BIO-615 requests space (not biology lab) for 35 students and meeting
hours in [MW 10:40 - 11:35]. 

In the database we have, for example, the following rooms:

\begin{itemize}
\item room: 1-218 CST, capacity: 45 students, type: classroom, and
pre-occupied hours: none.
\item room: 124-SIMS, capacity: 40 students, type: laboratory, and
pre-occupied hours: none.
\end{itemize}

{\bf\underline{Output:}}
Room 124-SIMS is assigned to BIO-615. \ \

\subsection{Room Priority}

Rooms are classified as:
\begin{enumerate}
\item General Purpose: used by all users.
\item Priority Rooms: are used based on certain priority of the class
or the department.
\item Special Purpose: are only assigned to specific users.
\end{enumerate}

\begin{itemize}

\item {\it IF [room(priority) == general] and [room(capacity) $>$
course(space-requested)] and [no time conflict in assigning this room]
and [type(room) matches type(requested)]  

THEN  assign any user to this room.}

\item {\it IF [room has a priority user] and [the user is already
assigned] and [room(capacity) $>$ course(space-requested)] and [no
time conflict in assigning this room] and [type(room) matches
type(requested)]

THEN  assign other users.}

\item {\it IF [room(priority) == special purpose] and [user belongs to
the special users of this room] and [room(capacity) $>$
course(space-requested)] and [no time conflict in assigning this room]
and [type(room) matches type(requested)]

THEN  assign the room to the user.}

\item {\it IF [room has a priority user] and [the user is already
assigned] and [room(capacity) $>$ course(space-requested)] and [no
time conflict in assigning this room] and [type(room) matches
type(requested)]

THEN  assign other users.}

\item {\it IF [room(priority) == special purpose] and [user belongs to
the special users of this room] and [room(capacity) $>$
course(space-requested)] and [no time conflict in assigning this room]
and [type(room) matches type(requested)]

THEN  assign the room to the user.}
\end{itemize}

\subsection{Components of the Rule-Based System}

This system consists of a number of heuristics implemented to take
care of various cases that arise when carrying out class
scheduling. We have developed this system specifically for the problem
of academic scheduling. The basic data structures or components of the
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 Structures} to keep track of which hour or
time slot is occupied and which is not.

\item {\bf Structure of department inclusion} many departments belong
to other larger departments or colleges, etc.
\end{itemize}

\subsection{The Overall Function of the System}

\begin{itemize}
\item It takes in data from external sources:
\begin{itemize}
\item Course data supplied by the university.
\item Building-room data also provided the registrar's office.
\item Department-to-building distance matrix.
\item Inclusion data, which a list of all colleges and schools and
their associated departments or sections. Each list is headed by a
college or a school prefix followed by its associated departments
prefixes (i.e. ECS CS MAE  etc.).
\end{itemize}
 Then builds an {\it internal database}. 
\item Using this internal database, the scheduling process takes place.
\end{itemize}

The scheduling process involves:

\begin{itemize}
\item Checking distance.
\item Checking room type, building, and hours occupied.
\item Check and compare hours for any possible conflict.
\item Check rooms for any possible space conflict.
\item Keep track of and update the list of hours already scheduled 
      (or occupied). 
\end{itemize}

\subsection{The Output of the Rule-Based System}

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} algorithm to
yield a final legal schedule.

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

\subsection{Mapping the Problem Components onto Time Periods}

The two sketches in Figure \ref{components-mapping} show roughly how the
various main components of the timetabling system are mapped onto the
desired time periods.

\begin{figure}[htb]
\begin{center}
\begin{picture}(380,380)
\psfig{figure=tuples-periods.ps,height=380pt,width=380pt}
\end{picture}
\end{center}
\caption{Mapping the problem components onto the time slots.}
\label{components-mapping}
\end{figure}

\subsubsection{Constraints}

The study case dealt with here is {\it course scheduling} at the
university level for both graduate and undergraduate students. Given
the various student and course section information, a host of
constraints need to be satisfied for any successful scheduling of this
nature. In addition to those previously stated in this report, here is
a sample ({\it hard and soft}): 
\begin{enumerate}
\item Section must be open. ({\it hard})
\item Student must meet eligibility criteria for the section. ({\it
hard})
\item Section meeting time may not conflict with other ``enrolled''
sections. ({\it hard}).
\item An enrollment balance by gender should be obtained in Honors
seminar sections. ({\it soft})
\item For each student, balance $MWF$ and $TuTh$ sections. ({\it hard})
\item Do not enroll athletes in courses that conflict with their sport
practice time. (may be {\it hard} or {\it soft}, depending on the sport)
\item Balance enrollment in multi-section courses. ({\it soft})
\item Enroll students in ALL parts of a course when associated sections 
(i.e. recitation, labs) are required. ({\it hard})
\item Optimize 1st choice course enrollments by attempting all 1st
choice courses for all students before attempting 2nd and 3rd
choices. ({\it soft}) 
\item A student with mapping status of {\it Req} should occupy a class
seat over a student with a status of priority ($\chi$). ({\it hard})
\item Class size/capacity to be observed. ({\it hard})
\item Distance/building preference or department-to-building distance
({\it soft}).
\item Various preferences of students or/and professors have to be
considered. ({\it soft}).
\end{enumerate}

Other constraints that may need to be taken into account during the
scheduling process:

\begin{itemize}
\item It is not the case, in general, that all classrooms are
available for all subjects. In reality, many subjects require a
special purpose rooms.
\item Some classes are taught for two or more hours in a row.
\item Group formation: for some subjects the classes are broken up
into option groups temporarily forming new classes.
\item The schedule should have as few ``holes'' as possible; that is
classes should be ``glued'' together.
\item Student with a ``required'' mapping status should occupy a class
seat over a student with other status.
\item Two courses of the same topic are scheduled on two different
working days (may be).
\item The predecessor-successor relation between the subjects/topics
is satisfied.
\item Classes may be designated as clashing with other classes because
of common students. 
\item The timetable may consist of an arbitrary number of periods per
day.
\item Some rooms may be declared unavailable during any time period.
\item Class subject combinations may request a preference for certain
periods.
\item Individual professor and class preferences may be specified for
specific rooms even if they are taken from a group or rooms.
\item Some classes may be grouped with others.
\item Daily limits must be specified to restrict professors from
taking more than a specified number of classes per day.
\item In order to schedule a number of classes at the same time, it is
possible to link class tuples together. In this way, the cost of a
move is the sum of the individual costs of each class tuple, however,
they are all moved at the same time.
\end{itemize}

\section{Timetabling via Simulated Annealing}

Simulated annealing (SA) has been widely used for tackling different
combinatorial optimization problems, particularly academic
scheduling \cite{3,4,39}. The results obtained depend heavily on the
cooling schedule used. We initially used the most commonly known and
used schedule, which is the geometric cooling, but later tried the
method of geometric re-heating based on cost \cite{2}.  

A comprehensive discussion of the theoretical and practical details of
simulated annealing is given in \cite{17}. It
suffices here to say that 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. 

\subsection{Some Advantages and Disadvantages of SA}

\begin{enumerate}
\item Relatively easy to implement.
\item Applicable to almost any combinatorial optimization problem.
\item It usually provides reasonable solutions, depending on the
cooling schedule(s) used.
\item Can easily be combined with other heuristics, such as rule-based
systems, forming quite useful hybrid methods for tackling a range of
complex problems.
\item The main drawback is the requirement for long run times.
\end{enumerate}

\subsection{The Algorithm}

The following is a sketch of the SA algorithm with a ``generic''
cooling schedule:

\vspace{0.5cm}
\vspace{.05cm}
\vspace{.25cm}

Let ${\cal N}_{s}$ be the neighborhood of schedule $s$.
\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}

\vspace{.25cm}
\vspace{.05cm}
\vspace{0.5cm}

\subsection{Mapping of Timetabling Into Annealing Algorithm}

The most obvious mapping of timetabling (TTS) into the SA algorithm
involves the following constructs:

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 cause a conflict
in the professor's schedule.

\item E(C): is the cost of scheduling certain classes at/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 a move) is the exchange of one or more of the
following:

\begin{itemize}
\item Class swapping: 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}

%% 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{enumerate}
Along with the output of the rule-based system, the algorithm also
takes the following as input:
\begin{itemize}
\item A list of courses that have not been already scheduled and their
associated professors, room categories, etc.
\item A list of rooms provided by the registrar's office.
\item A department to building distance matrix.
\item A list of students and their course preferences.
\item A list of courses that are not allowed to be scheduled
simultaneously.
\end{itemize}

\subsection{The Annealing Schedules}

Two annealing schedules have been used for our experiments: geometric
cooling and an adaptive re-heating as a function of cost (RFC, for
short). This later schedule is due to Abramson\cite{2}. 

\subsubsection{Geometric Annealing Schedule}

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

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

where $\alpha$ is typically in the range $0.95 \ldots 0.99$. 
This schedule is used as a base line for comparison with 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}}:
%% 
%% The state of the system is not taken into account in any way, and
%% thus can not adapt the intensity of the search depending on the
%% complexity of the problem.

\subsubsection{Reheating as a Function of Cost (RFC) Schedule}

{\bf \underline{Some background}}:
\begin{itemize}
\item In combinatorial optimization problems, {\bf phase transitions}
can be observed as sub-parts of the problem are resolved. Ray Lister
\cite{7} , in tackling the TSP, and Abramson \cite{2} observed that at
high temperatures the gross structure of the solution is resolved, and
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 what is called the {\bf specific
heat} of the substance. A {\bf phase transition} occurs at a
temperature $T_{msh}$ 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_{msh}$). Generally, the higher the best cost, the higher the
temperature which is required to escape the local minimum.

\item $T_{msh}$ is the temperature at which the maximum specific heat
occurs, or at which the system changes state.
\end{itemize}

{\bf \underline{The schedule}}:

\vspace{0.5cm}
\hrule
\hrule
\hrule
\hrule
\hrule
\vspace{.05cm}
\hrule
\vspace{.25cm}

\begin{itemize}
\item Let $C_i$ to denote the cost of configuration $i$.

\item At temperature $T$, the acceptance probability is: 
\be{T.1}
Pr_i(T) = {e^{-C_i \over {kT}} \over \sum_j{e^{-C_j \over {kT}}}}\,\,.
\ee

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

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

\item The variance of the cost (or energy) at $T$ is:
\be{T.4}
\sigma^{2}(T) = <C^{2}(T)> - <C(T)>^{2}\,\,.
\ee

\item Using the above derivations, the specific heat: 
\be{T.5}
T_{sh}(i) = {\sigma^{2}(T) \over T^{2}}\,\,, \text{where}\,i \in
\{1,2,\ldots,n\,\}\,.
\ee

\item Now the maximum specific heat:
\be{T.5.1}
T_{msh} = max(T_{sh}(i))\,\,, \text{where}\,i = 1,2,\ldots,n\,.
\ee

\item The new temperature is set to:
\be{T.6}
T_{new} = P \cdot C_b(s) + T_{msh}\,\,.
\ee

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

\vspace{.25cm}
\hrule
\vspace{.05cm}
\hrule
\hrule
\hrule
\hrule
\hrule
\vspace{0.5cm}

It follows from the Boltzmann distribution (see \cite{41}) that 
\be{T.7}
{d \over {dT}}E_T = {d \over {dT}}C(T) = {\sigma^{2}(T) \over T^{2}}
\ee

%%\vspace{0.25cm}
%%\begin{figure}[htb]
%%\centerline{\psfig{figure=Temperature.vs.Tmsp.ps,height=320pt,width=320pt,angle=-90}}
%%\caption{Temperature vs Specific Heat}
%%\label{graph.2}
%%\end{figure}
%%
%%\vspace{0.25cm}
%%\begin{figure}[htb]
%%\centerline{\psfig{figure=Temperature.vs.Acceptance.ps,height=320pt,width=320pt,angle=-90}}
%%\caption{Temperature vs Percentage of Acceptance}
%%\label{graph.3}
%%\end{figure}

\subsection{More on Simulated Annealing}
Simulated annealing is a robust technique and has been applied with
success to a wide variety of problems. However, to obtain good results
the annealing runs often require a great deal of computer time.
\cite{19} criticized much of the earlier research for only
comparing simulated annealing with the simpler local optimization
heuristics (i.e. those using r-opt style moves) and not with the
more competitive Lin-Kernighan (LK) heuristics \cite{48}. They
undertook a systematic comparison of the above three methods'
performance on the graph bisection problem, for low degree random and
random geometric graphs. 
When assessed using equivalent amounts of computer time, simulated
annealing emerged a clear winner over simple local optimization for
both types of graph. Against the LK-style algorithm however, the new
technique (SA) was only slightly better for random graphs and worse
for the random geometrical class. A similar investigation was carried
out for the TSP \cite{22}\cite{51} and the results suggest that,
matched for run-time, simulated annealing beats 3-opt but not as good
as a well-designed and implemented $LK$ heuristics.

In summary, SA appears competitive with many of the best local
optimization methods. Its major drawback is the requirement for long
run times. Furthermore, 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}.

\section{Experimental Results}
\subsection{Schedule-Specific Results}
As mentioned above we have used two cooling schedules for our 
experiments, reheating based on cost and geometric cooling. Each 
schedule takes a set of parameters - the temperature reduction factor,
time at each temperature, initial temperature, and for the second
schedule a final temperature. Overall, we found that the effect of the
temperature reduction factor is even less important than was predicted
on theoretical grounds. (If it is replaced with, say, its square root,
and the number of moves at the initial temperature is doubled, the
outcome will be the same). It was arbitrarily fixed at $0.95$. Since we
desire a comparison of the cooling schedules over a range of run times
and solution qualities, the time spent at each temperature was left as
an independent variable.

For geometric cooling, the initial comparison was with a standard sort 
of stopping criterion \cite{19}\cite{51}: the run was terminated when no moves had been
accepted for three generations. (other stopping criteria are
considered). Also, we have observed that the choice of initial
temperature poses more of a challenge. To be exact, the experimental
procedure is this: Two data sets were obtained for both schedules. For
the geometric cooling, its set consists of ten runs made from each of
ten starting temperatures between $100$ and $500$ with increments of
$10$'s. For the reheating schedule, ten choices of the initial $T$
were used between $128$ and $500$ also with increments of $10$'s.

To summarize, there are two data sets, each having $10$ samples for
each of their $10$ parameter combinations. For each combination the
{\it mean run time} as well as the {\it mean final energy (cost)} over
the $10$ sample runs were computed. If one parameter combination
yielded a longer run time and higher final energy than another, it was
discarded. The remaining combinations are those that are most
efficient, that is, by construction they have the property that as 
time increases, the energy decreases. In the output side: the lowest
solution energy actually produced was $2230$ (found in $5$ out of $10$
reheating runs but only once by the geometric cooling).

\subsection{Application-Specific Results}
Our study case is quite large in comparison to the scheduling case
used by Peterson and colleagues \cite{28}. The largest case they
have dealt with involve around 1000 students, 20 different possible
majors, and an overall periodic schedules (over weeks). In the case of
Abramson and colleagues \cite{2}, the problems they dealt
with are quite small and they state that problems involving more than
300 tuples\footnote{A tuple is a combination of a class, teacher, and
a classroom. The time periods are assumed to be given.} are quite
difficult to solve.

Our study case involve real scheduling data covering three semesters
here at Syracuse University. 
Those of first and second semester are roughly of the same size:
around 13600 students, 1100 professors, staff, and teaching
assistants, 400 rooms (classrooms, seminar rooms and auditoriums), and
2500 classes. With the exception of number of rooms, the third
semester data is much smaller. Along with this, we also have utilized 
the distance (in a form of a distance matrix) between various
buildings on main campus. Given the various building preferences of
the departments, we have constructed a {\it finite state automaton} in
a matrix format $[I,J]$ between all the academic schools and
departments $[I]$ and all the buildings involved in scheduling
$[J]$. Using this matrix in conjunction with the real -appropriately
scaled- distance, a final state matrix is derived and directly used in
the scheduling process.

\subsection{Observations and Analysis}

The main objective here is to generate a solution (i.e. a feasible
timetable) subject to all binding (or hard) constraints and to
minimize the cost incurred form the medium and soft constraints.

In regard to the geometric annealing, when we start from some good
solution rather than from the usual random solution, the initial
temperature must not be too high to avoid reaching equilibrium and
``forgetting'' the supplied initial solution. For totally random
starts, this was found not to be of any help.

We also observed that the efficacy of starting annealing (using either
adaptive or non-adaptive schedules) from a good solution depends not
only on the energy (or cost) of that solution, but also on how it was
obtained, that is, on its structure. For example, \cite{19}\cite{51}
give few thoughts on this subject but as far as we know we have not
come across any kind of analysis on the topic.

Our analysis starts with Figure \ref{graph.1} which shows the
relationship between the annealing temperature and cost when using the
method of reheating based on cost. The interesting thing to notice is
that the cost begins to decrease rapidly around the temperature of
$30$ and continue decreasing picking up speed approximately at
temperature of $20$. The phenomenon of Figure \ref{graph.1} becomes
more obvious when observing Figure \ref{graph.2}, which clearly show a
maximum specific heat at about temperature $30$. Unlike Figure
\ref{graph.1}, the relationship between temperature and cost in Figure
\ref{graph.3} is sort of typical for geometric cooling. The cost
continues to decrease, albeit slowly, beyond the point shown in the
plot till reaching close to 3000. After that the rate of change
becomes even slower with either taking very short upward moves or
slightly going down but never sharp downward moves, as partly shown
in Figure \ref{graph.4}. This pattern continues for at least 10000
more iterations till termination or reaching a stopping point.

\subsection{Code and Simulations}

The code of the aforementioned two annealing schedules are written in
ANSI C and all the simulations are on the IBM RS6000 and the SP2. In
regard to the SP2, individual jobs were run separately on different
nodes using different sets of parameters and if needed also different
cooling schedules. To save space, the actual code which is in the
thousands of lines including documentations and the I/O routines, is
not included here. Therefore, if there is a need to view the code,
please notify the author.

\vspace{0.5cm}
\begin{figure}[htb]
\centerline{\psfig{figure=non-geometric.Temp.vs.Cost-gnuplot.ps,height=320pt,width=320pt,angle=-90}}
\caption{Temperature vs cost for the reheating based on cost schedule}
\label{graph.1}
\end{figure}

\vspace{0.5cm}
\begin{figure}[htb]
\centerline{\psfig{figure=non-geometric.Temp.vs.Tmsh.gnuplot.ps,height=320pt,width=320pt,angle=-90}}
\caption{Temperature vs specific heat for the reheating based on cost schedule}
\label{graph.2}
\end{figure}

\vspace{0.5cm}
\begin{figure}[htb]
\centerline{\psfig{figure=geometric1.Temp.vs.Cost-gnuplot.ps,height=320pt,width=320pt,angle=-90}}
\caption{Temperature vs cost for the geometric annealing}
\label{graph.3}
\end{figure}

\vspace{0.5cm}
\begin{figure}[htb]
\centerline{\psfig{figure=geometric.Iterations.vs.Cost-gnuplot.ps,height=320pt,width=320pt,angle=-90}}
\caption{Number of steps vs cost for the geometric annealing}
\label{graph.4}
\end{figure}

%%
%%\begin{table}[htb]
%%\vspace{0.25cm}
%%\hrule
%%\hrule
%%\vspace{0.25cm}
%%The following table illustrates some mean error results of the MFA and
%%Simulated annealing using the RFC schedule, with and without
%%the rule-based system as a pre-processor. Each of these figures is for
%%100 runs of the same size (class, classrooms, students, etc.)
%%timetabling problem.
%%\vspace{0.25cm}
%%$$
%%\begin{tabular}{|l||c|c||c|c||}
%%\hline
%%                 &\multicolumn{2}{|c|}{Mean Field Annealing}&\multicolumn{2}{|c|}{Simulated Annealing} \\ \hline\hline
%%                 & Pre-Processor & No Pre-Processor & Pre-Processor   & No Pre-Processor \\ \hline\hline
%%Mean        &  2.6   &  14.24 &  0.32  & 7.1   \\
%%Percentage  &        &        &        &       \\       
%%Error       &        &        &        &       \\ \hline
%%\end{tabular}
%%$$
%%\caption{Performance figures for MFA and SA in the presence and
%%absence of pre-processor (a rule-based knowledge system).}
%%\label{table.1}
%%\vspace{0.25cm}
%%\hrule
%%\hrule
%%\end{table}

%%\begin{table}[htb]
%%\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}
%%$$
%%\caption{Performance figures for three terms using a {\it rule-based
%%system} only. Both class and students constraints are used.}
%%\label{table.2}
%%\vspace{0.25cm}
%%\hrule
%%\hrule
%%\end{table}

%%%%------------------------------- NEW ----------------------------

\begin{table}[htb]
\vspace{0.25cm}
$$
\begin{tabular}{|l||c|c|c|c||}
\hline
                & Total Courses & Scheduled & Not Scheduled & \% Scheduled\\ \hline\hline
First Semester  &     2482      &   1688    &      794      &     68.00   \\ \hline
Second Semester &     2164      &   1527    &      637      &     70.57   \\ \hline
Third Semester  &     709       &   569     &      140      &     80.25   \\ \hline
\end{tabular}
$$
\caption{Averaged figures for three terms using a {\it rule-based
system} only. Both class and students constraints are used.}
\label{table.2.1}
\vspace{0.25cm}
\hrule
\hrule
\end{table}

%%%%-----------------------------------------------------------
\begin{table}[htb]
\vspace{0.25cm}
$$
\begin{tabular}{|l||c|c|c|c||}
\hline
                & Total Courses & Scheduled & Not Scheduled & \% Scheduled\\ \hline\hline
First Semester  &     2482      &   1787    &      695      &     72.00   \\ \hline
Second Semester &     2164      &   1690    &      474      &     78.12   \\ \hline
Third Semester  &     709       &   631     &      78       &     89.00   \\ \hline
\end{tabular}
$$
\caption{Averaged figures using a {\em rule-based system (or expert
system)}. Only class constraints are used.} 
\label{table.3}
\vspace{0.25cm}
\hrule
\hrule
\end{table}

\begin{table}[htb]
\vspace{0.25cm}
$$
\begin{tabular}{|l||c|c|c||}
\hline
                & Scheduled & Not Scheduled & \% Scheduled\\ \hline\hline
SA (geometric)  &   1465    &      1017     &     59.70   \\ \hline
SA (cost-based) &   1644    &      838      &     66.22   \\ \hline
\end{tabular}
$$
\caption{Averaged figures for three algorithms with no
pre-processor used. Both students and class constraints are used and
the data is that of the first term. {\em Note}: Annealing is
carried out on space AND time. Also, all shown figures are averaged
over 10 runs usining first semester data only.}
\label{table.4}
\vspace{0.25cm}
\hrule
\hrule
\end{table}

\begin{table}[htb]
\vspace{0.25cm}
$$
\begin{tabular}{|l||c|c|c||}
\hline
                & Scheduled & Not Scheduled & \% Scheduled\\ \hline\hline
SA (geometric)  &   2407    &      75       &     97.27   \\ \hline
SA (cost-based) &   2444    &      38       &     98.47   \\ \hline
\end{tabular}
$$
\caption{Averaged figures for three algorithms using an expert
system as a pre-processor. Both students and class constraints are
used and the data is that of the first term. {\em Note}:
Annealing is carried out on space AND time. Also, all shown figures
are averaged over 10 runs using first semester data only.}
\label{table.5}
\vspace{0.25cm}
\hrule
\hrule
\end{table}

%%--------------------------------------------------------------------
%% Need to include plots: temperature.vs.cost,
%% professor_cost.vs.timesteps, temperature.vs.delta_cost, 
%% roomsizecost.vs.timesteps, class.1.vs.rmsizecost, class.2.vs.rmsizecost,
%% diff.in.cost_class1-class2(pair of swapped classes),
%% class1_enroll.vs.rmsizecost,  class2_enroll.vs.rmsizecost,
%% class1_capacity.vs.rmsizecost, class2_capacity.vs.rmsizecost
%%

\section{Summary and Conclusion}
This part outlines the basic method and the scheduling constraints.
An academic scheduling problem that is based upon equality constraints 
is considered. 
We have used the method of simulated annealing with two types of
cooling schedules to produce our target timetabling schedules. This
target need to be a valid timetable of classes, professors, and
students with no violations at all of the hard constraints and
preferrabaly satisfying most, if not all, of the soft constraints. The
rule-based system which is used as pre-processor for the simulated
annealing  contributed greatly to the improvement of the final outcome.

We plan to carry out more experiments using perhaps other cooling
schedules and an improved pre-processor system.

\clearpage
%\newpage
%\bibliography{TTS}

%% \appendix
%% \newpage
%% \renewcommand{\thesection}{Appendix A}
%% \renewcommand{\theequation}{\mbox{A}\arabic{equation}}
%% \pagestyle{myheadings}
%% \markright{Listing - Algorithm + Data Structures}
%% \setcounter{equation}{0}
%% \section{}
%% \appendix
%% \newpage
%% \renewcommand{\thesection}{Appendix B}
%% \renewcommand{\theequation}{\mbox{A}\arabic{equation}}
%% \pagestyle{myheadings}
%% \markright{Listing - the source code}
%% \setcounter{equation}{0}
%% \section{}

\begin{thebibliography}{HSW}

\bibitem{1}
Hertz, Krogh, and Palmer,
{\it Introduction to the theory of neural computation}, 
Addison-Wesley, Redwood City, 1991.

\bibitem{2}
Abramson, Dang, and Krishnamoorthy,
{\it An Empirical Study of Simulated Annealing Cooling Schedules},
Griffith Univ. report, Nathan, Qld, Aus. 1994.

\bibitem{3}
Dowsland, K., Using Simulated Annealing for Efficient Allocation of
Students to Practical Classes. Stat and OR Group, EBMS, Univ College
of Swansea, UK, 1993.

\bibitem{4}
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{5}
K. Gosselin and M. Truchon, ``Allocation of Classrooms by Linear
Programming'', Journal of Operational Research Society 37, 561 (1986).

\bibitem{7}
R. Lister,''Annealing Networks and Fractal Landscapes'', Proc. IEEE
Int. Conf. on Neural Nets, March 1993, Vol. I, pp 257-262.

\bibitem{8}
Mouritsen, O. G, Computer Studies of Phase Transitions and Critical
Phenomena. Springer-Verlag, Berlin, 1984.

\bibitem{9}
Montanari, U, ``Networks of constraints: fundamental properties and
applications to picture processing'', {\it Information Sciences} 7
(1974), pp. 95-132. 

\bibitem{10}
Ladkin, P.B., and Maddux, R.D.,
``On binary constraint problems'', {\it Journal of the ACM} 41 (1994),
pp. 435-469.

\bibitem{11}
Mackworth, A. K.,
``Consistency in networks of relations'', {\it Artificial
Intelligence} 8 (1977) pp. 99-118.

\bibitem{12}
Gary M, and Johnson, D.
{\it Computers and Intractability: A guide to the theory of
NP-completeness}. Freeman, San Francisco (1979).

%% \bibitem{13}
%% Sorkin, Gregory,
%% {\it Theory and Practice of Simulated Annealing on Special Energy
%% Landscapes}. PhD Thesis, UC-Berkeley, California, 1992.

\bibitem{14}
Shrijver, Alexander,
{\it Theory of Linear and Integer Programming}, John Wiley and Sons, 
Chichester, UK, 1986.

\bibitem{15}
Shrijver, Alexander,
{\it A Course in Combinatorial Optimization}, to be published in 1996. 

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

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

\bibitem{18}
Van den Bout, D. E, and T. K. Miller III. Graph partitioning using
annealed neural networks. {\it IEEE Transactions on Neural Networks},
1(2):192-203, June 1990.

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

\bibitem{20}
David Johnson,
Local Optimization and the TSP, Springer Lecture Notes in CS 443,
446-461, Springer-Verlag, 1990.

\bibitem{22}
David S. Johnson,
Data Structures for the TSP, to appear in the Jr. of Algorithms (1995).

\bibitem{23}
F. Praparata, M. Shamos, 
{\it Computational Geometry}, Springer-Verlag, 1988.

\bibitem{24}
Minsky, Marvin and S Papert, {\it Perceptron} , 1988 edition.

\bibitem{25}
S. Even, A. Itai, and A. Shamir,
``On the complexity of the timetable and multicommodity flow
problems'', SIAM Jr. Computing 5 (76), 691-703.

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

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

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

\bibitem{29}
Carsten Peterson, 
``Parallel Distributed Approaches to Combinatorial Optimization
Problems - Benchmark Studies on TSP'', Neural Computation 2, 261
(1990).

\bibitem{30}
C. Peterson, B. S$\ddot{o}$derberg, 
``Artificial neural Nets and Combinatorial Optimization Problems'',
To appear in {\it Local Search in Combinatorial Optimization}, Aarts
and Lenstra (eds.), John Wiley and Sons, UK (first half of 1996).

\bibitem{31}
Paul Stolorz, 
``Abusing Statistical Mechanics to do Adaptive Learning and
Combinatorial Optimization'', Preprint, Santa Fe Institute, Dec 1991.

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

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

\bibitem{34}
P. Simic, ``Statistical mechanics as the underlying theory of
'elastic' and 'neural' optimizations'', Network 1, 89-103 (1990).

\bibitem{35}
P. Simic, ``Constrained Nets for Graph Matching and Other Quadratic
Assignment Problems'', Neural Computation, v.3, n.2, 268-281 (1991).

\bibitem{36}
F. Y. Wu, ``The Potts model'', {\it Reviews of Modern Physics} 54,
235-268 (1982).

\bibitem{37}
A. Colorni, M. Dorigo, and V. Maniezzo, 
``On the use of genetic algorithms to solve the timetable problem'', 
report 90-060, Dipartimento Di Elettronica E Informazione, 
Politecnico Di Milano, Milano, Italia.

\bibitem{38}
Alain Hertz, ``Finding a feasible course schedule using Tabu search'',
Discrete Applied Mathematics 35, 255-270, 1992.

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

%% \bibitem{40}
%% Andrew Gee, Problem Solving with Optimization Networks, PhD Thesis,
%% The Univ. of Cambridge, Dept. of Engineering, July 1993. 

\bibitem{41}
S. R. White, ``Concepts of scale in simulated annealing''. In
Proceedings of the IEEE Int. Conference on Circuit Design, pp 646-651,
1984. 

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

\bibitem{49}
H. A. Eiselt and G. Laporte, ``Combinatorial Optimization Problems
with Soft and Hard Requirements'', J. Operational Research Society,
vol. 38, No. 9, pp. 785-795, 1987.

\bibitem{50}
J. Paulli, ``A computational Comparsion of Simulated Annealing and
Tabu Search Applied to the Quadratic Assignment Problem'', in Applied
Simulated Annealing, R. Vidal (ed), Springer-Verlag LNEMS 396,
1993.

\bibitem{51}
David Johnson and Lyle 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{42}
%% Martin Simmen,
%% PhD Thesis, Physics Dept, Univ. of Edinburgh, 1993.

%% \bibitem{43}
%% P. Simic, private communication.

\bibitem{44}
Martin Simmen, private communication.

\bibitem{45}
Andrew Gee, private communication.

\bibitem{46}
Carsten Peterson, private communications.

\bibitem{47}
Mike Carter, private communications.

\bibitem{52}
David Johnson, private communication.

\bibitem{53}
Geoffrey Hinton, private communication.

\end{thebibliography}

\end{document}

