\documentclass{amsart}[12pt]

\usepackage{color}
\newcommand{\red}{\color[rgb]{1.0,0.2,0.2}} % red

\begin{document}
\title{Progress Report Sample: Exam Period Length and Conflicts}

\author{Joel Friedman}
\address{Department of Computer Science, 
        University of British Columbia, Vancouver, BC\ \ V6T 1Z4, CANADA,
        and Department of Mathematics, University of British Columbia,
        Vancouver, BC\ \ V6T 1Z2, CANADA. }
\curraddr{}
\email{{\tt jf@cs.ubc.ca} or {\tt jf@math.ubc.ca}}
\thanks{Research supported in part by an NSERC grant.}
\urladdr{http://www.math.ubc.ca/~jf}

% \date{March 28, 2002}

\maketitle                 % Produces the title.
\setcounter{tocdepth}{3}
\tableofcontents

\noindent
{\bf Copyright:\ \ }
Copyright Joel Friedman 2017.  
Not to be copied, used, or revised without explicit written 
permission from the copyright owner.

\bigskip

{\red This is an example of a proposal. I am putting subsections
headings and details that may not appear in a publication.}


\section{Introduction}

\subsection{Overview} 

{\red [Short paragraph with one or two sentences.]}
The goal of this article is to study tradeoffs between
the length of a final exam period the number of students with exam conflicts.
We also study the effect of allowing large classes to give individual exams
for each section.

\subsection{Motivation}

{\red [Short paragraph with one or two sentences.]}
Our motivation is that
students and teaching staff tend to prefer a short exam period, but
exam conflicts creates additional work for the teaching staff.

\subsection{Specific Questions in this Line of Research}

\ {\red [One to three paragraphs.]}

The first type of questions we study involve varying the length of the
exam period, and seeing how the number of conflicts increases as the
period shortens.
Specifically we want to know under what circumstances there
is a threshold phenomenon, meaning that the number of conflicts is
extremely sensitive to the length of the exam period in a small interval of 
lengths,
and is otherwise fairly insensitive to the length.
We wish to study this question for a number of exam scenarios, based
on the size of the university and versatility of the programs.

We will also examine if allowing large
classes to schedule separate exams for each of its sections
can significantly reduce the exam period length.


\section{Models}

{\red Give some precise models you can work with.  Start with
a simple one; if there are more elaborate models, describe them.}

\subsection{Basic Model}

The simplest model of exam schedule is the classical model
of exam scheduling formulated as an ILP, akin to a graph colouring problem.  
The basic setup is
that we have $n$ classes and
$m$ possible exam periods, and
we are given the set, $P$, of pairs $(i,j)$ with $1\le i,j \le n$ such
that classes $i$ and $j$ have common students.
For each possible exam schedule, assigning classes to exam periods, we set
for $i=1,\ldots,n$ and $k=1,\ldots,m$
$$
x_{ik} = \left\{
\begin{array}{ll} 1 & \mbox{if class $i$ is assigned colour $k$, and}
\\ 0 & \mbox{otherwise.} \end{array}
\right.
$$
Conversely, if $x_{ik}$ are variables such that are either $0$ or $1$ and
such that
\begin{equation}\label{eq_each_class_one_colour}
\sum_{k=1}^m x_{ik} = 1,
\quad 
\mbox{for all $i=1,\ldots,n$}
\end{equation}
then we can interpret the $x_{ik}$ as determining an assignment of classes
to exam periods.  In this description, an exam schedule has no conflicts
if for all $(i,j)\in P$ and all exam periods $k=1,\ldots,m$ we have
\begin{equation}\label{eq_each_edge_is_monochromatic}
x_{ik}+x_{jk} \le 1
\quad
\mbox{for all $(i,j)\in P$ and $k=1,\ldots,m$.}
\end{equation}
So a conflict free schedule is equivalent to the feasibility of $x_{ik}$
subject to 
\eqref{eq_each_class_one_colour} and 
\eqref{eq_each_edge_is_monochromatic}.

\subsection{More Refined Modeling for Classes}

A fancier model is to replace
\eqref{eq_each_edge_is_monochromatic}
by introducing variables $y_{ijk}=0,1$ subject to
$$
x_{ik}+x_{jk}\le 1+y_{ijk}.
$$
Then the minimum value of 
$y_{ijk}$ is $0$ if $i,j$ aren't both assigned the
colour $k$, but otherwise $y_{ijk}$ must be $1$; one can then seek to
minimize 
$$
\sum_k \sum_{(i,j)\in P}  y_{ijk} w_{ij}
$$
where $w_{ij}>0$ is some measure of how bad it is to assign classes $i$
and $j$ to the same exam period.

\subsection{Modeling Students in Classes}

A refinement of the above 
model would be to keep track of individual students;
we could try to 
minimize the number of students {\em exam hardships},
i.e., three exams in a 24 hour period, or get a more accurate count
of how many conflicts there will be.

This can be modeled by the data that specifies for each of $s$ students,
the subset of classes the student is taking.
So for $\ell=1,\ldots,s$ we are given the subset 
$S_\ell\subset\{1,\ldots,n\}$
of classes that the $\ell$-th student is taking.

Given this data, in terms of the variables $x_{ij}$ above,
the $\ell$-th student does not have
an exam hardship during any four consective exams (representing a 24-hour
exam period) provided that
for each $k=1,\ldots,n-3$ and each $\ell=1,\ldots,s$ we have
$$
\sum_{j=k}^{k+3} \sum_{i\in S_\ell} x_{ij} \le 2 \ .
$$
Otherwise we could introduce
a variable $h_\ell$, which is $1$ if student $\ell$ has some exam hardship
and $0$ otherwise, and then require
$$
\sum_{j=k}^{k+3} \sum_{i\in S_\ell} x_{ij} \le 2 + 2 h_\ell \ ;
$$
hence the minimum value of $h_\ell$ is $0$ if student $\ell$ has no
hardships, and $1$ otherwise.
Then we can use the sum of the $h_\ell$ in the objective function.


\section{Data}

Using the UBC website, we have gathered the course requirements for 
students majoring in the following degree programs:
(1) B.A.~in Mathematics, (2) B.Sc.~in Computer Science,
(3) B.A.~in Psychology.
We have gathered class sizes in the last year for the core courses in such
programs, and taken a sample of possible electives.
See Appendix~A for this information.

Using the above data, we have created data sets of sample course selections
for students in years 1---5 in each of these majors, by
{\red state how this is done}.

We have also created some data sets of the number of exam conflicts in
each pair of courses by
{\red state how this is done}.

\section{Our Algorithms}

{\red Describe the LP/ILP/QP software you are using.}
We use the Gurobi libraries in Python to solve the ILP's based on
the above ILP's.

{\red If you are using other algorithms, describe them.}

\section{Our Main Current Results}

\section{Obstacles Encountered So Far}

\section{Questions for Future Research}

Our next steps are to {\red describe your very next step or two.}

{\red Give a list of specific
questions that would be good to study, including (1) some that you
might have time for, and (2) one or two that you won't have time for.}


\end{document}