\documentclass{amsart}

\usepackage{color}
\newcommand{\red}{\color[rgb]{1.0,0.2,0.2}} % red
\newcommand{\blue}{\color[rgb]{0.2,0.2,1.0}} % blue
\newcommand{\green}{\color[rgb]{0.0,0.5,0.0}} % green

\newcommand{\integers}{\mathbb{Z}}

\begin{document}
\title{Example of a Proposal Outline and Proposal}

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

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

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

\bigskip

\noindent {\bf OUTLINE:}

\medskip

\noindent {\bf One or Two Sentence Description:}
We will study the effects of 
university exam scheduling policies on the number of
student exam conflicts.

\medskip

\noindent {\bf Models:}
Here are some {\bf models} we plan to use:
\begin{enumerate}
\item 
A simple model:
We are given $n$ classes and a list of pairs of classes, $P$,
that have common students.
We want to know the smallest $m$ such that
one can schedule all classes in $m$ exam
slots so that any two classes with common students are in different
slots.
This is an IP, and can be viewed as a graph colouring problem.
\item
A more advanced model:
same as the previous model, except for each pair of classes with
common students we are given the number of common students.
For any $m$ we want to schedule the exams
to minimize the sum, over all pairs of 
classes assigned to the same slot,
of the number of students taking both classes.
This is an IP with a parameter, $m$.
\item
Another more advanced model:
we are given a list of $n$ classes, $s$ students, and for each student
we will list the classes this student is taking.
For each $m$ we want to schedule class exams in a way that
minimizes the total number of students with exam conflicts.
This is an IP with a parameter, $m$.
\end{enumerate}

\medskip 

\noindent {\bf Software:}
We plan to use Gurobi software to solve the above IP's.

\medskip 

\noindent {\bf Some questions we may study:}
When the exam period shrinks, how gradually do the number of exam
conflicts increase?  How easily can we model {\em exam hardships}
(i.e., having three exams in any 24 hour period)?
If large classes are broken up into smaller
sections for the purposes of exams, does this significantly improve
the number of exam conflicts?  Can the university impose some 
additional constraints 
to make the number of exam conflicts significantly
reduce (this may include deciding
the exam schedule before any students can register)?

\medskip 

% \noindent{\bf Our Basic LP/IP/QP/etc:}
\begin{description}
\item[OUR BASIC LP/IP/QP/ETC.:
Given Information]
%\item[Given Information]
We have (1) $n$ classes, (2) 
$m$ possible exam periods, and
(3) a set,
$$
P = \{ (i,j) \ | \ \mbox{classes $i$ and $j$ have students in common} \} \ .
$$
\item[OUR BASIC LP/IP/QP/ETC.:
Optimization Problem]
We wish to find if there is a schedule of exams where no two classes
with common students are assigned the same exam period.
This is {\bf equivalent to a graph colouring problem}.
{\red
[If your basic optimization problem is not equivalent to a standard type
of problem, describe a standard problem that is similar to your
problem.]
}
\item[OUR BASIC LP/IP/QP/ETC.:
The Decision Variables and Their Intuitive Meaning]
For $i=1,\ldots,n$ and $k=1,\ldots,m$ we introduce a decision variable
$x_{ik}$ whose intuitive meaning is
$$
x_{ik} = \left\{
\begin{array}{ll} 1 & \mbox{if class $i$ is assigned exam slot number $k$, and}
\\ 0 & \mbox{otherwise.} \end{array}
\right.
$$
\item[OUR BASIC LP/IP/QP/ETC.:
Formal Description]
The {\bf objective} is unimportant, since this problem is one of feasibility.
The {\bf constraints} are:
$x_{ij}\in\{0,1\}$ and
% \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}
[meaning that each class is assigned one exam slot],
$$ % \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}
[meaning that if $(i,j)\in P$, then at most one of classes $i$ and $j$
are assigned one slot].
In view of the above constraints, it is enough to require that
$x_{ij}\in\integers$ and $x_{ij}\ge 0$ for all $i,j$.
\end{description}

Our {\bf research group} includes: Jimi Hendrix (JH), Paul McCartney (PM),
and Ann Wilson (AW).

The {\bf tasks} we anticipate in this project include:
\begin{enumerate}
\item Modeling optimization problems based on synthetic data. [JH is
responsible]
\item Harvesting online information regarding UBC courses, making educated
guesses regarding course overlap based on degree requirements.
[PM is
responsible] 
\item Generating synthetic data sets based on harvested information and
various policies.
[AW is
responsible]
\item Running optimization algorithms. [JH is
responsible]
\item Statisical analysis of the results over various data sets.
[PM is
responsible]
\item Taking writeups of the above and organizing them into a coherent
report. [AW is
responsible]
\end{enumerate}

\bigskip

\newpage

\noindent {\bf PROPOSAL:}

{\bf We will study} the effects of 
university final exam scheduling policies on the number of
student exam conflicts.
Our
{\bf motivation} is that
students and teaching staff tend to prefer a short exam period, but
exam conflicts creates additional work for the teaching staff;
we seek to study these tradeoffs.
{\bf The specific policies} we study include
the length of the exam period
and requiring multi-sectioned classes to have separate exams for
each section.

Our simplest model of exam scheduling is an
IP (integer program) that is a special case of
graph colouring.
We are given 
$n$ classes and
the set, $P$, of pairs $(i,j)$ with $1\le i,j \le n$ such
that classes $i$ and $j$ have common students.
We want to know the smallest value of $m$ such that it is
possible to schedule exams in $m$ exam slots
so that any pair of classes with common
students are scheduled for different slots.

Given $n$, $P$, and $m$, we formulate the following IP: 
we introduce decision variables $x_{ik}$ 
for $i=1,\ldots,n$ and $k=1,\ldots,m$, whose values are in $\{0,1\}$,
and are meant to be
$$
x_{ik} = \left\{
\begin{array}{ll} 1 & \mbox{if class $i$ is assigned colour $k$, and}
\\ 0 & \mbox{otherwise.} \end{array}
\right.
$$
To enforce this, we impose the constraints
\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}
so that each class is assigned one exam slot; the constraints
\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}
requires at most one of each pair $(i,j)$ of classes with common students
to be assigned to each exam slot $k$.
So a conflict free schedule is equivalent to the feasibility of 
$x_{ik}\in\{0,1\}$
subject to 
\eqref{eq_each_class_one_colour} and 
\eqref{eq_each_edge_is_monochromatic}.

A more advanced 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 (such as the number of common students).

An even more advanced model would be to consider which individual
students are assigned to which classes and to try to prevent {\em exam
hardships}, i.e., three exams in a 24 hour period.

% {\red [Your project may not have many different models, but it should
% have a number of challenges that range from easier to more difficult.]}

Our data will be based on UBC requirements for the math B.A.,
from which we will generate some typical course schedules for students.  
We will then look at the number and schedule of the sections of
each class.
Time permitting, we will do this for other UBC degrees.
It is likely that we will
synthetically create larger data sets.

The simplest result we seek is the trade-off between the number
of exam slots and the number of student conflicts, and if
this trade-off has a threshold phenomenon.
We will look at a number of data sets to 
see if our conclusions are robust and what principles can be
drawn from our results.

Should time permit, we will impose some university policies that would
change the results.
For example, one could schedule individual exams for each section
of a class.
Another example is to require all students of one major (of
one faculty, etc.) to take a specific section of a course.

Our research group consists of (1) JH, in change of creating models
and running optimization algorithms, 
(2) PM, in change of harvesting online information,
(3) AW, in change of generating synthetic data sets and of 
coordinating and editing
the final report.

\end{document}