%% LATEX TWICE TO GET THE REFERENCES RIGHT
\documentstyle[11pt]{article}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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}

\pagestyle{empty}
\begin{flushright}
{\sl Draft-Ver.4}
\end{flushright}
\vfill
\begin{center} 
\hrule
\hrule
\hrule
\hrule
\hrule
\hrule
\hrule
\hrule
\hrule
\hrule
\vspace{.05cm}
\hrule
\vspace{.25cm}
{\bf 
Mean Field Annealing and non-Euclidean Combinatorial Optimization 
Problems: The case of Academic Course Scheduling, (PART I: The Algorithm)
}
\vspace{.25cm}
\hrule
\vspace{.05cm}
\hrule
\hrule
\hrule
\hrule
\hrule
\vspace{1cm}

Saleh Elmohamed\\
Geoffrey Fox\\
Paul Coddington\\
Dept. of Computer Science, and\\
Northeast Parallel Architectures Center,\\
Syracuse University\\
Syracuse, NY 13244\\
saleh@top.cis.syr.edu,$\;\;$ \{gcf, paulc\}@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. In our approach, we utilize feed-back
artificial neural system models along with the mean field theory 
approximation. Peterson's \cite{Peterson-89.1}\cite{Peterson-89.2}
Potts normalization conditions and equality constraints are extended to suit our study case.

\vfill
\noindent{\bf Key words : feed-back neural nets, MFT, 
tanh functions, Potts systems, constraints, events, stochastic
updating, annealing.}

\vfill
\centerline{\today}
\vfill

\newpage
\pagestyle{empty}
\tableofcontents


\newpage

\pagestyle{plain}

\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 ({\it CO})
problem, which is academic scheduling at the university level. For this
work we utilize the system of {\em course demand tracking and scheduling} of
first year undergraduate students at Syracuse University. 
 
From the various categories of artificial neural systems ({\it ANS})
for tackling {\it CO} problems, we choose the one most suitable for
the type of problem at hand; and that is the family of: 
{\it ``Pure'' feed-back ANS based on multi-state neurons with 
mean field theory (MFT) equations controlling the dynamics}. 
These {\it MFT} equations are used in place of the CPU
demanding stochastic updating procedures often used to avoid getting stuck
in local minima. 
One point worth mentioning is that one of the main reasons we are taking this
approach because it totally differs from exact and most other heuristic methods
in the sense that it has not trial-and-error mechanism, rather it ``feels'' its
way to a good solution. 

\section{Background and Motivation}

\subsection{Some Background}

The problem of academic scheduling or timetabling has been tackled 
by far too many researchers \cite{Carter-93} mostly in
the field of operations research. Unfortuantly, most of the work
we are aware of rarely takes the students and their needs into
account during the operation of scheduling. This, perhaps, may not
be that big of an issue when scheduling classes at the high school
level; but when  it comes to scheduling at a university or college
level, the students constitute a prime component in the 
scheduling equation.

Lately, there have been a number of ``non-conventional'' (or novel)
methods utilized to tackle this problem from different angles. Chief 
among them are neural networks \cite{Hop-85}, simulated annealing
\cite{Vidal-93}, genetic algorithms \cite{Colorni-92}, 
Tabu search \cite{Hertz-92}, and various combinations of 2 or more of these
techniques. Most of these utilizations were directed toward finding
optimal tours for the TSP. In this paper, we shall confine ourselves
to the neural net approach. 

Much of the work in the neural nets field has centered on
understanding and improving on the Hopfield-Tank's TSP
algorithm \cite{Hop-85} (HT, for short). 
HT proposed that CO problems could be solved using such analogue 
networks. To achieve this, one needs a representation of the problem
in which the feasible solutions lie at ``hypercube'' vertices, 
and a quadratic energy function for which the minima correspond to 
solutions and the depth of each minimum reflects the solution quality.
In practice however, considerable difficulties have been encountered carrying
this program out for the TSP, leave alone non-Euclidean CO problems
such as scheduling.

\subsection{What is the Potts approach and why utilize it?}

Clearly the original HT algorithm had difficulty constraining the
network into valid solutions. One way forward is therefore to lessen
the computational burden being placed on the network. This can be
done by constraining each city (in the TSP case) to be 'on' only once,
by enforcing $\sum_a V_{ia} = 1\; \forall i$, ($V_{ia} = 1/0$ means
that the city $i$ is/is not the $a^{th}$ city visited in the
tour), rather than relying on an energy penalty term to try and do
this (as in HT). This idea was first utilized and analyzed for the TSP
case by, among others, Peterson and S$\ddot{o}$derberg \cite{Peterson-89.1}. It
greatly enhances the degree of convergence to valid solutions.
Later, Peterson and colleagues somewhat extended the technique and
applied it to a case of high school scheduling \cite{Peterson-89.2}
and \cite{Peterson-91}.

In \cite{Peterson-89.1} the normalization occurs in the context of 
a {\it mean field annealing} approach. This generally yields the same 
final network equations as the 'neuronal circuit' approach of 
\cite{Hop-84}, but the exposition is a little bit clearer, as it is laid out 
in a statistical mechanics framework\footnote{This equivalence was 
also noted in \cite{Hop-85}. P. Simic and Martin Simmen brought this
point to our attention.}. The idea is to regard each hypercube vertex
(see \cite{Hop-84}) as a configuration, with and associated ${\it E}$
value. The partition
function is then formed by summing the Boltzmann factors of the 
admissible configurations. (For example, in the HT algorithm, all of
the $2^{N^2}$ configurations are admissible, whereas if each city
-in the TSP case- is restricted to being visited only once, then
only $N^N$ vertices are admissible). After taking a mean field 
approximation, saddlepoint equations are derived (see next sections),
the solutions of which pick out the dominant states of the network
at the current temperature ${\cal T}$.

This statistical mechanics characterization gives a somewhat clearer
picture of why the normalized model (which corresponds
to a type of Potts model \cite{Wu-82} in physics, in that each
city represented by a spin which can be in only one of $N$ states)
ought to perform better than HT model. As \cite{Peterson-89.1}
indicated, the HT algorithm's partition function sums over a vast
number of configurations which are nothing like tour states -in TSP,
and even  though these offenders have small Boltzmann weights their
large number inevitably affects the thermal average quantities.
The other advantage that draws us to this derivation is that, by
introducing a temperature, the concept of annealing, i.e. reducing
${\cal T}$ during a run, can be justifiably employed.

The above two paragraphs outline more or less the reasons
behind our utilization of mean field annealing.

\section{Class Scheduling and Mean Field Annealing}

\subsection{Notation and Definitions}

In this section we define some key terms and concepts used 
in this paper (some are adapted from the work of Peterson).

Let ($N_p$) to be a number of professors that give ($N_q$) classes in 
($N_x$) class-rooms at ($N_t$) time slots. Event-wise, $(p,q)$ event
-- denoting a professor $p$ giving a class $q$ -- takes place in the
space-time slot $(x,t)$ -- denoting classroom $x$ at time $t$.

\bd{dfn-0}
\ \ Let $S_{pq;xt}$ to denote the Potts (or multi-state) neuron(s), where
\be{form-1}
S_{pq;xt} =
\twoif {1} {\text{if event $(p,q)$ takes place in $(x,t)$ ,}}
       {0} {\text{otherwise.}}
\ee
\ed

\bd{const-dfn.1}
\ \ There are two types of constraints to deal with in this paper:
\begin{enumerate}
\item Those involving professors, classrooms, subjects, and time
periods.
\item Constraints dealing with students scheduling.
\end{enumerate}
In addition, some of these constraints are usually classified to be
{\bf hard} and the rest are {\bf soft}.
\ed

\bd{const-dfn.2}
Here, we define a number of {\bf hard constraints} of the first
type (see dfn \ref{const-dfn.1}) .
\begin{itemize}
\item An event $(p,q)$ should occupy precisely one space-time slot $(x,t)$.
\end{itemize}
This constraint can be embedded in the neural net in terms of the Potts \\
normalization condition:
\be{form-2}
\sum_{x,t} S_{pq,xt} = 1
\ee
\begin{itemize}
\item Different events $(p_1,q_1)$ and $(p_2,q_2)$ should not occupy the same
space-time slot $(x,t)$.
\end{itemize}
\be{form-3}
E_{XT} =
{1 \over 2}\sum_{x,t}\sum_{p_1,q_1}\sum_{p_2,q_2}S_{p_1q_1;xt}S_{p_2q_2;xt} = 
{1 \over 2}\sum_{x,t}{(\sum_{pq}S_{pq;xt})}^2
\ee
\begin{itemize}
\item A teacher $p$ should have at most one class at a time.
\end{itemize}
\be{form-4}
E_{PT} =
{1 \over 2}\sum_{p,t}\sum_{q_1,x_1}\sum_{q_2,x_2}S_{pq_1;x_1t}S_{pq_2;x_2t} = 
{1 \over 2}\sum_{p,t}{(\sum_{qx}S_{pq;xt})}^2
\ee
\begin{itemize}
\item A class $q$ should have at most one teacher at a time.
\end{itemize}
\be{form-5}
E_{QT} =
{1 \over 2}\sum_{q,t}\sum_{p_1,x_1}\sum_{p_2,x_2}S_{p_1q;x_1t}S_{p_2q;x_2t} = 
{1 \over 2}\sum_{q,t}{(\sum_{px}S_{pq;xt})}^2
\ee
\ed

\subsection{Mean field equations and more on the formation of constraints}
 In \cite{Hop-84}\cite{Hop-85}, 
 Hopfield introduced a model with neurons having a graded
 response. So given $I_i$ a fixed input bias to neuron $x_i$, $W_{ij}$ the weight
 of the connection between neurons $(x_i,x_j)$, and parameter 
 ${\cal T}$ to denote the {\it Temperature}, the behavior of $x_i$
 can be stated as:
 \be{form-JH}
 x_i =
 {1 \over 2} + {1 \over 2}\cdot tanh (({\sum_{i \neq j}W_{ij}x_j - I_i}) \times {1 \over {\cal T}})
 \ee
 When (${\cal T}$) approaches ($\infty$), function ({\ref{form-JH})'s response takes 
 on a step-wise form. These models of \cite{Hop-85} are known to be a bit sensitive 
 to parameter tuning for real world applications, especially those of the type that involves 
 ``finding'' or ``searching for'' ($1$ out-of $N$) type problems. 
 The mean field Potts model -as previously outlined- 
 aims at removing such inefficiency, and as stated in \cite{Peterson-89.1}\cite{Peterson-92},
 it appears to be successful in doing so. 

\bd{don-1}
\ \ At a finite (${\cal T}$), $x_i$ (of eq. \ref{form-JH})
can be replaced by an MFT variable $\upsilon_{ia}$, then
differentiating to obtain the Potts MFT equations:

\be{form-5.1}
\upsilon_{ia} =
- {1 \over {\cal T}} \cdot {{\partial E}[{\vec\nu}] \over {\partial \nu_{ia}}}
\ee
\be{form-5.2}
\nu_{ia} =
{e^{\upsilon_{ia}} \over {\sum_b e^{\upsilon_{ib}}}}
\ee

Which enforces

\be{form-5.3}
\sum_{a} \nu_{ia} = 1.0
\ee
Where $a$ denotes the vector components or all the elements of the group.
Also, we could state that 
$\nu_{ia} \approx Prob(neuron(i) \in state(a))$ --- a fuzzy type variable.
Equations (\ref{form-5.1}, \ref{form-5.2}) are computed in an iterative manner.
\ed

\bd{dfn-2}
\ \ To carry out the minimization of the energy functions of definition (\ref{dfn-0})
we need to convert the neural variables $\{0,1\}$ of $S_i$ to their correspondence of 
{\it mean field variables} at (${\cal T}$). These correspondences are derived
to be: 

\be{form-6.1}
V_{pq;xt} \approx <S_{pq;xt}>_{\cal T}
\ee
A thermal averages of the original binary spines, with the following 
multi-state $MFT$ equations (see (\ref{form-5.1}, \ref{form-5.2}) for 
a general format):

\be{form-6}
U_{pq;xt} =
- {1 \over {\cal T}} \cdot {{\partial E} \over {\partial V_{pq;xt}}}
\ee
\be{form-7}
V_{pq;xt} =
{e^{U_{pq;xt}} \over {\sum_{x^{'}t^{'}}e^{U_{pq;x^{'}t^{'}}}}}
\ee
\ed

The $MFT$ equations of ($\upsilon$ and $\nu$) are
solved {\it iteratively} either synchronously or asynchronously, under
${\cal T}$.
Also, these equations give rise to 2 phase  transitions; one in $x$ (space) and the other
in $t$ (time). This leads to factorization of the system by replacing $S_{pq;xt}$ by
{\bf $X$-neurons} $S^{(X)}_{pq;x}$ and {\bf $T$-neurons} $S^{(T)}_{pq;t}$ :

\bd{dfn-3} \ \
\be{form-8}
S_{pq;xt} =
S^{(X)}_{pq;x} \cdot S^{(T)}_{pq;t}
\ee
With separate Potts conditions:
\be{form-9}
\sum_{x}S^{(X)}_{pq;x} = 1
\ee
\be{form-10}
\sum_{t}S^{(T)}_{pq;t} = 1
\ee

For {\bf $X$-neurons} and {\bf $T$-neurons}, respectively. 
Rather than dealing with $p$ and $q$ directly, an independent variable
($i$) -acting as an event index- to which $p$ and $q$ are attributes
$p(i)$ and $q(i)$. The value of these exits in a look-up table which
contains all the relevant information to process each event ($i$).
Now, the above (\ref{form-9}, \ref{form-10}) conditions can be 
re-stated as follows:

\be{form-9.1}
\sum_{x}S^{(X)}_{i;x} = 1
\ee
\be{form-10.1}
\sum_{t}S^{(T)}_{i;t} = 1
\ee

\ed

During annealing, as we go from a higher temperature to a lower one, 
a {\it phase transition} is passed at (${\cal T} = {\cal T}_c$), where 
${\cal T}_c$\footnote{See pp 29-31, \cite{Hertz-91} for an approximate
value in the case of Ising ferromagnets.} is the {\it critical temperature}. 
The value of ${\cal T}_c$ set the scale or the range of the value of
${\cal T}$, and it is estimated by expanding \ref{form-7} around some
trivial fixed-point such as

\be{trivial-form}
V^{(0)}_{pq;xt} = {1 \over {N_x N_t}} \;\text{, at ${\cal T}$ = 0} .
\ee

Also ${\cal T}_c$ depends on the 
self-coupling coefficient $\beta$, and on the method of the update. 
This parameter $\beta$ acts as a
Lagrangian multiplier for the given energy constraint(s). See section
on the generic Potts algorithm and \cite{Peterson-89.1}.

\bd{dfn-4}\ \
{\em Relative Clamping}: During the revision process of an existing schedule,
sometimes it is desirable to have a certain cluster of events to stick 
together in time (or within some specified period of time). This amounts
to making the following notational replacement:
\be{form-12}
i \longrightarrow (j,k) \;\; ;
\ee
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.
\ed

\bd{dfn-3.9}
To deal with events that take place over two consecutive hours, what \cite{Peterson-89.1}
called effective $time$-neurons $\tilde{S}^{(T)}_{i;t}$ are introduced:
\be{form-11}
\tilde{S}^{(T)}_{i;t} =
\sum_{k=0}^{g_i - 1} S^{(T)}_{i;t-k} \;\;{\text{;}}
\ee
where $g_i = 1$ for single hours and $= 2$ for double hours. For those 
events that occur between one and two hours, $g_i$ can be adjusted 
accordingly to handle these cases.
\ed

Utilizing definition (\ref{dfn-3.9}), constraints (\ref{form-3},
\ref{form-4}, \ref{form-5}) can be put into the following form:

\bd{dfn-3.9.1}

\be{form-11.1}
 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}
\ee

\be{form-11.2}
 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}
\ee

\be{form-11.3}
 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}
\ee
\ed

\bd{dfn-6}\ \
The Kronecker $\delta_{q(i),q(i')}$ ensures that only
events $i$ and $i'$ with identical primordial classes (or point of origination) are, 
for example, summed over. Here, $q(i)$ and $q(i')$ refer to classes of the same type
or 2 sections derived from the same original class. 
\be{Kronecker}
\delta_{r,s} =
\twoif {1} {\text{if} r = s}
       {0} {\text{otherwise.}}
\ee
\ed

\bd{dfn-3.9.2}\ \
One important soft constraint that need to be handled is {\it group formation}.
Briefly, it can be stated as follows: for some optional subjects the
classes are broken up into option groups temporarily forming new 
classes. In order to account for this, we need a formalism that allows
for the breaking up of these primordial classes and subsequent 
recombinations into {\it quasi}-classes. This is a common practice
with those classes where the students have many choices.
To carry out such an extension to quasi-classes one might
have contributing pairs of events where the primordial
classes are different. Hence one should replace $\delta$ with
a more structured overlap matrix $\Gamma$ which is given by a look-up
table.
\be{form-11.4}
\delta_{q(i),q(i^{'})} \longrightarrow \Gamma_{q(i),q(i^{'})} \; .
\ee
\ed

\bd{dfn-3.9.3}\ \
From definitions ($\ref{dfn-4}$, $\ref{dfn-3.9.2}$), we need to make
sure that ($\forall k$) events within a given ($j$) cluster 
$p(j,k) \neq 0$. This says that there can be no ``uncovered'' class
period or a class event (that is, periods when no professor has been
assigned to an already scheduled class).
For this purpose we introduce $\tilde{\delta}_{j,k}$
according to:
\be{form-3.9.3}
\tilde{\delta}_{j,k} = \delta_{j,k}(1 - \delta_{j,0}\delta_{k,0}) \; .
\ee
If $j = 0$ then $\forall k$ , $k = 0$ .
\ed

\bd{dfn-3.9.4}\ \
Utilizing the concepts of the above definition ($\ref{dfn-3.9.2}$,
$\ref{dfn-3.9.3}$), the collision terms of definition
($\ref{dfn-3.9.1}$) are extended to ensure that all the hard
constraints are satisfied (or the solutions obtained are legal).
The extension takes the following forms:

\be{form-3.9.4.1.1}
 E_{XT}{\text{(form 1)}} =
 {1 \over 2}\sum_{jk \neq j^{'}k^{'}}\sum_{x}
 S^{(X)}_{jk;x}S^{(X)}_{j^{'}k^{'};x}
\sum_{t}\tilde{S}^{(T)}_{j;t}\tilde{S}^{(T)}_{j^{'};t}
\ee

\be{form-3.9.4.1.2}
 E_{XT}{\text{(form 2)}} =
 {1 \over 2}\sum_{j \neq j^{'}}\sum_{k k^{'}}\sum_{x}
 S^{(X)}_{jk;x}S^{(X)}_{j^{'}k^{'};x}
 \sum_{t}\tilde{S}^{(T)}_{j;t}\tilde{S}^{(T)}_{j^{'};t}
 + {1 \over 2}\sum_{j}g_j \sum_{k \neq k^{'}} \sum_{x} 
 S^{(X)}_{jk;x}S^{(X)}_{jk^{'};x}
\ee

\be{form-3.9.4.2.1}
 E_{PT}{\text{(form 1)}} =
 {1 \over 2}
\sum_{p,t} [ \sum_{jk} \tilde{\delta}_{p,p(j,k)}
 \tilde{S}^{(T)}_{j;t} ]
[ \sum_{j^{'}\neq j}\sum_{k^{'}}
 \tilde{\delta}_{p, p(j^{'},k^{'})} 
 \tilde{S}^{(T)}_{j^{'};t} ]
\ee

\be{form-3.9.4.2.2}
 E_{PT}{\text{(form 2)}} =
	{1 \over 2}\sum_{j \neq j^{'}}\sum_{k k^{'}} 
	\tilde{\delta}_{p(j,k), p(j^{'},k^{'})}
	\sum_{t}\tilde{S}^{(T)}_{j;t} \tilde{S}^{(T)}_{j^{'};t}
\ee

\be{form-3.9.4.3.1}
 E_{QT}{\text{(form 1)}} =
 {1 \over 2} 
\sum_{qt} [ \sum_{jk} \delta_{q,q(j,k)} \tilde{S}^{(T)}_{j;t} ]
[ \sum_{j^{'} \neq j} \sum_{k^{'}} \Gamma_{q,q(j^{'}, k^{'})}
	\tilde{S}^{(T)}_{j^{'};t} ]
\ee

\be{form-3.9.4.3.2}
E_{QT}{\text{(form 2)}} =
	{1 \over 2}
	\sum_{j \neq j^{'}}\sum_{kk^{'}} 
	\Gamma_{q(j,k), q(j^{'},k{'})} \sum_{t} \tilde{S}^{(T)}_{j;t}
	\tilde{S}^{(T)}_{j^{'};t}
\ee

Note: Each (form 2) above is a derivation from its corresponding (form
1) .
\ed

The factorization idea of (dfn \ref{dfn-3.9.4}) can be extended to 
{\it mean field} variables
$V^{(X)}_{jk;x}$ and $V^{(T)}_{j;t}$, corresponding to neurons
$(S^{(X)}_{jk;x})$ and $(S^{(T)}_{j;t})$, respectively.
$V^{(X)}_{jk;x}$ and $V^{(T)}_{j;t}$ can be interpreted as being 
the probabilities that the corresponding events occur
at given $x$-value and $t$-value with normalization given by the above equations
(\ref{form-9.1}, \ref{form-10.1}) .

Substituting $V$ for $S$ in (\ref{form-9.1}, \ref{form-10.1}), 
the {\it mean field} equations at a finite 
${\cal T}$, are given in terms of the {\it local fields} 
$U^{(X)}_{jk;x}$ and $U^{(T)}_{j;t}$. Now, the {\it mean field} 
dynamics proceed over the following local and mean field variables:

\bd{dfn-3.99}
\be{form-4.1.3}
U^{(X)}_{jk;x} =
- {1 \over {\cal T}} \cdot {{\partial E} \over {\partial V^{(X)}_{jk;x}}}
\ee

\be{form-4.1.4}
U^{(T)}_{j;x} =
- {1 \over {\cal T}} \cdot {{\partial E} \over {\partial V^{(T)}_{j;t}}}
\ee

\be{form-4.1.5}
V^{(X)}_{jk;x} =
{e^{U^{(X)}_{jk;x}} \over {\sum_{x^{'}} e^{U^{(X)}_{jk;x^{'}}}}}
\ee

\be{form-4.1.6}
V^{(T)}_{j;t} =
{e^{U^{(T)}_{j;t}} \over {\sum_{t^{'}} e^{U^{(T)}_{j;t^{'}}}}}
\ee

The iterations of the {\it MF} dynamics over equations ({\ref{form-4.1.3}} - {\ref{form-4.1.6}})
can either be {\bf synchronous} or {\bf serial} (see \cite{Peterson-92}).
\ed

\bd{dfn-4.2}
{\em Synchronous Updating}: \ \
A single sweep consists of first computing all the local fields, and then
updating all the neurons. That means do equations ({\ref{form-4.1.3}},{\ref{form-4.1.4}})
then perform equations ({\ref{form-4.1.5}},{\ref{form-4.1.6}}).
\ed

\bd{dfn-4.3}
{\em 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 equation ({\ref{form-4.1.3}}) followed by ({\ref{form-4.1.5}})
and/or do equation ({\ref{form-4.1.4}}) followed by ({\ref{form-4.1.6}}).
\ed

Next, we need to define 2 important {\bf soft constraints} encountered
when scheduling classes.

\bd{dfn-5}\ \
\begin{itemize}
\item {\em Spreading}: different classes in a particular area (i.e. computer science) 
should be spread over the week in a (MWF) and (TuTh) type of spread.
\end{itemize}

First, assume we have access to a subject attribute $s(j,k)$. Second, 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):
\be{day-neuron}
S^{(D)}_{i;d} = \sum_h \tilde{S}^{(T)}_{j;dh} = g_j \cdot S^{(T)}_{j;dh}
\ee

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

\be{spread-1}
E_{QSD} = 
{1 \over 2} \sum_{qsd}{[\sum_{jk}\sum_{h} \delta_{q,q(j,k)} \delta_{s,s(j,k)}
\tilde{S}^{(T)}_{jk;dh}]}^2
\ee

Refining the above a bit more 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)

\be{spread-2}
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}}
\ee

Now for some day $(d)$ of the week:

\be{spread-3}
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}
\ee

\begin{itemize}
\item {\em Glueing}: The schedule should have as few ``holes'' as possible; that is
lessons should be glued together.
\end{itemize}
The penalty term that rewards situations where $(d,h)$-events are glued to
$(d,h-1)$-events can be defined as follows:

\be{glueing-1}
E_{QDH} = -\alpha \sum_{q}\sum_{d,h} [\sum_{j,k}\delta_{q,q(j,k)}\tilde{S}^{(T)}_{j;dh}]
[\sum_{\hat{j} \neq j}\Gamma_{q,q(\hat{j},\hat{k})} \tilde{S}^{(T)}_{j;d(h-1)}] 
\ee

The energy term
of (\ref{glueing-1}) 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.}

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

\be{glueing-2}
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)}
\ee
The presence of the ($-$) sign in front of (\ref{glueing-1}, 
\ref{glueing-2}) indicates that such energy functions are to be minimized. 
Also, the ($\alpha$) in front of the the above forms governs the strength of 
this reward relative to the energies of equations
(\ref{form-3},\ref{form-4},\ref{form-5}). 
This ($\alpha$) takes on a value between zero and $1$.

Finding {\em legal} solutions with no collisions corresponds to minimizing
the {\em hard} energy:
\be{Hard}
E_{hard} = E_{XT} + E_{PT} + E_{QT}
\ee
to zero. The {\em soft energy} is given by:
\be{Soft}
E_{soft} = E_{QSD} + E_{QDH}
\ee
The total energy $E$ to be minimized is then:
\be{total}
E = E_{hard} + E_{soft}
\ee
\ed

\subsection{The generic Potts algorithm}
\subsubsection{Some general comments on the method}

Let ($N$) denotes the total number of the utilized neurons. At high
${\cal T}$, the mean field solutions will tend to be states near to the
(symmetrical) maximum entropy state: $\forall (i, a) v_{ia} = {1/N}$.
Conversely at low ${\cal T}$, finding a mean field solution will be
equivalent to using a local optimization method on the internal energy
--- a procedure highly sensitive to the initial conditions and known
to be ineffective (see p. 149 of \cite{Hop-85}).

These characteristics are similar to those of simulated annealing,
which is no surprise since both it and the mean field method compute thermal
averages over Gibbs distributions of discrete states, the former
stochastically and the later through a deterministic approximation.
It is therefore natural to couple the mean field method with the 
concept of annealing from high to low temperatures. The resulting
{\it mean field annealing} method is a powerful and general technique
which has found many applications in combinatorial optimization.

In addition to the structure of the energy function, there are three
major interdependent issues which arise in completely specifying 
a mean field annealing algorithm for a timetabling problem:

\begin{itemize}
\item The values of the coefficients of terms in the energy function.
\item The types of dynamics used to find solutions of the mean field
 equations at each ${\cal T}$.
\item The annealing schedule details, i.e. the initial temperature
 ${\cal T}(0)$, the rules for deciding when to reduce ${\cal T}$ and
 by how much, and the termination criteria.
\end{itemize}

A quantity introduced by \cite{Peterson-89.1} is called {\it
saturation},
$\Sigma$, defined as
\be{saturation}
\Sigma = {1 \over N} \sum_{ia} \nu^{2}_{ia} \;\; ,
\ee
to characterize the degree of clustering\footnote{Other measures could
also do this, e.g. an entropy measure $-\sum_{ia}\nu_{ia}ln(\nu_{ia})$,
but $\Sigma$ will be used here for consistency with the original
work.} of events in time and/or space; 
clearly $\Sigma_{min} = {1 \over N}$ and $\Sigma_{max} = 1$.

\subsubsection{The Algorithm}
\begin{itemize}
\item Choose a problem $\Longrightarrow$ (mapped into) $\{w_{ij}\}$.
\item Find the approximate phase transition temperature by linearizing equation 
(\ref{form-5.2}), see also above section.
\item Add a self-coupling $\beta$-term if necessary. Neural-wise, this
corresponds to a feedback connection from a neuron to itself.
\item Initialize the neurons $\nu_{ia}$ with ${1 \over N} \pm$ {\em random values}; and set
${\cal T}(0) = {\cal T}_c$.
\item Until ($\Sigma \approx {1 \over N}\sum_{ia}\nu^{2}_{ia}\geq 0.99$) do:
\begin{itemize}
  \item At each ${\cal T}(n)$, update all $\nu_{ia}$ via $\upsilon_{ia}$:
  \begin{itemize}
    \item  $\upsilon_{ia} = - {1 \over {{\cal T}(n)}} \cdot {{\partial E[\nu]} \over {\partial \nu_{ia}}}.$
    \item  $\nu_{ia} = {e^{\upsilon_{ia}} \over {\sum_b
e^{\upsilon_{ia}}}}. \;\;\; (\equiv f_{ia})$
  \end{itemize}
  \item ${\cal T}(n+1) = 0.9 \times {\cal T}(n)$.
\end{itemize}
\item After $\Sigma \geq 0.99$ is reached perform a {\it greedy heuristics} if needed to
account for possible imbalances or rule violations.
\end{itemize}

Since the parameter ${\cal T}_c$ is so essential to the success of the
method, the next subsection will expound a bit about it.

\subsubsection{The critical temperature ${\cal T}_c$}
--- to be completed ---

\subsubsection{Some implementation details}
The general idea is to initialize the system close to the symmetric
state at a temperature near ${\cal T}_c$, then, allowing the system
to converge to a fixed point at each temperature, anneal (i.e. reduce
${\cal T}$) until either the system reaches a stable high saturation
state or some other termination criterion is satisfied.
Specifically, the implementation used here has the following
ingredients\footnote{These follow the method used in
\cite{Peterson-89.1} but with some additions/improvements done by the
authors -see algorithm above.}:
\begin{itemize}
\item {\bf Initial State}\ \
Another possible initial value of $\nu^{n=0}_{ia}$ is $(1 +
\xi_{ia})/N$,
with the $\xi_{ia}$ being random variables drawn uniformly from 
${[-\xi, \xi]}$. Clearly $\xi$ should be $\ll 1$.

\item {\bf Convergence}\ \
At each ${\cal T}$ the $\nu_{ia}$ variables are updated as above or by
the following rule\footnote{Thanks to M. Simmen for pointing this out.
Also see \cite{Peterson-89.1}}:
\be{convergence-rule}
\nu^{(n+1)}_{ia} = \nu^{(n)}_{ia} + \gamma(f_{ia} - \nu^{(n)}_{ia}),
\;\; 0 < \gamma \leq 1\; .
\ee
Setting $\gamma = 1$ recovers the dynamics of \cite{Peterson-89.1},
and the $\gamma \rightarrow 0$ limit gives the first order Euler
integration method for the differential equation:
\be{diff-equation}
d\nu_{ia} / dt = f_{ia} - \nu_{ia}\;.
\ee
The fixed points (also referred to as the free energy minima)
of this equation constitute the mean field solutions.
The degree of convergence is monitored through some sort
of a ``tolerance'' quantity of the form 
$\sum_{ia}{(\nu_{ia} - f_{ia})}^2$.

\item {\bf Annealing Schedule} \ \
A simple exponential scheme is used, i.e. after reaching a fixed point
at ${\cal T}$, ${\cal T} \mapsto {\cal T}$ X ${\cal T}_r$, where 
${\cal T}_r \in (0,1)$ controls the cooling rate. Roughly speaking,
${\cal T}_r$ should be set to $0.9$.

\item {\bf Termination}\ \
As outlined above in the algorithm.

\end{itemize}

\section{Our study case using the Potts model}
\subsection{Scope and motivation}
Besides those reasons outlines at the beginning of the paper, another
motivating factor is to determine the algorithm's scalability for
large problems such as this case.

--- outline here what is new, etc... ---

\subsection{Notation and Definitions}

Let $q(i)$ represents a section of class $q$, $O_{q(i)}$ indicates that section 
$q(i)$ is open, and $C_{q(i)}$ is closed. Also, let $b(x,t)$ be a balanced 
interval for some time period $(t)$, $R$ is the overall set of students, 
and an arbitrary given subset is  $r \subseteq R$. 

Here, we need to introduce the $R$-neuron: $S^{(R)}_{r(i);(d(t)d(x)}$ where
$k= 1,2,\ldots$.
Each student $r(i) \in R$ should have a balanced schedule 
over the two-group of days $(MWF)$ and
$(TuTh)$. We will also use $r_s$ to denote a single student.

For $X$ and $T$ neurons, let $x(j)$ and $t(j)$ where $j= 1,2,\ldots, n$
stand for places and time slots (or events), respectively. 
Using such notation, an example of the Potts normalizations will be:
$S^{(X)}_{p(i)q(i);x(j)}$ and $S^{(T)}_{p(i)q(i);t(j)}$ respectively, where
$i=1,2,\ldots,n$ is a section index.

\bd{athletes}\ \
{\it The athletes case}: Let $\vec{r} \subseteq R$ denotes the group of athletes 
that are dealt with in this study. 
Let ($r^{*}$,$b$) be playing/training events scheduled during
the weekdays at (or during) times when academic (attending lectures) events ($r^{+}$,$a$) 
are also scheduled, or may possibly occur. Let ($d(x)$, $d(t)$) a place/time during
the week at which any of these events can occur. 

In addition to the above stated Potts neurons, we also will be using :

\begin{enumerate}
\item $S^{(\vec{r},X)}_{r^{*}b;d(x)}$ , $S^{(\vec{r},T)}_{r^{*}b;d(t)}$ :
It takes a value of ($1$) if event ($r^*,b$) takes place
in the place and time slot, respectively, of a weekday $d$, and zero otherwise.

\item $S^{(\vec{r},X)}_{r^{+}a;d(x)}$ , $S^{(\vec{r},T)}_{r^{+}a;d(t)}$ :
It takes a value of ($1$) if event ($r^+,a$) takes place
in the place and time slot, respectively, of a weekday $d$, and zero otherwise.

\item $S^{(\vec{r},X)}_{jk;d(x)}$ : 
It takes a value of ($1$) if event ($k$) of cluster ($j$) that is associated with
the $x$-neuron of $\vec{r}$ occurs in place $d(x)$, and zero otherwise.

\item $S^{(\vec{r},X)}_{\hat{j}\hat{k};d(x)}$ : 
It takes a value of ($1$) if event ($\hat{k}$) of cluster ($\hat{j}$) that is associated with
the $x$-neuron of $\vec{r}$ occurs in place $d(x)$, and zero otherwise.

\item $\tilde{S}^{(\vec{r},T)}_{j;d(t)}$ : 
It takes a value of ($1$) if cluster ($j$) that is associated with
the $t$-neuron of $\vec{r}$ occurs in time $d(t)$, and zero otherwise.

\item $\tilde{S}^{(\vec{r},T)}_{\hat{j};d(t)}$ : 
It takes a value of ($1$) if cluster ($\hat{j}$) that is associated with
the $t$-neuron of $\vec{r}$ occurs in time $d(t)$, and zero otherwise.
\end{enumerate}

In the above list, the last 2 neurons act as what Peterson calls {\it effective} $time$-neurons. Not
only will they handle periods of single hours but also variants of longer and shorter
intervals.
\ed

\bd{time-int.dfn}\ \
Set ($\epsilon$) and ($c$) to some desired values depending on the time
period of the set of classes, now, the above {\it effective}
$t$-neurons can be defined as follows:

\be{time-int.1}
\tilde{S}^{(\vec{r},T)}_{j;d(t)} = 
\sum^{g_j - c}_{k=0} S^{(\vec{r},T)}_{j;d(t-k+\epsilon)}
\ee

$\tilde{S}^{(\vec{r},T)}_{\hat{j};d(t)}$ can be defined in a similar manner.
If ($c = 1$) and ($g_i = 2$), then we are dealing with double-hour intervals
so we set ($\epsilon = 0$). If ($c = 1$) and ($g_i = 1$) then
($\epsilon = 0$) and

\be{time-int.2}
\tilde{S}^{(\vec{r},T)}_{j;d(t)} = S^{(\vec{r},T)}_{j;d(t)} .
\ee
\ed

\bd{consts-dfn}\ \
Let $S^{(R)}_{q(i)r(i);b(x,t)}$ for balancing the enrollment in a multi-section
courses. Section $q(i)$ of students $r(i)$ are balanced over space-time $b(x,t)$.

To enroll student $r(i)$ in a particular section $q(i)$ given the tag $EC$ to
indicate the status of the student, 
we have $S^{(X[T])}_{q(i)r(i);(d(x)[d(t)])}|EC\in \{0,1\}$  is set to
$0$ if $EC$ is $0$, otherwise, it is set to $1$ and the action $q(i)r(i)$ occurs during place
$d(x)$ and/or time $d(t)$. 

Let $lin(c_i,c_j)$ representing the concept that course $c_i$ is linked to some
other course $c_j$ ; in this case, $c_i$ is a pre-requisite to $c_j$. 
The degree of ``linkage'' varies between $0$ and $1$. 
It takes a value of $1$ if 
under all circumstances, course $c_i$ must be taken before $c_j$.

To deal with this link concept, we assumed in definition (\ref{dfn-5})
that we have an attribute $s(j,k)$ to represent a subject. For a
strong linkage, we will assume that we're dealing with subjects
that belong to the same cluster ($j$) (e.g. physics courses), so the 
link between various events of ($j$) is: $lin(s(j,k), s(j,\hat{k}))$.

Other degrees of linkage can involve subjects or courses from
different groups or clusters (e.g. physics and math courses, or 
engineering and math courses), and this connection is in the 
form: $lin(s(j,k), s(\hat{j},\hat{k}))$.

Let $\hat{x}(i)$ be a single location (or a seat) in class
$x(i)$ such that $i=1,2,\ldots, num$ ; where ($num$) is the 
number of class-rooms.

\ed

\subsection{Constraints}

The study case dealt with here is {\it course scheduling} at the university level
for first year (freshman) 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 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 Do not enroll students in sections when 
%%%%%%% {\it PRINT} is set to {\it NO}. 

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

\end{enumerate}

\subsubsection{Day-Class Balancing}
Each student of any particular section (i.e. $r(k)$) should have a balanced schedule
between ({\it MWF}) and ({\it TuTh}). The balancing operation is accomplished
by spreading as much as possible the courses of the student over each of ({\it MWF}) and
({\it TuTh}).

Let $D$ be the set $\{\{MWF\}, \{TuTh\}\} = \{ D_1, D_2 \}$. Assume the existence of
the subject attribute $s(j,k)$. We introduce the energy function $E_{QSD}$ that
spreads the classes ($Q$) in a particular field or subject ($S$) over the 
set $\{D_1, D_2\}$.

\bd{balance-dfn.1}
The Potts condition of balancing $S^{({\bf R})}_{q(m)r(m);b(x,t)}$
(take a value of $1$ for balanced and $0$, otherwise) is accomplished
through one (or all) of these energies:

\be{balance.1}
E^{r}_{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_1,d_2} S^{(D)}_{j,d_1} S^{(D)}_{\hat{j},d_2}
\ee

\be{balance.2}
E^{r}_{QSD_1} =
{1 \over 2}\sum_{j_1 \neq \hat{j_1}}\sum_{k_1 \hat{k_1}} 
\delta_{q(j_1,k_1),q(\hat{j_1},\hat{k_1})}
\delta_{s(j_1,k_1),s(\hat{j_1},\hat{k_1})}\sum_{d_1}\sum_{i \neq \hat{i}} S^{(D)}_{i,d_1} 
S^{(D)}_{\hat{i},d_1}
\ee

\be{balance.3}
E^{r}_{QSD_2} =
{1 \over 2}\sum_{j_2 \neq \hat{j_2}}\sum_{k_2 \hat{k_2}} \delta_{q(j_2,k_2),q(\hat{j_2},\hat{k_2})}
\delta_{s(j_2,k_2),s(\hat{j_2},\hat{k_2})}\sum_{d_2}\sum_{i \neq \hat{i}} S^{(D)}_{i,d_2} 
S^{(D)}_{\hat{i},d_2}
\ee
\ed

\subsubsection{The Case of Student Athletes}
The main constraint of this case very much analogous to the {\bf hard} constraint
stated somewhere above : {\it different events should not occupy the same space-time slot}.

\bd{athletic}

\be{athletic.1}
E^{\vec{r}}_{d(XT)} =
{1 \over 2}\sum_d\sum_{xt}\sum_{\dot{r}b}\sum_{\ddot{r}a} 
S^{(\vec{r},X[T])}_{\dot{r}b;d(x)[d(t)]} 
S^{(\vec{r},X[T])}_{\ddot{r}a;d(x)[d(t)]}
\ee

Where $(\dot{r}b)$ and $(\ddot{r}a)$ are some two different events. 
After some further refinement, we obtain:

\be{athletic.2}
E^{\vec{r}}_{d(XT)} =
{1 \over 2}\sum_{j \neq \hat{j}}\sum_{k \hat{k}}\sum_{d(x)} S^{(\vec{r},X)}_{jk;d(x)} 
S^{(\vec{r},X)}_{\hat{j}\hat{k};d(x)} \sum_{d(t)} \tilde{S}^{(\vec{r},T)}_{j;d(t)}
\tilde{S}^{(\vec{r},T)}_{\hat{j};d(t)} + {1 \over 2} \sum_j g_j \sum_{k \neq \hat{k}}\sum_{d(t)}
S^{(\vec{r},X)}_{jk;x} S^{(\vec{r},X)}_{j\hat{k};x}
\ee

Since it is always the case that athletic training facilities 
are kept separate from the academic class-rooms and lecture halls, 
a more refined energy function is obtained:

\be{athletic.3}
E^{\vec{r}}_{d(T)} =
{1 \over 2}\sum_{j \neq \hat{j}}\sum_{d(t)} \tilde{S}^{(\vec{r},T)}_{j;d(t)} 
\tilde{S}^{(\vec{r},T)}_{\hat{j};d(t)}
\ee
\ed

\subsubsection{Eligibility for Enrollment}
\bd{The Eligibility Criteria}
Before going through the process of balancing, each student 
($r(i) = r_s$) eligibility for enrolling in a given class need to be
determined.
Let the student's eligibility criteria be denoted by ($EC$), using 
the notation stated above, we could derive the
following energy function ---note: if $EC$ is set to ``No'' then it takes
a $0$ value in the energy function, otherwise, it is a $1$ :

\be{eligibility-criteria.1}
E_{QR} = 
{1 \over 2}\sum_{qr}\sum_{jk}\sum_{i} 
\delta_{q,q(j,k)}\delta_{r,r(i)} S^{X}_{ij;x(i)}|({\it EC\in\{0,1\}})
\ee

\be{eligibility-criteria.2}
\sum_{i} O_{q(i)}=1 \Rightarrow \text{Test:}\{ EC(R) + \text{satisfy-constraints}(Hard,Soft)\}
\ee
\ed

\subsubsection{Course Pre-requisite and Subsequent Assignment}

Utilizing the link concept (${\bf lin(s,s')}$) between two different
subjects (see definition \ref{consts-dfn}), 
a general energy assignment can be put together as follow: 

\bd{pre-sub.dfn}\ \
Let ($i$) stands for the situation at hand (also can be viewed as 
a space-time event).

\be{pre-requisite.1}
E_{link(1)} =
 -\gamma \sum_{is}{[\sum_{jk} \delta_{s,s(j,k)}
\tilde{S}^{(X[T])}_{ln(s,s');i}]}^{2}
\ee

\be{pre-requisite.2}
E_{link(2)} =
 -\gamma \sum_{s}\sum_{j \neq j'}\sum_{k \neq k'} \delta_{s(j,k),s(j',k')}
\sum_{i} \tilde{S}^{(X[T])}_{ln(s(j,k),s(j',k')); i}
\tilde{S}^{(X[T])}_{ln(s(j,k),s(j,k')); i}
\ee

\be{pre-requisite.3}
E_{link(3)} =
 -\gamma \sum_{j \neq j'}\sum_{k \neq k'} \delta_{s(j,k),s(j',k')}
\tilde{S}^{(X[T])}_{ln(s(j,k),s(j',k')); i}
\tilde{S}^{(X[T])}_{ln(s(j,k),s(j,k')); i}
\ee

If ($\gamma > 0$) then function minimization is the target here,
otherwise maximization will take place.
\ed

\subsubsection{Enroll in all parts  of a course}
There are a number course of different types that not only
have lecture periods but also associated sections that consist
of either labs or recitations or both. Signing up for such a course
entails enrolling in all associated sections of it. 

Let us assume the existence of some subject attribute $s(j,k)$
consisting of 2 components: $\dot{s}$ denoting lectures, and
$\ddot{s}$ stands for labs. Now the energy equation depicting
this assignment can be outlined as follow:

\be{enroll-in-all-parts.1}
E_{enroll(1)} =
{1 \over 2}\sum_{s}\sum_{jk}\sum_{i} \delta_{s,s(j,k)}\delta_{r,r(i)} 
\sum_{t} S^{(T)}_{jk;t}
\ee

\be{enroll-in-all-parts.2}
E_{enroll(2)} =
{1 \over 2}\sum_{si} \sum_{t\neq t'}[\sum_{jk} 
\delta_{s,\dot{s}(j,k)} \delta_{r,r(i)}
S^{(T)}_{jk;t}][\sum_{jk'} \delta_{s,\ddot{s}(j,k')} \delta_{r,r(i)}
S^{(T)}_{jk';t'}]
\ee

\be{enroll-in-all-parts.3}
E_{enroll(3)} =
{1 \over 2}\sum_{k \neq k'}\delta_{s,\dot{s}(j,k)}
\delta_{s,\ddot{s}(j,k')}
\sum_{t \neq t'} S^{(T)}_{jk;t} S^{(T)}_{jk';t'}
\ee

\subsubsection{Lecture hall capacity}
In order to satisfy this constraint, the following inequality
need to hold.
\be{part-1}
\forall x \sum_{i}||x(i)| - \sum_{j}\sum_{k} S^{(X)}_{jk;x(i)}| \geq 0
\; .
\ee


\subsubsection{Student status and priority mapping}
\be{status-and-priority-mapping}
E_{assign} =
{1 \over 2}\sum_{m, \hat{x}, x}\sum_{i\neq i^{'}}
S^{(X)}_{\hat{x};x} 
( S^{(R)}_{r(i);(\hat{x}(m) \in x(m))}|({\it M = Req})
+
S^{(R)}_{r(i^{'});(\hat{x}(m) \in x(m))}|({\it M = \chi}))
\ee

\subsubsection{Balance enrollment in multi-section courses}
---To be completed ---

\subsubsection{Optimize Choice Enrollment}
---To be completed ---

\subsubsection{Priority Assignment}
---To be completed ---

%% \bo{observe-1}
%% \eo



\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.
The utilized formalism allows for revision and rescheduling 
when encountering unplanned events once a legal schedule exists. 
The way this is done is basically to clamp those
events not subject to change and then heat up and cool the remaining dynamical neurons. 

The next version of this report may address some relevant aspects of 
(\cite{simic-90}, \cite{simic-91}), and perhaps compare them with the above 
concepts of the Potts model.
The experimental results will be reported in another paper. 


\newpage
\begin{thebibliography}{HSW}

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

\bibitem[PS-88]{Shamos-88}
F. Praparata, M. Shamos, 
{\it Computational Geometry}, Springer-Verlag, 1988.

\bibitem[Min-88]{Minsky}
Minsky, Marvin and S Papert, {\it Perceptron} , 1988 edition.

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

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

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

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

\bibitem[PS-92]{Peterson-92}
Peterson, S$\ddot{o}$derberg, ``Artificial neural Nets and Combinatorial Optimization Problems'',
To appear in {\it Local Search in Combinatorial Optimization}, edited by Aarts and
Lenstra , second half of 1993.

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

\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[Hopfield-84]{Hop-84}
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[Simic-90]{simic-90}
P. Simic, ``Statistical mechanics as the underlying theory of
'elastic' and 'neural' optimizations'', Network 1, 89-103 (1990).

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

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

\bibitem[CDM-92]{Colorni-92}
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[Hertz-92]{Hertz-92}
Alain Hertz, ``Finding a feasible course schedule using Tabu search'',
Discrete Applied Mathematics 35, 255-270, 1992.

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

\bibitem[Simic-93]{pc.1}
P. Simic, private communication.

\bibitem[Simmen-93]{pc.2}
Martin Simmen, private communication.

\bibitem[Gee-93]{pc.3}
Andrew Gee, private communication.

\bibitem[Peterson-92-93]{pc.4}
Carsten Peterson, private communications.

\bibitem[Carter-93]{Carter-93}
Mike Carter, private communications.


\end{thebibliography}

\end{document}
